Problem Statement
题目简述
定义一个由数字组成的斜边在最下面一行的等腰直角三角形为*山*，
*高度* 为*山* 的行数，
*山峰* 为*山* 最上面一行的那一个字符，
*位置* 为*山峰* 所在的列（从0开始编号）
。例如这是一座*高度* 为3、*位置* 为2的*山*：
..0...
.000..
00000.
现在有一个宽度为W(1 <= W <= 50)、高度足够高的屏幕，
在上面依次画N(1 <= N <= 10)座*山*（第i座的数字是i-1），
**后画的会覆盖掉先画的**，像这样：
..0...
20001.
220111
现在给出N座*山* 的*高度*，
给出每一列包含且只包含哪几种数字（即每座*山* 在且仅在哪几列可见），
求满足要求的每座*山* 的*位置*(0 <= *位置* < W)的安排方案数模1,000,000,009的余数。
保证至少有一种合法方案。
Manao is developing a simple 2-D 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 N-1. 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 0-based. Columns are numbered left to right and rows are numbered bottom to top. The parts of the screen where the i-th mountain is visible are denoted by digit i. Character '.' means that the corresponding pixel is not covered by any mountains.
The i-th (0-based 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 i-th 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 j-th character of visibility[i] is equal to 'X' if the i-th mountain was visible at column j of the screen and '-' otherwise. In other words, the j-th 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.