TopCoder Statistics - Problem Statement

Problem Statement

Fox Ciel learned a new skill of splitting! She can split into (S + L + R) foxes each time. Now she is practicing this skill on an infinite horizontal plane. At the beginning, Fox Ciel is the only fox on the plane. She stands at the point (0,0) and she is facing the point (1,0).

There will be n steps. In each step, each fox on the plane will split into exactly (S + L + R) foxes. Out of those foxes:

S will make a step forward, moving exactly one unit of distance in the direction they are facing.
L will stay in the same place and rotate 90 degrees to the left. (So for example if the original fox was facing the point (1,0), there will be L new foxes facing the point (0,1).)
R will stay in the same place and rotate 90 degrees to the right.

The score of a fox standing at the point (x,y) is x*y. Note that the score of a fox may be zero or even negative. The total score is the sum of the scores of all foxes on the plane. You are given the long n and the ints S, L, and R. Return the total score of all foxes after n steps, modulo 1,000,000,007 (10^9 + 7).

Definition

Class:: SplittingFoxes
Method:: sum
Parameters:: long, int, int, int
Returns:: int
Method signature:: int sum(long n, int S, int L, int R)
(be sure your method is public)

Notes

Note that you should return a number between 0 and 1,000,000,006, inclusive.
E.g., if the answer is -1, you should return 1,000,000,006 instead of -1.

Constraints

n will be between 1 and 10^18, inclusive.
S will be between 0 and 10^9, inclusive.
L will be between 0 and 10^9, inclusive.
R will be between 0 and 10^9, inclusive.

Examples

58

2

0

0

Returns: 0

After step 1: there are 2^1 foxes at (1, 0), After step 2: there are 2^2 foxes at (2, 0), ... After step 58: there are 2^58 foxes at (58, 0). For each fox at (58, 0), her score is 58 * 0 = 0, so the answer is 0.
3

1

1

0

Returns: 1

There will be 8 foxes at the end. The fox at (1,1) has score 1. Each of the other 7 foxes has score 0.
5

1

3

2

Returns: 34
5

1

2

3

Returns: 999999973

The answer is (-34) % 1,000,000,007.
123456789

987654321

544

544

Returns: 0

By symmetry, if L = R, then the answer will be zero.
65536

1024

512

4096

Returns: 371473914
660813542121999053

882803579

874896056

705234023

Returns: 261143543
766775761821710067

845887643

533982753

115747299

Returns: 434616057
695207666619531728

155592680

562998418

533219542

Returns: 910823973
588301871297543347

120480313

848149037

474843694

Returns: 409785381
173235083857908783

981498462

927319236

249140212

Returns: 508656847
857380839765139476

417383386

217580301

988254240

Returns: 485106363
609513282708337523

764677874

962938268

133082076

Returns: 332250277
161953961742003357

554114881

914609945

493204256

Returns: 285565352
667136952830723363

706766746

902573993

474609430

Returns: 240953424
462515461125923286

613392195

234025167

916284925

Returns: 642320004
496080614158705351

719610584

101478311

278282221

Returns: 401389536
759273103765959495

454236305

419048169

965202829

Returns: 261239500
500181948678347239

522821422

744240704

204386682

Returns: 368338074
646389296909453433

550318494

418518924

789623598

Returns: 430242943
794093457605225484

308791445

522423066

841454568

Returns: 22776853
419337366712433907

901483584

207151442

780160221

Returns: 414267778
970687994890833597

382711859

927940169

910748041

Returns: 647508165
860188996775665725

566850954

124735999

831668776

Returns: 951384959
109296038737750915

478521873

609769865

49836835

Returns: 820256309
676402505315218912

959477683

112712025

158396785

Returns: 149750098
213508806352183269

615919700

424096915

568347684

Returns: 273318714
391918472459793763

226139391

602594702

958724759

Returns: 77697937
881153627020164459

43645725

299424725

213666626

Returns: 75249250
900978599314721358

119247111

807188159

897480237

Returns: 485605562
527243772939356573

342254321

998906274

443167179

Returns: 23468093
692623640428418090

129388712

395838143

919743234

Returns: 445661806
938219539338509828

949443293

569482952

145952861

Returns: 792089845
73221043634316925

544529055

584721417

508502065

Returns: 846480425
269837182151772199

956335685

668458123

463969564

Returns: 137017087
272976770419738834

453254138

886984676

326682623

Returns: 486689195
273214971447216526

116707347

612890962

280911504

Returns: 146861830
563358447332767406

363428243

609279088

368997672

Returns: 289775761
516516384864032706

881529372

544104264

997209487

Returns: 595122841
361918364408242075

