### Problem Statement

Consider strings constructed from the letters 'A', 'B', and 'C'. You will be given an integer N and two forbidden substrings, bad1 and bad2. You are to calculate the number of strings of length N that do not contain either substring. Note that a substring need not be shorter than the string in which it is contained (e.g., "AB" is a substring of "AB").

### Definition

 Class: BadSubstrings Method: howMany Parameters: int, String, String Returns: long Method signature: long howMany(int N, String bad1, String bad2) (be sure your method is public)

### Constraints

-N is between 1 and 39, inclusive.
-bad1 contains between 1 and 39 characters, inclusive.
-bad2 contains between 1 and 39 characters, inclusive.
-Each character in bad1 is 'A', 'B', or 'C'.
-Each character in bad2 is 'A', 'B', or 'C'.

### Examples

0)

 `3` `"AB"` `"BA"`
`Returns: 17`
 There are 17 three-letter strings that do not contain "AB" or "BA", shown below: ``` AAA AAC ACA ACB ACC BBB BBC BCA BCB BCC CAA CAC CBB CBC CCA CCB CCC ```
1)

 `2` `"A"` `"BB"`
`Returns: 3`
2)

 `5` `"ABC"` `"ABB"`
`Returns: 189`
3)

 `39` `"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"` `"ABCABCABCABCABCABCABCABCABCABCABCABCABC"`
`Returns: 4052555153018976265`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4018

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6554&pm=4018

vorthys

#### Testers:

PabloGilberto , lbackstrom , Yarin

#### Problem categories:

Dynamic Programming