Problem Statement

Some jewels are placed in a rectangular grid on an infinite plane. You are given String[] jewels describing the jewels. If the j-th character of the i-th element of jewels is 'R', 'G' or 'B', there is a red, green or blue jewel at the center of the j-th cell of the i-th row of the grid, respectively. Jewels of the same color cannot be distinguished.

Alice draws two squares on this plane. Their sides must be parallel to the axis and have length k. She is allowed to draw squares so that some part of them are on the outside of the grid. Then she will get the jewels which lie in the inside of at least one of the two squares. Note that the inside of a square does not contain its boundary. She wants to make a chain of jewels, using some of the jewels she will get. She does not have to use all of the jewels she will get. A chain is a row of one or more jewels. Chains are non-directional. For example, chains R-G-B and B-G-R are considered equal. How many different chains are possible, considering all the chains from all possible square locations? Return the answer modulo 1,000,000,009.

Definition

 Class: ColorfulJewelry Method: getChains Parameters: String[], int Returns: int Method signature: int getChains(String[] jewels, int k) (be sure your method is public)

Notes

-For the purposes of this problem, a jewel is considered to be a single point.

Constraints

-jewels will contain between 1 and 44 elements, inclusive.
-Each element of jewels will contain the same number of characters.
-Each element of jewels will contain between 1 and 44 characters, inclusive.
-Each character in jewels will be either 'R', 'G' or 'B'.
-k will be between 1 and 44, inclusive.

Examples

0)

 ```{ "RGB" } ``` `1`
`Returns: 6`
 Alice can get at most two jewels. The possible chains are: R, G, B, R-G, R-B, G-B.
1)

 ```{ "RGB" } ``` `2`
`Returns: 9`
 Alice can get all the three jewels.
2)

 ```{ "RGB" } ``` `10`
`Returns: 9`
3)

 ```{ "RRRRR", "RGGRR", "RGGGG", "RRRGG" } ``` `2`
`Returns: 280`
4)

 ```{ "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR", "RRRRRRRRRR" } ``` `6`
`Returns: 68`
5)

 ```{ "RRRGGGGG", "RRRGGGGG", "RRRGGBBB", "GGGGGBBB", "GGGGGBBB" } ``` `4`
`Returns: 613435159`

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14287&pm=11061

lyrically

Testers:

SnapDragon , Rustyoldman , marek.cygan , timmac , ivan_metelsky , Egor

Math