334395103

785257738

587668951

Returns: 261735014
938206012427942986

95310575

875143802

822274993

Returns: 285150257
128596380943607584

831369420

52467905

653589294

Returns: 179194023
624944182861526190

42201081

814399795

537751606

Returns: 969539916
469557750768739526

707634373

244495318

85057455

Returns: 189615445
926336066205282935

561202102

649562663

685230187

Returns: 879759804
362254017551082515

223747939

639012016

298480817

Returns: 513284413
117373482147601196

644770793

810332802

30126493

Returns: 732064058
824553956498941073

825976421

668590209

372915985

Returns: 703197359
66017712176760917

437436615

12787815

251774917

Returns: 987360148
21677663029696968

456733891

950452497

822134918

Returns: 688931367
681210238602381179

172629555

471447765

599515929

Returns: 113224660
937016307826240319

919473446

137427375

56221407

Returns: 982151672
796575486613002789

344265459

971922327

608248811

Returns: 87787498
700467958998054014

954872247

422251412

254050404

Returns: 195096117
62501611844023771

439932004

425209120

812446495

Returns: 212489391
259398081068221709

102362675

534590823

623903250

Returns: 728897556
703047274265800365

4

4

0

Returns: 533239865
513750524984834570

4

2

0

Returns: 822289733
828200077710873557

5

6

7

Returns: 211062035
799504371557728375

6

9

8

Returns: 857170286
257180145626451352

1

2

9

Returns: 271324407
237916468858348067

2

10

7

Returns: 84152263
313522628867264064

1

9

9

Returns: 0
238693049195518807

1

10

0

Returns: 69261272
162095043263814675

8

9

0

Returns: 189339896
722144401930419291

6

8

10

Returns: 886467446
33173008951284058

9

6

0

Returns: 953671638
674270380673427831

7

10

0

Returns: 637826872
114098797555375196

5

1

2

Returns: 522425771
815328412213795571

8

6

4

Returns: 734646739
435235899832500067

6

0

4

Returns: 14972067
707752708951776534

3

1

0

Returns: 119748168
91089262711427253

4

4

10

Returns: 690311385
425425984597397545

9

1

10

Returns: 833028586
134074920278833819

7

5

2

Returns: 509703182
106372394000656500

0

3

5

Returns: 0
3

656510120

180931241

498355505

Returns: 920142490
8

418411685

251372732

251082452

Returns: 844000405
7

443558903

105815372

600042535

Returns: 972152184
6

919495157

532784218

513379689

Returns: 894539033
6

324023008

22541540

357776539

Returns: 412416886
6

482155516

558041208

952259863

Returns: 755938649
4

183980741

655743494

943240702

Returns: 471568710
10

677068357

234747810

637436633

Returns: 193091390
9

401203474

572770441

430586826

Returns: 809059322
1

459723434

653757931

939033653

Returns: 0
7

316873363

31053991

280859477

Returns: 600631675
4

688812506

795350012

736664124

Returns: 383675380
5

179111968

988733400

134578803

Returns: 5393829
1

223782353

163590214

315446113

Returns: 0
8

23578770

725856499

562638443

Returns: 632213234
5

894373793

287783661

941685022

Returns: 302862426
8

355793585

314513054

273450488

Returns: 305667481
1

235889584

942147068

850379849

Returns: 0
4

906384393

371319451

307044406

Returns: 51373689
3

691613293

875884977

34008640

Returns: 423108396
1

1

5

1

Returns: 0
8

2

1

6

Returns: 999172807
3

8

5

3

Returns: 128
9

2

8

9

Returns: 853496519
10

4

2

4

Returns: 332057095
8

4

5

2

Returns: 12768768
3

8

3

4

Returns: 999999943
7

3

5

6

Returns: 999639683
6

4

0

4

Returns: 999918087
2

3

7

5

Returns: 0
5

10

7

10

Returns: 999616007
7

3

1

6

Returns: 999587267
4

8

0

9

Returns: 999981575
2

5

5

9

Returns: 0
5

1

6

1

Returns: 170
3

7

7

5

Returns: 98
8

0

3

10

Returns: 0
2

2

5

1

Returns: 0
7

8

9

5

Returns: 107728896
1

3

9

9

Returns: 0
1000000000000000000

1000000000

1000000000

1000000000

Returns: 0
1000000000000000000

999999999

999999999

1000000000

Returns: 789460183
1000000000000000000

999999234

999999123

999999453

Returns: 736114829
1000000000

1000000000

999999999

555555555

Returns: 894236504

Statistics

Problem Statement for "SplittingFoxes"

Problem Statement

Definition

Notes

Constraints

Examples