TopCoder problem "IOIString" used in SRM 452 (Division I Level Two)



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

Writer:

rng_58

Testers:

PabloGilberto , connect4 , ivan_metelsky

Problem categories:

Math