|Cat Taro has a triangle board divided into hexagonal cells. The board contains N rows numbered 0 through N-1 from top to bottom, where the i-th row contains (i+1) hexagonal cells numbered (i,0) through (i,i) from left to right. For example, if N = 4, the board looks like the picture below.
Each cell contains a token. Rabbit Hanako locked some cells so that tokens in those cells can't be moved. You are given a String board containing exactly N elements. For all i between 0 and N-1, inclusive, the i-th element of board will contain exactly (i+1) characters. If the j-th character of the i-th element of board is 'X', the cell (i,j) is locked. If the j-th character of the i-th element of board is '.', the cell (i,j) is unlocked.
Cat Taro can perform the following operation an arbitrary number of times: Choose three distinct unlocked cells A, B and C. These three cells must have a common vertex. Move the token in cell A to cell B, the token in cell B to cell C and the token in cell C to cell A.
Return the number of different board states he can achieve by performing operations as described above, modulo 1,000,000,007. Two states are different if there exists at least one token that is placed in a different cell in one state than it is in the other state.
|-||board will contain between 1 and 50 elements, inclusive.|
|-||The i-th (0-indexed) element of board will contain exactly i+1 characters.|
|-||Each character in board will be '.' or 'X'.|