Statistics

Problem Statement for "BlackBoxDiv1"

Problem Statement

Cat Upper has a rectangular black box. On the bottom of the box there is a grid that divides the box into identical square cells. There are N rows of cells, each containing M cells. There are no walls between the cells. The sides of the box are transparent.

Each cell contains a single mirror. Seen from above, the mirror is a segment that connects two opposite corners of the cell. The mirror surface is on both sides of the segment. (Note that for each cell there are two possible positions of the mirror.)

Cat Upper has a laser which can be used to cast rays. When casting a ray, the following rules must be obeyed:
  • The ray must be cast from outside of the black box.
  • The ray must enter the box exactly in the middle of a side of a cell.
  • The ray must enter the box in the direction perpendicular to the side of the box it enters through.

Once inside the box, the laser follows the laws of reflection: it travels in a straight line through open space, and it reflects whenever it hits a mirror. (Note that this means that the laser will always travel in a direction parallel to one of the sides of the box.)

The process ends when the ray exits the black box. (Note that this always has to happen, and that the ray will necessarily leave through the middle of some other cell wall.)

Cat Upper used the laser to cast a ray through each of the 2N+2M cell sides that were visible from the outside. For each cell side C, Upper recorded where the laser that entered through C exited the black box.

Afterwards, Upper removed a single mirror from the grid and repeated the entire experiment. Surprisingly, the results were completely identical to the first experiment.

Cat Upper has lost the black box and he does not remember the cell from which he removed the mirror. The only thing he remembers are the dimensions of the black box.

You are given the two ints N and M. Return the number of possible initial states of the black box, modulo 1,000,000,007.

Definition

Class:
BlackBoxDiv1
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int N, int M)
(be sure your method is public)

Constraints

  • N will be between 1 and 200, inclusive.
  • M will be between 1 and 200, inclusive.

Examples

  1. 2

    2

    Returns: 5

    There are 5 possible patterns. In the leftmost configuration Upper could remove any of the four mirrors. In each of the other four configurations, Upper can remove the mirror that does not touch the other three mirrors.

  2. 1

    1

    Returns: 0

  3. 3

    5

    Returns: 32478

  4. 194

    197

    Returns: 647560542

  5. 1

    200

    Returns: 0

  6. 200

    1

    Returns: 0

  7. 200

    200

    Returns: 137974162

  8. 16

    42

    Returns: 786980056

  9. 144

    139

    Returns: 274270453

  10. 115

    116

    Returns: 291753185

  11. 194

    175

    Returns: 962856170

  12. 96

    182

    Returns: 934932818

  13. 107

    162

    Returns: 839704822

  14. 41

    184

    Returns: 147033874

  15. 38

    191

    Returns: 92361539

  16. 94

    115

    Returns: 161477449

  17. 180

    162

    Returns: 263123427

  18. 46

    125

    Returns: 215880163

  19. 131

    26

    Returns: 658892131

  20. 104

    47

    Returns: 453883689

  21. 131

    77

    Returns: 468126505

  22. 177

    32

    Returns: 948327117

  23. 85

    30

    Returns: 721386154

  24. 77

    160

    Returns: 268888578

  25. 147

    2

    Returns: 604537113

  26. 33

    161

    Returns: 595287717

  27. 9

    139

    Returns: 703169625

  28. 126

    93

    Returns: 366338278

  29. 37

    164

    Returns: 419791043

  30. 160

    101

    Returns: 76061187

  31. 130

    189

    Returns: 590139417

  32. 189

    163

    Returns: 121702483

  33. 191

    146

    Returns: 67718337

  34. 84

    45

    Returns: 656025807

  35. 99

    169

    Returns: 633244121

  36. 6

    189

    Returns: 715824080

  37. 159

    50

    Returns: 250226581

  38. 91

    157

    Returns: 835810290

  39. 2

    122

    Returns: 600392459

  40. 82

    136

    Returns: 767074861

  41. 132

    185

    Returns: 304365292

  42. 63

    54

    Returns: 405928991

  43. 151

    24

    Returns: 92382126

  44. 68

    135

    Returns: 323797276

  45. 20

    44

    Returns: 218442994

  46. 48

    152

    Returns: 114158329

  47. 113

    116

    Returns: 867461667

  48. 97

    56

    Returns: 69299284

  49. 127

    113

    Returns: 44517943

  50. 192

    177

    Returns: 636985790

  51. 81

    187

    Returns: 140686105

  52. 54

    147

    Returns: 258123736

  53. 178

    96

    Returns: 817157123

  54. 124

    28

    Returns: 532618572

  55. 25

    53

    Returns: 713835489

  56. 9

    96

    Returns: 982266800

  57. 190

    158

    Returns: 100433629

  58. 5

    5

    Returns: 33553306

  59. 2

    200

    Returns: 201187467

  60. 3

    200

    Returns: 151414239

  61. 200

    2

    Returns: 201187467

  62. 200

    3

    Returns: 151414239

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: