TopCoder Statistics - Problem Statement

Problem Statement

Let us define an infinite table of integers as follows:

Each cell is uniquely identified by the value it contains. Let us define S(X) as the sum of all the values in the rectangle with cell 1 as its upper-left corner and cell X as its lower-right corner. For example, S(12) is the sum of all the values in the green rectangle shown above.
You are given a long N. First, find the rectangle with cell 1 as its upper-left corner and cell N as its lower-right corner. Then, calculate the sum of S(X) for all values X inside this rectangle. Return this sum modulo 1,000,000,007.
For example, if N is 8, you would first find the 3 x 2 rectangle with 1 in its upper-left corner and 8 in its lower-right corner. You would then calculate S(X) for each value X in this rectangle: S(1) = 1, S(2) = 3, S(9) = 12, S(4) = 5, S(3) = 10, and S(8) = 27. You would them sum these values to get 1 + 3 + 12 + 5 + 10 + 27 = 58.

Definition

Class:: MegaSum
Method:: calculate
Parameters:: long
Returns:: int
Method signature:: int calculate(long N)
(be sure your method is public)

Constraints

N will be between 1 and 10^10, inclusive.

Examples

8

Returns: 58

This is the example from the problem statement.
12

Returns: 282
11

Returns: 128
6

Returns: 50
34539

Returns: 437909839
72092288

Returns: 999999996
382105

Returns: 79
4863616

Returns: 32
10000000000

Returns: 832250385
1234567891

Returns: 270344636
1000000007

Returns: 912713920
2735855555

Returns: 989075999
4444444444

Returns: 465502423
8087674693

Returns: 235845444
8087674692

Returns: 63006008
8087674691

Returns: 175693749
8087674593

Returns: 746019129
8087674693

Returns: 235845444
8087584762

Returns: 788924965
8087764624

Returns: 789014897
8087764625

Returns: 491242426
8087764623

Returns: 367089643
8087584761

Returns: 174551930
8087584763

Returns: 367089643
1010101010

Returns: 369124411
1001000101

Returns: 284928151
5555555555

Returns: 530805245
6666666666

Returns: 796563719
7777777777

Returns: 492500188
8888888888

Returns: 151490215
9999999999

Returns: 496801141
1111111111

Returns: 1262560
2222222222

Returns: 977390827
3333333333

Returns: 175814602
273

Returns: 1922649
576

Returns: 30212
141

Returns: 21418
722

Returns: 1760412
744444

Returns: 105888587
42453

Returns: 649413023
3942219498

Returns: 678889441
3689426

Returns: 451875264
510

Returns: 7578914
592440

Returns: 829991811
2906131

Returns: 794073915
62399858

Returns: 669252772
64431

Returns: 498549078
445

Returns: 216208
88039581

Returns: 297793792
30133266

Returns: 32452298
54483

Returns: 307356662
386218

Returns: 877708854
69528228

Returns: 933980531
7565792

Returns: 39773876
106916018

Returns: 970172363
7314758

Returns: 617467728
261544

Returns: 214019076
13908400

Returns: 658569996
5916858

Returns: 92850932
477723511

Returns: 106296747
4013683

Returns: 566560197
521

Returns: 1203984
66046624

Returns: 719984711
553

Returns: 14447980
247791949

Returns: 446463053
454

Returns: 2238418
104593

Returns: 219521764
90716740

Returns: 75825489
73354

Returns: 329883206
49788126

Returns: 306169432
6721

Returns: 38628448
546731

Returns: 33543068
22142

Returns: 819156417
388

Returns: 1603966
587144026

Returns: 940392002
7619

Returns: 350661911
46187198

Returns: 437894642
38039

Returns: 50681021
6153

Returns: 399911467
355671422

Returns: 24706432
7347499

Returns: 851875391
7323982153

Returns: 346823628
6801120

Returns: 244136754
5940036

Returns: 74942820
2906763

Returns: 360648084
718

Returns: 3979794
44257

Returns: 350652408
87361

Returns: 260453379
4237570

Returns: 293952578
6739

Returns: 488717208
564212976

Returns: 810872914
431938175

Returns: 460809260
995326

Returns: 493707781
44725900

Returns: 46695630
517254123

Returns: 219392889
923062

Returns: 52990933
32772937

Returns: 719058259
354162624

Returns: 473052140
962

Returns: 93264
849

Returns: 2646432
7225489

Returns: 968174942
6246298

Returns: 172859769
645727395

Returns: 424155871
9338010

Returns: 846432594
175263989

Returns: 953047777
92

Returns: 67650
432595234

Returns: 28539356
3717

Returns: 17907583
2521794

Returns: 922708984
9147

Returns: 541482558
76961285

Returns: 809965922
1666358

Returns: 297713766
115782

Returns: 512667873
348465247

Returns: 21736682
58030092

Returns: 431326523
56401417

Returns: 66611556
966126390

Returns: 529256890
362502

Returns: 372697753
369453

Returns: 136222022
7756990

Returns: 969991708
715

Returns: 6443416
268825421

Returns: 413957835
52

Returns: 2822
219924

Returns: 743596489
1535984

Returns: 536833416
522269473

Returns: 404772876
9623

Returns: 561288247
38259

Returns: 794552915
577704

Returns: 179922462
4692240

Returns: 605233249
7355627

Returns: 577108636
87322548

Returns: 734621319
89

Returns: 49632
59

Returns: 12096
36555

Returns: 870276210
40

Returns: 3118
822

Returns: 16235030
936116564

Returns: 138647842
6702427

Returns: 122802592
999999999

Returns: 7293690
9999900002

Returns: 832127558
9999900001

Returns: 95642093
9999900000

Returns: 501160889
9999800003

Returns: 496801141
9999800002

Returns: 832150385
9999800001

Returns: 501133716
9999800000

Returns: 503751137
9999700004

Returns: 981139057
9999700003

Returns: 237648762
9999700002

Returns: 650072318
9999600006

Returns: 503451141
9999600005

Returns: 501133716
1

Returns: 1
2

Returns: 4
3

Returns: 19
4

Returns: 6
5

Returns: 16
7

Returns: 134
9

Returns: 16
987654321

Returns: 526013781
9999923457

Returns: 567547471
5000000000

Returns: 141947519
9234567899

Returns: 967556476
9999900071

Returns: 815135573

Statistics

Problem Statement for "MegaSum"

Problem Statement

Definition

Constraints

Examples