### Problem Statement

A string s is called an IOI string if it satisfies the following two conditions:
• s contains only uppercase 'I' and uppercase 'O' letters.
• There is at least one pair of non-negative integers (a,b) such that the a-th (0-indexed) character of s is 'I', the (a+b)-th character is 'O', and the (a+2*b)-th character is 'I'.
You are given a String[] mask. Concatenate the elements of mask to get one string. Each '?' character in mask can be replaced with either 'I' or 'O'.

Return the number of different IOI strings that can be formed, modulo 1,000,000,007 (1E9+7).

### Definition

 Class: IOIString Method: countIOIs Parameters: String[] Returns: int Method signature: int countIOIs(String[] mask) (be sure your method is public)

### Constraints

-mask will contain between 1 and 50 elements, inclusive.
-Each element of mask will contain between 1 and 50 characters, inclusive.
-Each character in mask will be uppercase 'I' or uppercase 'O' or '?'.

### Examples

0)

 `{"IO?"}`
`Returns: 1`
 Two strings can be formed here : "IOI" and "IOO". Only "IOI" is an IOI string.
1)

 `{"????"}`
`Returns: 4`
 There are four IOI strings of length 4 : "IIOI", "IOII", "IOIO", and "OIOI".
2)

 `{"?II"}`
`Returns: 0`
 No IOI string can be formed from "?II".
3)

 `{"I??O??I"}`
`Returns: 16`
 Character 0 is 'I', character 3 is 'O', and character 6 is 'I'. Therefore, all possible strings are IOI strings here.
4)

 `{"???I???????O???","???????????O??IO????????I???"}`
`Returns: 438952513`
 Don't forget to concatenate strings.

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13906&pm=10564

rng_58

#### Testers:

PabloGilberto , connect4 , ivan_metelsky

Math