TopCoder Statistics - Problem Statement

Problem Statement

A level-n simple maze consists of five squares arranged into the shape of a cross. Each square consists of n times n rooms, each having the shape of a unit square. Simple mazes of level 1 and level 3 are shown below, with each '.' representing one cell.

 .
...
 .

   ...
   ...
   ...
.........
.........
.........
   ...
   ...
   ...

In a single step you can move from your current room into any room that shares a side with your room. The distance between two rooms is the smallest number of steps needed to get from one room to the other.

You are given the long n. Consider the level-n simple maze. For each pair of rooms compute their distance. Let S be the sum of all those distances. Compute and return the value S modulo (10^9 + 7).

Definition

Class:: SimpleMazeEasy
Method:: findSum
Parameters:: long
Returns:: int
Method signature:: int findSum(long n)
(be sure your method is public)

Constraints

n will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.

Examples

1

Returns: 16

The level-1 simple maze consists of five rooms. There are four pairs of adjacent rooms (i.e., distance = 1). There are six pairs of rooms that are at distance 2. Thus, the sum of all distances is 4*1 + 6*2 = 16.
3

Returns: 4680
5

Returns: 61000
12345

Returns: 598011702

don't forget mod.
1000000000000

Returns: 763641672
1000000000000000000

Returns: 554915149
66

Returns: 628153008
430013829

Returns: 534334024
68

Returns: 592873724
14561493

Returns: 420928395
7521949216195539

Returns: 682736322
53601

Returns: 823158687
517954936

Returns: 179572644
189717349401640931

Returns: 235159525
16069892689614323

Returns: 306252769
631189381

Returns: 944669236
198721747201307

Returns: 940906601
41

Returns: 278252562
99471198180814

Returns: 166478912
3098959

Returns: 65987364
7

Returns: 329280
9567586

Returns: 351224857
4

Returns: 19904
75398296

Returns: 218998828
22368077

Returns: 167750101
33304207618616404

Returns: 126302287
72441281041

Returns: 87223761
20441774562623195

Returns: 234574084
836141540

Returns: 768290544
386804888689515616

Returns: 272743712
48522212

Returns: 989321214
6365581

Returns: 676049544
177515021252

Returns: 153940392
1483333207

Returns: 152311723
93311

Returns: 790896145
81051371

Returns: 73940737
4

Returns: 19904
466366962037226

Returns: 643063976
912519710998

Returns: 957768365
8515593382727400

Returns: 546341048
2584652203264

Returns: 375620857
4505666462392

Returns: 164181764
4

Returns: 19904
9

Returns: 1158624
687684854695598

Returns: 985660829
48

Returns: 10739165
874006492843456

Returns: 17571338
22520907890017

Returns: 805954087
6261301015171531

Returns: 109084532
5

Returns: 61000
48410208570300

Returns: 68830091
57973059015872

Returns: 936184209
6347609025362

Returns: 432522339
763940625684

Returns: 94636593
204072734326952

Returns: 593731594
45

Returns: 628718979
3175

Returns: 619182891
65204063000

Returns: 23798160
53071

Returns: 85925862
5613160155

Returns: 68420953
847852

Returns: 637892515
32247400

Returns: 899720800
38445537

Returns: 494251970
484375357

Returns: 524130368
7357741039221262

Returns: 902830376
8753565

Returns: 588315917
123

Returns: 669957529
10000000000

Returns: 947491238
999999999999999873

Returns: 220644519
123545

Returns: 371583578
100000000000000

Returns: 407467142
25

Returns: 192000000
2321321312321

Returns: 918825480

Statistics

Problem Statement for "SimpleMazeEasy"

Problem Statement

Definition

Constraints

Examples