Limak is a big grizzly bear.
He is now going to destroy an entire forest.
Limak's forest is a rectangular grid that consists of **W** columns by **H** rows of cells.
At the beginning a single tree grows in each cell.
The forest is aligned with the major compass directions: row numbers increase towards the South and column numbers increase towards the East.
Limak will destroy the forest by pushing some of the trees.
Whenever Limak pushes a tree, the tree will fall down and remain lying both in the current cell and in the next cell in the direction in which it was pushed.
For example, if Limak pushes the tree that grows in the cell (r,c) southwards, he will obtain a toppled tree that lies in the cells (r,c) and (r+1,c).
When pushing the trees, Limak always follows a few rules:
- He only pushes trees in two directions: either southwards or eastwards.
- He will never push a tree in a way that would cause it to fall out of the forest. For example, he will never push a tree in the last column eastwards.
- He will never push a tree in a way that would produce two fallen trees lying on the same cell.
There is a single letter written on each of the trees.
Each of these letters is either S or E (representing South and East, respectively).
When pushing a tree, Limak will prefer the direction that is written on the tree.
For example, if a tree has the letter S, Limak will push it southwards if possible.
Limak is going to visit each cell in the forest exactly once, in row major order.
I.e., first he will visit all the cells in the first row from left to right, then the cells in the second row from left to right, and so on.
In each cell he will act according to the following algorithm:
- Is there a fallen tree in the current cell? If yes, there is no room here to do anything, so I'll just move to the next cell.
- Can I push the tree in the direction that is given by the letter written on the tree? If yes, I'll do so and move to the next cell.
- Can I push the tree in the other direction? If yes, I'll do so and move to the next cell.
- I'll move to the next cell without pushing the tree.
See Example 0 for a sample execution of Limak's algorithm.
You are given the ints **W**, **H**, and **MOD**.
There are 2^(**W*****H**) different forests with these dimensions.
(Different forests have different assignments of letters S and E to the trees.)
For each of these forests, compute the number of trees Limak would topple.
Return the sum of those 2^(**W*****H**) numbers, modulo **MOD**. |