Problem Statement
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
Definition
- Class:
- BearDestroys
- Method:
- sumUp
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int sumUp(int W, int H, int MOD)
- (be sure your method is public)
Constraints
- W will be between 1 and 30, inclusive.
- H will be between 1 and 13, inclusive.
- MOD will be between 3 and 10^9, inclusive.
- MOD will be prime.
Examples
4
3
999999937
Returns: 24064
There are 2^(4*3) = 2^12 = 4096 different forests with W=4 columns and H=3 rows. One of those forests looks as follows: SEEE ESSS EESS When destroying this forest, Limak will push five trees. In the scheme below, the final locations of the toppled trees are shown using the numbers 1 through 5. The trees are numbered in the order in which Limak pushed them. The two cells that do not contain a fallen tree at the end are denoted by underscores. 1223 1453 _45_ It can be shown that for these dimensions there are exactly 512 forests in which Limak would topple exactly 5 trees. In each of the remaining (4096-512) forests Limak would topple 6 trees. Thus, the return value is 512 * 5 + (4096-512) * 6.
3
4
999999937
Returns: 24576
For these dimensions of the forest Limak will always topple exactly 6 trees. The return value is 6 * 2^12.
20
2
584794877
Returns: 190795689
For these dimensions of the forest Limak will always topple exactly 20 trees. The return value is (20 * 2^40) modulo MOD.
10
5
3
Returns: 1
1
1
19
Returns: 0
30
13
312880987
Returns: 107607437
1
1
71876209
Returns: 0
1
2
483128897
Returns: 4
1
3
442951021
Returns: 8
1
4
366999047
Returns: 32
1
5
3
Returns: 1
2
1
643643149
Returns: 4
2
2
291474539
Returns: 32
2
3
633529777
Returns: 192
2
4
7
Returns: 2
2
5
108313867
Returns: 5120
3
1
975807823
Returns: 8
3
2
232315729
Returns: 192
3
3
11
Returns: 2
3
4
253520207
Returns: 24576
3
5
781548307
Returns: 229376
4
1
73185317
Returns: 32
4
2
257580319
Returns: 1024
4
3
908346931
Returns: 24064
4
4
110648963
Returns: 522240
4
5
748527467
Returns: 10354688
5
1
496986739
Returns: 64
5
2
836042177
Returns: 5120
5
3
11
Returns: 4
5
4
3
Returns: 1
5
5
13
Returns: 11
1
13
13
Returns: 12
30
1
246931759
Returns: 55563025
2
13
543491279
Returns: 328923953
30
2
431566237
Returns: 186599373
21
1
932041361
Returns: 20971520
11
13
5
Returns: 3
4
4
338057281
Returns: 522240
11
1
673227689
Returns: 10240
21
9
519275041
Returns: 71604848
5
6
204635693
Returns: 61181514
5
7
291198361
Returns: 262838451
12
11
754290517
Returns: 52038692
27
1
153692323
Returns: 54214911
17
13
89654479
Returns: 79471581
10
9
703497889
Returns: 53361980
10
10
759804347
Returns: 147096858
10
11
342529669
Returns: 151925764
10
12
945707647
Returns: 562232074
10
13
476882267
Returns: 212057217
13
13
226092029
Returns: 180163014
30
13
521517259
Returns: 129321867
30
12
18861637
Returns: 5058191
30
11
5
Returns: 3
30
10
62988109
Returns: 9275484
30
9
763736669
Returns: 41126138
29
13
615400307
Returns: 133029240
29
12
863998307
Returns: 540327057
29
11
11
Returns: 10
29
10
623550203
Returns: 228218036
29
9
130471169
Returns: 113841063
28
13
747432841
Returns: 190852227
28
12
668902831
Returns: 9320986
28
11
857873893
Returns: 169809024
28
10
10639481
Returns: 5266453
28
9
121972309
Returns: 67200524
27
13
219726329
Returns: 119714882
27
12
3
Returns: 1
27
11
366586403
Returns: 294794250
27
10
226377817
Returns: 105929559
27
9
97837079
Returns: 15574588
26
13
684074123
Returns: 320952243
26
12
749850341
Returns: 741870057
26
11
86944129
Returns: 6994280
26
10
501500617
Returns: 44830198
26
9
878048231
Returns: 661637042
30
13
515499977
Returns: 342536444
30
13
406274287
Returns: 144992906
30
13
3
Returns: 0