Problem Statement   Manao is developing a simple 2D computer game. The screen of the game is H pixels high and W pixels wide (1 <= H, W <= 50).
Manao is currently working on the background which should be filled with N mountains (1 <= N <= 10). The mountains are numbered from 0 to N1. The contents of the screen are stored in an array of characters pix where pix[x, y] gives the contents of the pixel at column x, row y. Both indices are 0based. Columns are numbered left to right and rows are numbered bottom to top. The parts of the screen where the ith mountain is visible are denoted by digit i. Character '.' means that the corresponding pixel is not covered by any mountains.
The ith (0based index) mountain is described by its peak position (X[i], Y[i]), 0 <= X[i] < W, 0 <= Y[i] < H. In order to draw the mountains, the following pseudocode is used:
Fill all elements of pix with '.' characters.
For 0 <= i < N:
For 0 <= x < W:
For 0 <= y <= Y[i]  x  X[i]:
pix[x, y] := i + '0'
For example, consider three mountains with peaks at (1, 1), (2, 2) and (4, 1). Once these mountains are drawn on a screen with H = 3, W = 6, the resulting picture will look as follows:
..1...
.1112.
111222
Manao has recently filled the background with N mountains as described above. After that he wrote down the height of each mountain. Also, for each column he wrote down which mountains were visible at that column. You are given a int[] heights containing N elements. Element i of heights gives the height of the ith mountain in pixels (which is equal to Y[i] + 1). You are also given a String[] visibility. It contains N elements and each element is W characters long. The jth character of visibility[i] is equal to 'X' if the ith mountain was visible at column j of the screen and '' otherwise. In other words, the jth character of visibility[i] is equal 'X' if and only if at least one pixel of column j contained digit i after all mountains were drawn.
Count the number of sequences of exactly N mountains that match the information given by heights and visibility. Return this number modulo 1,000,000,009. It is guaranteed that there exists at least one such sequence.   Definition   Class:  Mountains  Method:  countPlacements  Parameters:  int[], String[]  Returns:  int  Method signature:  int countPlacements(int[] heights, String[] visibility)  (be sure your method is public) 
    Notes    The value of H is not directly given in the input parameters. For the purposes of this problem, you can assume that H is equal to the largest element of heights.   Constraints    heights will contain between 1 and 10 elements, inclusive.    Each element of heights will be between 1 and 50, inclusive.    visibility will contain the same number of elements as heights.    Each element of visibility will be between 1 and 50 characters long, inclusive.    All elements of visibility will be of the same length.    Each element of visibility will consist of 'X' and '' characters only.    At least one sequence of mountains matching the given information will exist.   Examples  0)    {2, 3, 2}  {"",
"XXXX",
"XXX"} 
 Returns: 4  The given information corresponds to the three mountains from the problem statement. Mountains 1 and 2 are uniquely determined. Mountain 0 can have the peak in each column from 1 to 4. 

 1)    {4, 3, 4}  {"XXXXX",
"XXX",
"XXXXXXX"} 
 Returns: 4  The four possible mountain sequences are:
 (2, 3), (10, 2), (7, 3)
 (2, 3), (11, 2), (7, 3)
 (3, 3), (10, 2), (7, 3)
 (3, 3), (11, 2), (7, 3)
After drawing these sequences, the following pictures are obtained:
..0....2..... ..0....2..... ...0...2..... ...0...2.....
.000..222.1.. .000..222..1. ..000.222.1.. ..000.222..1.
000002222211. 0000022222111 .00002222211. .000022222111
0000222222211 0000222222211 0000222222211 0000222222211


 2)    {13, 2, 3, 2}  {"XXXXXXXXX",
"XXX",
"XXXXX",
"XXX"} 
 Returns: 9  
 3)    {8, 2, 9, 3, 10}  {"X",
"",
"X",
"",
"XXXXXXX"} 
 Returns: 98  
 4)    {20, 20, 20, 20, 20, 20, 45, 50, 49, 50}  {"",
"",
"",
"",
"",
"",
"",
"XXXXXXX",
"XXXXXXX",
"XXXXXXXXXXXXXXXXXXX"}

 Returns: 973726691  

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.
