The unicorn is an exotic chess piece similar to the knight. The difference is that while the knight moves two cells in one direction and one in the other direction, the unicorn moves more than two cells in one direction and more than one in the other direction.
More precisely, each unicorn move looks as follows:
- pick up the unicorn;
- pick one of the four basic directions, and move the unicorn more than two cells in that direction;
- pick one of the two basic directions that are orthogonal to the previous one, and move the unicorn more than one cell in that direction;
- put down the unicorn.
We have a chessboard that has R rows times C columns.
Each cell of the chessboard contains one of the first L letters of the alphabet.
To keep the input small, the content of the cells is randomly generated using the method
described below.
You are given the ints R, C, and L described above, an int seed used to generate
the letters in the cells, and a String word. You want to trace the String word by taking a unicorn, placing it onto a cell containing the
first letter of word, making a valid move that takes it onto a cell that contains the second letter, from there making another
move to the third letter, and so on.
Return the number of ways in which this can be done, modulo 1,000,000,007.
The content of the cells is generated using the following pseudocode:
x = seed;
d = (65535 div L)+1;
for (int r=0; r<R; r++)
for (int c=0; c<C; c++) {
x = (x * 25173 + 13849) modulo 65536;
chessboard[r][c] = character with ASCII code (65+(x div d));
}
|