Problem Statement   Some jewels are placed in a rectangular grid on an infinite plane.
You are given String[] jewels describing the jewels.
If the jth character of the ith element of jewels is 'R', 'G' or 'B',
there is a red, green or blue jewel at the center of the jth cell of the ith 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 nondirectional.
For example, chains RGB and BGR 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)     Returns: 6  Alice can get at most two jewels.
The possible chains are: R, G, B, RG, RB, GB.


 1)     Returns: 9  Alice can get all the three jewels.


 2)     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  

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)2010, TopCoder, Inc. All rights reserved.
