Statistics

Problem Statement

John and Brus are interested in a new game called "Hexagon Flower". The rules are simple. You are given a flower formed by seven hexagons arranged as follows:



The objective of the game is to place a number in each hexagon of the flower such that all of the following conditions are satisfied:

• Each number is an integer between 1 and n, inclusive.
• Each number is distinct.
• For every pair of adjacent hexagons, if the numbers placed in them are a and b, then a%k != b%k.

Given n and k, return the total number of distinct solutions. Two solutions are considered the same if you can rotate one to form the other.

For example, if n = 8 and k = 4, then:



The top three placements are not valid. The other three placements are valid, but the first two among them are considered equal since one can be rotated to become the other.

Definition

Class:

TheHexagonsDivTwo

Method:

count

Parameters:

int, int

Returns:

long

Method signature:

long count(int n, int k)

(be sure your method is public)

Constraints

• n will be between 1 and 300, inclusive.
• k will be between between 1 and 9, inclusive.

Examples

1. 7

   3

   Returns: 0

   There is no way to place all 7 numbers (1 through 7, inclusive) such that no two adjacent numbers are equal modulo 3.

2. 8

   3

   Returns: 24

3. 8

   4

   Returns: 256

4. 20

   5

   Returns: 4692480

5. 8

   4

   Returns: 256

6. 160

   8

   Returns: 74141923072000

7. 9

   3

   Returns: 108

8. 38

   7

   Returns: 1801108000

9. 64

   5

   Returns: 27633171072

10. 173

    3

    Returns: 1907993842944

11. 186

    5

    Returns: 55929426172416

12. 50

    5

    Returns: 4616640000

13. 117

    7

    Returns: 5994639486720

14. 46

    7

    Returns: 7316362080

15. 264

    5

    Returns: 663258338775552

16. 118

    8

    Returns: 8562415251600

17. 80

    8

    Returns: 538125504000

18. 97

    3

    Returns: 30525665280

19. 252

    6

    Returns: 899808018036480

20. 205

    6

    Returns: 209689196945280

21. 82

    3

    Returns: 9084020400

22. 215

    7

    Returns: 444914804935800

23. 223

    9

    Returns: 962487983541000

24. 40

    9

    Returns: 4445530880

25. 142

    6

    Returns: 15603607264128

26. 57

    6

    Returns: 22753689264

27. 267

    6

    Returns: 1352198336735664

28. 230

    8

    Returns: 961002687608096

29. 38

    6

    Returns: 1175336736

30. 110

    8

    Returns: 5199317841536

31. 162

    4

    Returns: 7144096627200

32. 164

    4

    Returns: 7796343520000

33. 242

    9

    Returns: 1713009478364352

34. 261

    4

    Returns: 208847732870400

35. 110

    8

    Returns: 5199317841536

36. 168

    9

    Returns: 130335990502392

37. 17

    6

    Returns: 2484240

38. 136

    8

    Returns: 23465149879360

39. 26

    6

    Returns: 68405760

40. 119

    7

    Returns: 6769429520840

41. 222

    8

    Returns: 748699263516960

42. 84

    7

    Returns: 566290448640

43. 85

    9

    Returns: 1032282686880

44. 176

    3

    Returns: 2155943565240

45. 197

    6

    Returns: 158296535168640

46. 23

    5

    Returns: 13613200

47. 271

    6

    Returns: 1501728292287000

48. 22

    8

    Returns: 40012560

49. 28

    4

    Returns: 19904976

50. 144

    6

    Returns: 17242028236800

51. 261

    4

    Returns: 208847732870400

52. 139

    4

    Returns: 2406813472700

53. 84

    5

    Returns: 195614065920

54. 191

    8

    Returns: 259083702501120

55. 212

    9

    Returns: 673582715642896

56. 95

    4

    Returns: 158915324160

57. 195

    5

    Returns: 78136749760680

58. 235

    7

    Returns: 833169954320352

59. 39

    5

    Returns: 741683712

60. 190

    7

    Returns: 185925983724720

61. 224

    5

    Returns: 208063705449600

62. 141

    9

    Returns: 37730049745500

63. 127

    4

    Returns: 1265494495232

64. 189

    7

    Returns: 179169660115740

65. 148

    9

    Returns: 53166201518336

66. 23

    7

    Returns: 41462280

67. 86

    5

    Returns: 231558378496

68. 115

    7

    Returns: 5302089263360

69. 156

    5

    Returns: 16097292542160

70. 43

    6

    Returns: 2928516360

71. 22

    9

    Returns: 49752896

72. 44

    7

    Returns: 5297010120

73. 120

    5

    Returns: 2499242618880

74. 42

    8

    Returns: 5098564800

75. 163

    8

    Returns: 84484026268400

76. 265

    7

    Returns: 1943389640301760

77. 264

    6

    Returns: 1248975338265600

78. 153

    6

    Returns: 26475704070000

79. 74

    5

    Returns: 78716786400

80. 56

    4

    Returns: 3487294720

81. 149

    8

    Returns: 44749365605568

82. 252

    5

    Returns: 477715248825000

83. 116

    9

    Returns: 9461816844480

84. 230

    6

    Returns: 472346443546912

85. 39

    4

    Returns: 241639200

86. 177

    9

    Returns: 188464054951404

87. 238

    9

    Returns: 1522775541512576

88. 48

    8

    Returns: 13607032320

89. 29

    7

    Returns: 243528000

90. 26

    6

    Returns: 68405760

91. 98

    9

    Returns: 2853209078720

92. 26

    5

    Returns: 35315200

93. 88

    3

    Returns: 15131944800

94. 266

    3

    Returns: 40237960139520

95. 74

    6

    Returns: 149540720640

96. 10

    3

    Returns: 336

97. 92

    5

    Returns: 375103450152

98. 131

    6

    Returns: 8808833880000

99. 216

    9

    Returns: 768927624192000

100. 126

     9

     Returns: 17024821793280

101. 20

     4

     Returns: 1432000

102. 124

     4

     Returns: 1067649858000

103. 11

     4

     Returns: 7740

104. 49

     3

     Returns: 210201600

105. 275

     8

     Returns: 3384739143529180

106. 8

     9

     Returns: 6720

107. 7

     8

     Returns: 840

108. 7

     4

     Returns: 32

109. 300

     9

     Returns: 7775708550920640

110. 299

     9

     Returns: 7595552680374120

111. 300

     5

     Returns: 1633117602240000

112. 257

     8

     Returns: 2101432964771840

113. 300

     7

     Returns: 4655560757609160