Statistics

Problem Statement

Petya likes triangles. He draws a trianglar grid using the following process: He starts off with an equilateral triangle. He then draws points on the edges of this triangle, dividing each edge up into N equal-length segments. Next, he connects each pair of points that is at equal distance from some vertex of the triangle with a straight line, ending up with N*N smaller equilateral triangles. An example of this figure with N = 4 is shown below.

However, he likes hexagons more than he likes triangles. How many non-degenerate convex hexagons can be formed using the line segments in his figure? This number can be very big, so return it modulo 1000000007.

Definition

Class:

ConvexHexagons

Method:

find

Parameters:

int

Returns:

int

Method signature:

int find(int N)

(be sure your method is public)

Notes

• The length of each edge of every hexagon must be greater than zero.

Constraints

• N will be between 1 and 500000, inclusive.

Examples

1. 3

   Returns: 1

2. 4

   Returns: 7

   There are 7 hexagons:

3. 7

   Returns: 232

4. 104

   Returns: 635471838

5. 1

   Returns: 0

6. 8195

   Returns: 325178177

7. 330410

   Returns: 496809237

8. 213435

   Returns: 605395784

9. 15285

   Returns: 872768413

10. 218045

    Returns: 743588278

11. 123836

    Returns: 442196153

12. 359944

    Returns: 68531503

13. 437198

    Returns: 339664453

14. 236868

    Returns: 260490781

15. 76240

    Returns: 716704771

16. 473467

    Returns: 978034156

17. 62630

    Returns: 44405838

18. 154575

    Returns: 527858231

19. 124851

    Returns: 862434821

20. 53508

    Returns: 832417351

21. 330874

    Returns: 502627572

22. 251504

    Returns: 484041379

23. 465660

    Returns: 553266009

24. 426579

    Returns: 10969552

25. 482269

    Returns: 468357025

26. 143279

    Returns: 139873004

27. 121503

    Returns: 777490502

28. 305366

    Returns: 353266118

29. 447811

    Returns: 506737712

30. 197659

    Returns: 399430120

31. 370008

    Returns: 295062172

32. 147229

    Returns: 713103117

33. 235359

    Returns: 127271322

34. 434281

    Returns: 12278458

35. 86096

    Returns: 781926750

36. 85438

    Returns: 999007290

37. 179601

    Returns: 938704957

38. 243259

    Returns: 341421304

39. 178717

    Returns: 289912124

40. 331612

    Returns: 417652818

41. 47982

    Returns: 830041917

42. 383570

    Returns: 521314593

43. 426512

    Returns: 921004716

44. 72781

    Returns: 326324376

45. 119773

    Returns: 420949847

46. 347155

    Returns: 16796486

47. 142091

    Returns: 693039392

48. 11520

    Returns: 789934845

49. 480477

    Returns: 516220520

50. 299684

    Returns: 975434164

51. 219609

    Returns: 882663408

52. 322580

    Returns: 87919936

53. 398750

    Returns: 726101243

54. 433924

    Returns: 604025528

55. 245329

    Returns: 605813081

56. 424468

    Returns: 907885293

57. 278029

    Returns: 298019804

58. 196633

    Returns: 62615803

59. 475868

    Returns: 334064720

60. 89395

    Returns: 325924288

61. 300062

    Returns: 760546460

62. 474930

    Returns: 714636669

63. 113796

    Returns: 644409157

64. 40055

    Returns: 947678366

65. 2505

    Returns: 102420448

66. 453080

    Returns: 593564096

67. 435294

    Returns: 556833988

68. 306645

    Returns: 743081221

69. 157807

    Returns: 687092680

70. 475621

    Returns: 806673546

71. 449547

    Returns: 87937229

72. 242584

    Returns: 953951996

73. 445536

    Returns: 847684662

74. 377776

    Returns: 164584313

75. 394563

    Returns: 17796571

76. 222357

    Returns: 948244693

77. 35361

    Returns: 950393135

78. 369092

    Returns: 454843506

79. 499103

    Returns: 296860968

80. 169929

    Returns: 277950136

81. 322858

    Returns: 255128265

82. 181234

    Returns: 94576493

83. 65419

    Returns: 699487055

84. 191157

    Returns: 446921484

85. 185341

    Returns: 870222929

86. 315883

    Returns: 222936575

87. 52472

    Returns: 888110326

88. 208652

    Returns: 43426202

89. 249896

    Returns: 269310488

90. 353661

    Returns: 12711761

91. 464327

    Returns: 753457245

92. 122510

    Returns: 914179390

93. 290813

    Returns: 824781569

94. 410036

    Returns: 13926307

95. 473421

    Returns: 847308100

96. 145368

    Returns: 974445200

97. 498598

    Returns: 57475856

98. 449135

    Returns: 939928332

99. 333366

    Returns: 995280147

100. 85211

     Returns: 848343293

101. 487754

     Returns: 184037772

102. 291402

     Returns: 989589691

103. 261004

     Returns: 549500393

104. 474367

     Returns: 512755055

105. 35523

     Returns: 271597365

106. 500000

     Returns: 259652042

107. 1

     Returns: 0

108. 2

     Returns: 0

109. 3

     Returns: 1

110. 4

     Returns: 7

111. 5

     Returns: 29

112. 6

     Returns: 90

113. 499971

     Returns: 229659847

114. 499999

     Returns: 595702048