IOIString | Topcoder Archive

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

```
{"IO?"}
```
```
Returns: 1
```
Two strings can be formed here : "IOI" and "IOO". Only "IOI" is an IOI string.
```
{"????"}
```
```
Returns: 4
```
There are four IOI strings of length 4 : "IIOI", "IOII", "IOIO", and "OIOI".
```
{"?II"}
```
```
Returns: 0
```
No IOI string can be formed from "?II".
```
{"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.

{"???I???????O???","???????????O??IO????????I???"}

Returns: 438952513

Don't forget to concatenate strings.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.