Statistics

Problem Statement

Fox Ciel has a board divided into X times Y square panels. Initially, all panels are unlit. Whenever Ciel presses a panel, that panel will turn on and from that moment on the panel will be lit forever.

Ciel is going to perform the following operation twice. The operation starts with Ciel choosing a subrectangle of the board. The dimensions of the subrectangle have to be sx times sy, and the side with length sx has to be parallel to the side of the board with length X. Once the subrectangle is chosen, Ciel presses some of the panels it contains (possibly none at all or all of them).

The following figures show an example of these operations for X = 5, Y = 4, sx = 3, and sy = 2. The picture on the left shows the initial board, the picture in the middle shows the board after the first operation, and the picture on the right shows the board after the second operation.



Compute and return the number of different patterns Ciel can have after finishing the two operations, modulo 1,000,000,007.

Definition

Class:

LitPanels

Method:

countPatterns

Parameters:

int, int, int, int

Returns:

int

Method signature:

int countPatterns(int X, int Y, int sx, int sy)

(be sure your method is public)

Constraints

• X will be between 1 and 40, inclusive.
• Y will be between 1 and 40, inclusive.
• sx will be between 1 and X, inclusive.
• sy will be between 1 and Y, inclusive.

Examples

1. 2

   2

   1

   1

   Returns: 11

   All patterns with at most two lit panels are possible. The number of such patterns is C(4, 0) + C(4, 1) + C(4, 2) = 11, where C denotes binomial coefficients.

2. 2

   3

   1

   2

   Returns: 40

   The following picture shows all 40 possible patterns.

3. 4

   4

   3

   2

   Returns: 14096

4. 40

   39

   5

   8

   Returns: 877713074

5. 39

   30

   19

   6

   Returns: 910646629

6. 33

   38

   18

   37

   Returns: 194248776

7. 39

   38

   5

   27

   Returns: 672204430

8. 11

   28

   3

   14

   Returns: 976102091

9. 28

   11

   11

   10

   Returns: 845166142

10. 24

    31

    20

    16

    Returns: 51434886

11. 23

    31

    11

    9

    Returns: 441644622

12. 39

    34

    16

    13

    Returns: 637898925

13. 22

    39

    20

    5

    Returns: 388324708

14. 23

    32

    6

    22

    Returns: 105718060

15. 23

    20

    4

    5

    Returns: 120935308

16. 22

    13

    20

    8

    Returns: 344015095

17. 22

    37

    13

    3

    Returns: 157424773

18. 13

    14

    1

    4

    Returns: 734722

19. 32

    20

    24

    11

    Returns: 581156206

20. 35

    24

    22

    9

    Returns: 354411196

21. 40

    35

    8

    14

    Returns: 570868936

22. 19

    40

    18

    32

    Returns: 34849280

23. 10

    27

    7

    16

    Returns: 363338153

24. 24

    33

    10

    24

    Returns: 432650652

25. 40

    40

    1

    1

    Returns: 1280801

26. 40

    40

    1

    10

    Returns: 17478937

27. 40

    40

    1

    30

    Returns: 255128517

28. 40

    40

    1

    40

    Returns: 717566518

29. 40

    40

    10

    1

    Returns: 17478937

30. 40

    40

    10

    10

    Returns: 604269258

31. 40

    40

    10

    30

    Returns: 81588147

32. 40

    40

    10

    40

    Returns: 51702122

33. 40

    40

    30

    1

    Returns: 255128517

34. 40

    40

    30

    10

    Returns: 81588147

35. 40

    40

    30

    30

    Returns: 930255495

36. 40

    40

    30

    40

    Returns: 592352867

37. 40

    40

    40

    1

    Returns: 717566518

38. 40

    40

    40

    10

    Returns: 51702122

39. 40

    40

    40

    30

    Returns: 592352867

40. 40

    40

    40

    40

    Returns: 592352867

41. 1

    1

    1

    1

    Returns: 2

42. 1

    40

    1

    10

    Returns: 66584576

43. 1

    40

    1

    30

    Returns: 511620083

44. 40

    1

    10

    1

    Returns: 66584576

45. 40

    1

    30

    1

    Returns: 511620083

46. 40

    40

    13

    13

    Returns: 464067811