Consider all strings of length n made up of characters 'a' , 'b' and 'c'.

An be the number of strings such that the substring "abc" occurs exactly once.

Bn be the number of strings such that one of the substrings "aacc","bcab" and "cbba" occurs exactly once and the other two do not occur at all.

Find

The answer can be expressed as a/b such that a and b are co-prime.

Report a+b.