Statistics

Problem Statement for "CandyBowlGame"

Problem Statement

The candy game is played with N bowls of candies. The bowls are arranged in a row and numbered from 0 to N-1 sequentially.

The game is played by two players who take alternating turns. The player unable to take a valid turn loses the game. Each turn, the current player has two options:

  • Select a bowl that currently contains at least two candies. Eat exactly two of those candies.
  • Select an odd number k. Select a bowl x >= k that currently contains at least k candies. Take exactly k candies from bowl x and place them into bowl (x-k).

(For example, suppose you select the odd number k = 3. If bowl 10 contains 100 candies, you may select x = 10. You will then take the k = 3 candies from bowl x = 10, leaving 97 candies there, and you will add those three candies to whatever is in bowl x-k = 7.)


You are given the initial distribution of some candies: the int[] C with N elements such that for each i, bowl i contains C[i] candies.

You are also given E extra candies that have to be added to the bowls. (You must add each of the E candies to one of the bowls.)


A distribution of candies is winning if the player who starts the game has a winning strategy - i.e., a strategy such that the starting player following that strategy is guaranteed to win the game, regardless of what their opponent does.


Consider all different candy distributions that can be obtained by starting with the distribution C and then adding the E extra candies. Among them, count all winning ones. Return their count modulo 10^9 + 7.

Definition

Class:
CandyBowlGame
Method:
win
Parameters:
int[], int
Returns:
int
Method signature:
int win(int[] C, int E)
(be sure your method is public)

Notes

  • Candies are indistinguishable. Hence, different distributions of candies into bowls are simply different N-tuples of non-negative integers.

Constraints

  • C will have between 1 and 100 elements, inclusive.
  • Each element of C will be between 0 and 10^9, inclusive.
  • E will be between 0 and 10^6, inclusive.

Examples

  1. {4}

    3

    Returns: 1

    The position in which the only bowl (bowl 0) contains 7 candies is winning. This is because the only valid move is to eat two candies. After the first, second, and first player again do so, the bowl will have only one candy left, and at that point the second player will lose the game as there are no valid moves left.

  2. {0, 0, 0, 0, 0, 0, 1}

    0

    Returns: 0

    The position described by this C is losing. The only valid move is to take the only candy and move it one bowl to the left. Eventually, the second player will move the candy into bowl 0 and then the first player will lose.

  3. {0, 0, 0, 0, 0, 5, 0}

    0

    Returns: 1

    The first player has a winning move: they can start by moving all five candies to bowl 0. Then the second player is forced to eat two of them, the first player eats another two, and then the second player loses the game (with one candy left in bowl 0).

  4. {1, 0, 0}

    2

    Returns: 4

    In this input we are asked to consider the following six configurations: {3, 0, 0}, {2, 1, 0}, {2, 0, 1}, {1, 2, 0}, {1, 1, 1}, and {1, 0, 2}. Four of them are winning, two are losing.

  5. {0, 0, 0}

    0

    Returns: 0

    The first player loses the game immediately.

  6. {1, 2, 3}

    4

    Returns: 9

  7. {461908963}

    65562

    Returns: 0

  8. {612881716, 368797829}

    475708

    Returns: 237855

  9. {415062492, 421352827, 660953937}

    537336

    Returns: 183031057

  10. {449395963, 707195153, 25404580, 110011131}

    833704

    Returns: 315897017

  11. {850666235, 517063356, 777236130, 587001530, 9809442}

    276621

    Returns: 859777051

  12. {459238762, 247011036, 255273357, 561856451, 551852547, 385561480}

    595138

    Returns: 901529818

  13. {35717065, 602310784, 401759007, 769585354, 738306335, 379516815, 645292643}

    253806

    Returns: 802652434

  14. {617512215, 818082095, 210435486, 256215401, 846762737, 902613028, 782917677, 982424200}

    584885

    Returns: 410938952

  15. {358552528, 105169864, 389595010, 621000790, 411864481, 545789166, 579958392, 872936870, 271479000}

    131595

    Returns: 218329567

  16. {936243973, 946086475, 243694079, 995373586, 750769163, 907983561, 359552046, 234670474, 505764849, 799056097}

    680324

    Returns: 625360228

  17. {447385546, 649243544, 379083493, 724619612, 936679871, 307431950, 943979838, 829933621, 869690042, 256605994, 868778923, 596212365, 989998540, 280879785, 383264903}

    810627

    Returns: 982140643

  18. {43067572, 519633099, 335229332, 604235495, 837158197, 424641141, 279434604, 784058147, 557700496, 858579682, 237229314, 651057817, 122337491, 673673332, 903481341, 222357206, 407879373, 521192987, 271805617, 648024763, 994029812, 599194165, 160204725, 476619356, 16310367, 182853533, 587328861, 673404583, 863645037, 817622289, 88879941, 80106251, 285346811, 548934239, 872583032, 668418986, 587191332, 511648895, 840026799, 861002056, 467735815, 392537040, 986210305, 815161857, 35628518, 652610126, 284556008, 965501521, 691803009, 653516178, 555088476, 723820366, 976562440, 506602156, 981853232, 760408746, 685395201, 857357003, 338221218, 890700442, 23872914, 619463997, 260940257, 226951148, 371476397, 463467161, 930735750, 742802513, 197585684}

    592847

    Returns: 237045610

  19. {988878479, 213327221, 137306116, 105675226, 146737412, 784281966, 842998321, 611626153, 369426272, 566292666, 421294032, 116055547, 286544298, 476656188, 485223, 700751158, 131400022, 444604326, 72117357, 396477633, 22249658, 283733899, 44780631}

    492613

    Returns: 777135398

  20. {793651122, 549388645, 897188377, 527189263, 215981477, 840829695, 829866348, 871544936, 531174522, 567230838, 487039672, 605166843, 609173462, 10723827, 746288199, 79290910, 188036108, 897404346}

    189980

    Returns: 403138453

  21. {583518861, 363292614, 682389688, 931030468, 50128420, 942251502, 667919250, 251793813, 764765051, 65750734, 406657323, 132229151, 23852118, 95121428, 325052044, 57866117, 944087158, 588255571, 330353341, 256750958}

    966637

    Returns: 222850159

  22. {788143801, 574330895, 162354904, 590480970, 622510786, 818650486, 293303963, 664632564, 921594081, 612929097, 86654360, 604472707, 527479943, 367988208, 597560671, 56030499, 123045707, 443968465, 448443766, 379828288, 973463063, 325142223, 605934918, 906551299, 815748422, 525333703, 641733357, 149950278, 68221557, 545326953, 125699083, 969905990, 495279163, 701102584, 844881430, 487227965, 884403724, 19196099, 466629860, 869380778, 605515027, 560627570, 819709817, 71072587, 839253913, 847423726, 308839297, 841539667, 756726466, 526350671, 539442012, 122544572, 810623578, 263195265, 378160092, 854968508, 355526281, 179226442, 496671190, 24260175, 631062846, 105426212, 720412488, 493352292, 494488687, 297197665, 685081509, 585103878, 736604806, 746550455, 739996155, 986463310, 25537871, 601508804, 203243637, 884873256, 729714784, 308222626, 43901203}

    940028

    Returns: 852474495

  23. {582239740, 518276962, 411998379, 73514838, 775694911, 843957081, 117075129, 944031161, 559272524, 761348627, 633503745, 643082351, 512516892, 576767593, 799221060, 849100512, 388654383, 621118347, 334682124, 442484489, 826768666, 733157853, 962200196, 964545183, 219977310, 786368716, 679160796, 98188879, 110252490, 550176498, 868789569, 327488403, 434950847, 357293695, 578737879, 897908491, 386678572, 913854417, 116822057, 876386673, 100051728, 917869312, 668324192, 798837166, 457550043, 387115369, 53950146, 375574708, 625812828, 928943728, 60640904, 993976201, 420753700, 680685373, 866619587, 287670031, 273090581, 226141678, 311090680, 224634685, 499291494, 913802966, 710090537, 881514056, 878068838, 321600643, 478078314, 832904610, 472931687, 340861581, 928574706, 724232338, 58810011, 166727022, 623077931, 515073838, 660746, 29553320, 453916726, 930045747, 491132366, 558585770, 470167904, 659341082, 874709996, 923298130, 276727007, 315638992, 110066395, 325424349, 132981064, 182265406, 454286950, 361481930, 534217596, 457410644, 251800944, 540473952, 612320496}

    276049

    Returns: 731149359

  24. {336070116, 595702143, 24768466, 986216349, 653790074, 722703644, 937805117, 407292477, 918944507, 981459236, 638457511, 632758912, 748166164, 638705883, 740721136, 670024913, 985149561, 495881981, 662478751, 599484617, 192736949, 732861406, 753657890, 404816052, 874553094, 45952094, 195028227, 658188387, 997624442, 194843137, 669887201, 83679517, 520715735, 441328632, 64715109, 240968959, 495771283, 188882615, 999267553, 642031201, 427234463, 4793407, 670493112, 149346959, 798054733, 78153605, 601501271, 417806775, 810169, 412713771, 536148941, 796563254, 488685466, 676216947, 400720810, 784501784, 131516507, 548947955, 430015013, 109637006, 92381310, 847718052, 451283482, 442330296, 955753427, 591098775}

    275881

    Returns: 110373533

  25. {662807300, 187723307, 970209759, 714165864, 535330823, 510886848, 471638318, 640306370, 889758904, 100636318, 424668443, 563196276, 542924252, 351539983}

    893297

    Returns: 905617978

  26. {980750910, 211144144, 339716496, 426400948, 910274885, 80090326, 142284813, 765291445, 523577852, 357621016, 697865346, 697184247, 112574389, 271115611, 521260085, 849335196, 99546047, 383493614, 31925668, 423641319, 670770887, 87319693, 645911309, 240774617, 553833415, 691563364, 226325723, 545243635, 276680942, 765865031, 921223553, 820193932, 329181419, 536941528, 650205373, 122125671, 980661601, 603609901, 67053696, 308060349, 772702299, 190339681, 524279703, 746861204, 259106281, 434185122, 655650968, 509022207, 7600386, 632549435, 937244480, 429046081, 653966169, 252599354, 671430481, 595262024}

    785311

    Returns: 553781975

  27. {845548682, 114584279, 362763678, 69033214, 168657967, 633379555, 113697937, 256607956, 906858947, 929270383, 196738984, 85869072, 152165059, 552954730, 180549570, 771786201, 177607406, 82929219, 99524446, 135237798, 632552639, 422823419, 925852342, 373997695, 130776087, 445245040, 316619487, 589756569, 687771007, 235734230, 729166753, 985501755, 372498812, 825313015, 96744363, 688723784, 337321499, 109430393, 38425210, 216705223, 870864911, 600314219, 145461625, 354557570, 97596117, 895195765, 342876693, 825430080}

    840079

    Returns: 457930715

  28. {983564784, 460599972, 543549149, 586221488, 614802102, 808423217, 826572987, 730206253, 967125742, 378121270, 856303625, 559767407, 557787926, 456876900, 684887938, 471503640, 468195242, 726055962, 443577392, 781439377, 526842172, 24347361, 209179998, 350506113, 52690485, 643888823, 460126676, 967702369, 108567928, 471473318, 830378227, 625779005, 133179045, 103394234, 909045810, 359343819, 469391980, 793256113, 978451960, 63364009, 358312655, 845870445, 810271073, 201299071, 981305305, 873194536, 718205950, 438917892, 503374292, 796111176, 981912402, 994070996, 556148090, 510014715, 743845156, 554500238, 128335516, 990286838, 246358736, 213253709, 673613713, 28325499, 579735865, 529972178, 349194489, 988023003, 152479609, 725197699, 175900271, 831185720, 310391575, 77943946, 50425260, 801636735, 899480440, 971454460, 649218198, 320727332, 47475366, 689268659, 662912312, 915562149, 718682183, 6766887, 275073122, 370083199, 969893482, 206399912, 596475437, 230917733, 396613518, 968584733}

    695619

    Returns: 330286424

  29. {217322534, 480391204, 661634889, 37085384, 855177131, 796389967, 873907333, 323850329, 647074276, 718894194, 321677090, 452878615, 118965929, 453793776, 905792744, 449159156, 373129315, 812593217, 534486857, 275762577, 48742449, 777448046, 606607706, 774963800, 740287894, 979135681, 526985908, 246665392, 290525281, 435434484, 62786847, 937032331, 25771035, 422104353, 204805745, 822084014, 448078214, 393888244, 558562208, 95257110, 370603160, 775849257, 931345903, 670691068, 951449378, 673872987, 364001622, 473746333}

    140100

    Returns: 331628433

  30. {70281718, 508055586, 286480490, 69102455, 174227103, 219823444, 244202171, 997385309, 453224676}

    923963

    Returns: 235681336

  31. {212013153, 318593834, 6376815, 122607088, 649091097, 606036483, 874630388, 12738098, 269623223, 572736011, 228705735, 571556809, 400151437, 505743508, 984038052, 230058198, 356936916, 429995144, 978506403, 41161877, 722638555, 694139976, 629723229, 445302559, 349449636, 870743927, 863679939, 577243635, 370145438, 961133610, 8033522, 117346907, 22072732, 333903229, 850137163, 52171598, 653879906, 234799331, 883625231, 881753329, 906758648, 562896777, 928195198, 657037158, 3608569, 37488411, 936164376, 595556493, 631512666, 52890094, 411722031, 958920515, 819342377, 498256618, 205051663, 96393176, 297700924, 724900465, 998965079, 682705091, 952571937}

    831854

    Returns: 17677899

  32. {373515540, 40598036, 952049656, 70079751, 326462496, 645788154, 766988591, 334136497, 55868363, 655206220, 984408050, 474324241, 497583523, 436763796, 782245860, 773450369, 357142261, 772540577, 96563432, 271881319, 915834028, 957372742, 451425244, 401042095, 105467295, 760537921, 405221552, 405306409, 189430592, 317497028, 31989628, 32726129, 617521430, 726017513, 619324219, 871948755, 951735767, 205501001, 135272466, 602537865, 239233694, 92667707, 8177953, 454128574, 459168224, 446959522, 759229787, 454231929, 620958489, 787641000, 136988490}

    534998

    Returns: 747961996

  33. {774867576, 794438709, 796228454, 914960509, 403416923, 578629390, 688684551, 973483087, 494006315, 282008119, 687581714, 886033331, 688680143, 158444827, 80619762, 42543234, 633350052, 259280604, 873094826, 784896455}

    810712

    Returns: 755801172

  34. {75703654, 974654823, 18824810, 147075427, 131683492, 556736524, 837370284, 136669034, 657283461, 917253376, 313656809, 611977490, 647129739, 945353533, 449164981, 587730180, 800411910, 524059221, 657631083, 916829793, 623784894, 934807899, 25189944, 179749843, 839551594, 864246081, 641872477, 581930457, 620904646, 884453279, 680032466, 777589859, 156614937, 998550953, 248279256, 911137234, 125931884, 162686522, 961925421, 975155805, 306166691, 662212723, 520043731, 963663275, 866417028, 698359883, 526189448, 494591081, 884868198, 916902058, 649637067, 332016440, 439933264, 809428128, 994217734, 482871342, 650222602, 197011876, 13736714, 459504530, 868217808, 846173433, 936515003, 523293685, 525742634, 786028983, 438127919, 368811557, 402588821, 596705226, 324151370, 858690323, 963513038, 329960449, 423562100, 893557231}

    134497

    Returns: 187209804

  35. {669734590, 819272128, 565159598, 288540651, 152087734, 501831491, 421315870, 108815604, 897479257, 947036521, 827960312, 708141539, 115582222, 636528825, 36450493, 394889797, 685588141, 881244446, 956590930, 365287554, 712797109, 727704974, 613878494, 806797731, 158368945, 1176794, 279584623, 377143495, 171791451, 666574063, 922606452, 42708358, 855656830, 864537452, 442722984, 516391627, 770084348, 347333594, 158396353, 285257142, 275044379, 355156688, 438888331, 705675087, 119762142, 220653916, 968931231, 718317149, 189624752}

    37283

    Returns: 579357229

  36. {247513706, 989801274, 302963301, 713258932, 263814769, 494629645, 746759329, 822514784, 566678279, 366068895, 992101254, 167581775, 566868632, 387564734, 119742495, 962856223, 157283768, 989045509, 190822315, 606252558, 993325837, 244278498, 579712236, 907283297, 613552593, 841249330, 566383529, 892819224, 833095611, 344020031, 685975529, 849986754, 686313605, 581779980, 221132852, 849113146, 683837376, 267547179, 43809681, 392440295, 408431882, 963287787, 809727134, 184616433, 526358251, 653678607, 787348666, 967600908, 779413611, 182842244, 994013394, 937637265, 207557984, 432322630, 864005185, 781877102, 718940260, 57626284, 503487331, 350884231, 589017924, 980174540, 579282471, 80153798, 277949393, 102260530, 148720048, 912658136, 718362960, 882190772, 553349042, 802872130, 622248951, 717226780, 223613532, 293876822, 641316024, 418215816, 933805530, 119174041}

    921924

    Returns: 664853062

  37. {384081635, 128444743, 403558184, 399695759, 697295741, 572360428, 241576536, 312392336, 269443404, 653481056, 726880979, 750581442, 698581538, 344474778, 611678993, 41154509, 815750640, 663889712, 222756080, 318072459, 478939336, 829775835, 991922159, 936906407, 349184565, 809825375, 122641025, 157041994, 635679035, 196573588, 947041530, 938912378, 976371215}

    579760

    Returns: 832346836

  38. {294194531, 101654213, 316286622, 223339634, 40658558, 821755213, 954402002, 290500609, 658397254, 698614578, 233064740, 212982245, 733317428, 528654651, 531718764, 83152377, 409898425, 696906123, 24998314, 702657256, 823531873, 636544414, 160956422, 114275360, 952796041, 450237810, 323193706, 992703435, 236574870, 915831654, 444578740, 806490794, 203786101, 92510152}

    359711

    Returns: 5109157

  39. {681085407, 940417590, 713507814, 239991166, 588454245, 95860451, 596522359, 450200886, 331842645, 338618884, 401479246, 979071747, 127501683, 97788329, 743163565, 337440621, 488128802, 227480666, 826273789, 126126158, 701456661, 93030635, 575331082, 713303747, 365784802, 816072996, 608460821, 739756130}

    673523

    Returns: 569965678

  40. {235075023, 63742419, 342489325, 331150913, 850123877, 784629986, 790922388, 716341955, 848863661, 406938846, 284356842, 822699844, 635553317, 63742693, 81519488, 274942463, 490941911, 541236526, 236499458, 550743712, 548748657, 521132927, 304290805, 342001492, 468604458, 554339969, 267144960, 654921847, 730521679, 914819766, 754201962, 689727791, 944156014, 352830663, 612460484, 680788928, 225195979, 934987889, 613720295, 886058949, 190555653, 203371246, 256920389, 809231904, 44568548, 31547554, 746135704, 652946826, 914027476, 547139920, 923729020, 965378732, 872448897, 650364372, 279749952, 790175292, 653975627, 316428352, 963039859, 213199019, 368616926, 635579721}

    833562

    Returns: 23072262

  41. {946956585, 600446388, 361553583, 541555155, 186630427, 802433616, 833335012, 910847218, 351951338, 400184362, 198432453, 168785931, 709487332, 780723745, 529817935, 81103305, 37782502, 419704490, 498449467, 998257389, 745713324, 483244203, 315973312, 667432712, 100871023, 848584236, 686573551, 747489348, 528621849, 869734475, 673666890, 921814483, 290424728, 358398435, 303088382, 746571563, 232994097, 880548956, 886913146, 973068819, 750897152, 912785633, 869474303, 459009036, 81042950, 274266982, 657022710, 410764214, 347421594, 493608953, 313460938, 172951437, 259903771, 195834966, 389412330, 247206990, 991686712, 331775805, 38944609, 232566755, 741275615, 617018256, 508593434, 26472005, 381771396, 9910859, 676832086, 305358809, 294035915, 593660090, 446459598, 813523104, 568643729, 990234015, 253476460, 487591577, 487750166, 56806493}

    660543

    Returns: 94660084

  42. {139726159, 788165983, 432071304, 475924931, 200996813, 266158026, 49291936, 431349811, 722308395, 485499074, 571418087}

    756051

    Returns: 900668532

  43. {599028848, 28449513, 584674225, 481412041, 580321032, 521291716, 903430148, 632355596, 173139741, 170221973, 846112932, 813288469, 255961014, 295934998, 720985359, 341992746, 207943922, 598352957, 725053471, 914937551, 529434123, 546151788, 859939374, 797334874, 295000238, 493684037, 274214649, 361862050, 563823125, 125120813, 237141678, 817268918, 272982210, 842355480, 242659281, 35096959, 839243618, 148065548, 262571502, 739774042, 791261077, 945579725, 993876805, 765183967, 480929297, 790133105, 766905041, 934188350, 834583515, 91022361, 348018470, 782066372, 588010765, 792594064, 693919126, 703996019, 231993629, 347371571, 672987830, 101020612, 850625276, 279436854, 556755568, 168658123, 298489061, 387453591, 149811813, 803695838}

    104559

    Returns: 365755307

  44. {936060168, 197845379, 873253679, 59908794, 915817694, 830211681, 546695397, 192797326, 648388736, 982778184, 984130080, 694548490, 869941945, 596447180, 657048494, 659111742, 110244358, 307193054, 45065366, 861668078, 344203210, 199147537}

    82558

    Returns: 449668529

  45. {296132579, 105909350, 320452292, 209762398, 636373933, 809649229, 809494947, 531432208, 670018415, 775254863, 154613845, 828429878}

    471478

    Returns: 78220732

  46. {764189163, 578120339, 911521224, 258206409, 653448590, 335525630, 275785662, 722703083, 793874906, 964568268, 487871184, 869692513, 28229430, 331853797, 983452480, 202396397, 800223340, 981348321}

    255113

    Returns: 1096061

  47. {187131484, 288525763, 944663569, 750657728}

    451698

    Returns: 980505141

  48. {13801157, 396785468, 682951182, 265601509, 431034015, 544656689, 192270657, 844502691, 189381670, 192209615, 647481449, 53886781, 231001523, 338394543, 654959070, 432279362, 703765701, 322000707, 786839155, 287368544, 671933863, 99681987, 325095825, 247043053, 46682255, 601999444, 506017811, 997758613, 965973116, 875313313, 328610375, 253339595, 317597696, 894692255, 490139238, 192337769, 189849489, 595094751, 325087308, 850177816, 494085229, 310477149, 312925620, 657037925, 795951971, 55600562, 896589650, 329287801, 975807843, 40733571, 707908843, 929726138, 73633916, 655557036, 643533008, 429162252, 609167346, 543472064, 456325863, 157158293, 406337811, 412934040, 706612068, 582866171, 240725785, 569160043, 601548321, 444055918, 742740156, 477778426, 579570713, 873508151, 951141124, 195851681, 271125097, 430168720, 343942783, 982086238, 359893798, 965526417, 133832752, 405968573, 467516742, 150919523, 96397850, 788783620, 465623791, 268026355, 253058919, 3795734, 275981015, 581999942, 878244190, 27255389, 860733383, 361917826, 425869258, 923440938}

    470305

    Returns: 111217051

  49. {212617237, 272297390, 72661578, 728706101, 54359800, 260817297, 187496022, 655400072, 378584168, 371797146, 89760090, 734884754, 535993288, 280134609, 301299248, 825547801, 641592965, 395144935, 219442694, 873439307, 51486093, 885307928, 279650887, 523175052, 249946077, 713515652, 117424596, 567095306, 900685018, 328202784, 198192511, 426046959, 301908536, 795213016, 635367512, 981060514, 765388552, 216486916, 566987261, 300931476, 815929985, 172275958, 173352263, 343708248, 164534169, 298745038, 517629708, 105991853, 306762031, 745304562, 280681362, 162143873, 419878592, 724193895, 235521335, 238159963, 860849121, 808592008, 848136889, 191248811, 92590547, 987660075, 311456702, 554942738, 156493368, 876242435, 499431674, 834892398, 316968557, 33901618, 114449043, 952905550, 729813895, 595832880, 237159747, 222616949, 114139692, 211464671, 536220190, 411516942, 324732523, 769448531, 274169982, 13067809, 919717079, 360152608, 386949583, 450942182, 103822817, 94427179, 353892625, 995858020, 279236865, 572639173, 896214698, 248826997, 623870422, 772429306, 740979507}

    747604

    Returns: 855917199

  50. {986259275, 860373156, 533938415, 591479416, 749538918, 678755198, 215440317, 828937986, 36628313, 795546307, 180078286, 25448690, 611340766, 934120926, 934513593, 336877536, 244322081, 736662056, 393837976, 906430369, 245963741, 262725165, 524668521, 397811676, 216656721, 885282511, 927293718, 455987663, 200184748, 497790844, 639470632, 660253708, 238873739, 38176964, 826290732, 436688070, 500501549, 248927732, 454766825, 980906547, 822121572, 19522819, 453936704, 663800371, 550453667, 70802934, 526784636, 207625627, 419665642, 201346481, 777915218, 2211188, 257245317, 528541724, 558128167, 12602705, 898376970, 591124264, 317379691, 514706265, 337414809, 328994774, 656135483, 751560230, 713953677, 557338348, 761754040, 743463424, 800394633, 673053408, 542072698, 403219852, 670768202, 238829734, 723897792, 57843448, 233551650, 234624600, 818372068, 527463247, 631265854, 473560128, 535136612, 908666815, 429421179, 583893764, 431799896, 150271760, 449470262, 383566398, 13877558, 747734427, 562817262, 364707772, 585987424, 798255604, 114938110, 821901444}

    706146

    Returns: 18593504

  51. {547493938, 931847486, 414265720, 281294714, 164181214, 951306365, 56688850, 230979638, 56690750, 604562855, 281029825, 739067791, 277614973, 189249999, 401874113, 950060050, 658667777, 401158250, 248011406, 612564358, 621495513, 594568371, 872220174, 930006773, 994658875, 143127586, 253225509, 113920546, 952702928, 144266278, 385963700, 923636420, 55165532, 155823830, 786789266, 990476920, 187481095, 418898248, 826599391, 900571674, 825205548, 744611073, 713352709, 290524755, 560740181, 67494238, 669588348, 785950664, 571590225, 165324553, 965512134, 258641277, 345948914, 487992591, 919497847, 556632984, 792194209, 761415306, 282034523, 101148590, 376513442, 819631326, 275478582, 10155154, 677837918, 593916634, 299698975, 572832777, 287353556, 499217863, 563220039, 658538631, 501418462, 944602910, 161660824, 390297591, 144895586, 720544820, 921603225, 223253833, 21160640, 105468699, 58139390, 412762888, 530315118, 221224953, 705318991, 724342890, 567823096, 721431415, 618386722, 169462444, 678918193, 752245956, 394835119, 62328240, 598871823, 798436401, 195162645}

    878458

    Returns: 790355567

  52. {831896541, 514805273, 458392916, 61241079, 754253426, 533779298, 744593238, 754688725, 935725065, 739479286, 831874040, 934099746, 251564145, 550377765, 618517409, 348597778, 547385011, 236234056, 416981367, 796277982, 489729987, 145735096, 687187182, 182328204, 184478658, 943232848, 212721360, 863698752, 357046587, 2010801, 635660418, 561926682, 790170009, 214741079, 588868849, 911907434, 480850466, 175644374, 313103870, 560192715, 689403681, 466535559, 702957187, 507180463, 595265539, 468208979, 926796725, 737194166, 23044474, 179104229, 625450003, 459795417, 428283207, 34652972, 598651985, 53058897, 65053482, 650577805, 740716553, 109357599, 222852837, 517651730, 202174619, 857634748, 592178307, 958688670, 34418159, 847690669, 572991024, 963159847, 826423976, 129017748, 17742396, 356236843, 277872449, 514973481, 298763155, 105827682, 978162830, 813553732, 793192424, 707831772, 125632138, 385260198, 518939842, 9716293, 298988001, 613584394, 494047372, 940803296, 987673638, 478896674, 199322697, 132361033, 277800698, 395851892, 500197733, 57880096}

    504913

    Returns: 94390143

  53. {87950281, 739757410, 962318869, 816310106, 750686834, 225533883, 398039651, 210635569, 247461793, 777436844, 628517516, 153767819, 221121272, 532004561, 551951617, 799620535, 114532246, 312032389, 827297157, 650600548, 684791407, 793573402, 735932377, 580240073, 815785239, 924310291, 106770599, 851821593, 902928378, 526143480, 208486131, 40580456, 161287836, 790538421, 543532827, 811870054, 277548715, 159082738, 301181834, 400523950, 157695078, 911572038, 357240199, 980577723, 925069863, 853625939, 713391958, 896529439, 978911321, 571040945, 397614256, 965206459, 136452756, 971217700, 153953317, 459828809, 436724952, 612887487, 868950776, 341034993, 728208641, 193067737, 649519024, 876791388, 834487372, 402755978, 20344374, 979446763, 112322228, 455785522, 800162067, 179101077, 732818034, 986987789, 921246381, 69804500, 108226771, 139419976, 110871231, 851205383, 82081724, 862382746, 923624750, 234031193, 30770936, 194248717, 882180891, 415231217, 103621867, 68780599, 874407455, 599595345, 517035513, 803658002, 948375310, 18738801, 131750027}

    984086

    Returns: 403477621

  54. {140551516, 753834577, 141293877, 299279181, 240666055, 148905246, 55229543, 416444351, 170467705, 450047870, 867064651, 594596606, 31346005, 77974721, 982773215, 262086705, 726624786, 746916155, 541027220, 458114087, 545839915, 674207932, 643078498, 67975262, 835660131, 380272268, 260698435, 382992504, 286030621, 982568721, 202201186, 47483763, 328120033, 968766200, 47827540, 190332539, 975297835, 63516251, 562056353, 334230789, 330453695, 469157740, 770290503, 992164257, 365330557, 945698143, 985950062, 50577083, 394685689, 799010025, 842343877, 697276698, 645647087, 270204400, 684199671, 196558361, 558633715, 839300396, 851168911, 673923180, 175589868, 204563366, 664869282, 25891435, 571780889, 806471571, 848640198, 500003984, 246945115, 846880136, 278753557, 448365805, 515588645, 5752703, 810016245, 703632125, 56076456, 957917669, 366298956, 662790209, 436999491, 99641421, 81435418, 667150430, 367121133, 224108135, 278851271, 367238887, 744334619, 129607545, 668408720, 163207890, 639506700, 483867094, 958449883, 406535781, 624240571, 360740995, 217129347}

    996238

    Returns: 510002687

  55. {268399389, 517757549, 190466591, 616585642, 439481772, 417095665, 212910190, 37795998, 347434840, 47746916, 915362140, 252600135, 72385970, 125070530, 293970753, 257113855, 517674450, 473753261, 811590955, 150119021, 664967025, 103078065, 752813264, 8879673, 629895714, 357689261, 304566467, 612363519, 42998395, 284345844, 401900570, 873338536, 400092316, 391982934, 169679834, 976923234, 94422491, 803231121, 276033385, 96455714, 518070106, 575731187, 543300212, 501318155, 716302255, 365860307, 650029266, 415643757, 174904828, 989003388, 316783866, 129565820, 478161477, 454370136, 627489227, 725676406, 284447000, 267563092, 774427045, 258779868, 868017395, 817865003, 49504544, 168415524, 35749791, 821399374, 990085810, 327454326, 694479045, 884262483, 450406514, 531153724, 265783814, 943266942, 227603246, 999015167, 60560270, 744572697, 292550425, 854161230, 622681490, 890882317, 624440559, 228344211, 553293429, 41254426, 345312096, 294178269, 143121695, 446931315, 128712614, 124007020, 245111140, 569414851, 974761206, 192525605, 748334009, 779796208, 655503114}

    959979

    Returns: 283211021

  56. {420286676, 347711872, 288080402, 7517714, 960070962, 740115153, 855855854, 947787579, 998435346, 742992524, 537290480, 574456193, 293121693, 773416207, 189880157, 547861487, 922298487, 9181606, 676421106, 553131102, 631688866, 330010512, 932255271, 616271365, 319444604, 720848160, 439916696, 618354816, 626808370, 402208309, 355005166, 262388857, 302384348, 229755489, 730964527, 985398973, 741074731, 361716932, 433132622, 882582409, 849247767, 885370670, 750359832, 399340534, 735527424, 793830321, 891192890, 227214661, 146815373, 818624434, 381033067, 551813018, 31125318, 498497119, 159062299, 586203990, 377753678, 956513139, 424835479, 96050206, 92402513, 79149231, 596064678, 450618873, 924692027, 840066084, 849089339, 541471591, 919756489, 165476214, 718829400, 198863725, 875516599, 180766996, 486462815, 74426788, 229317621, 393470522, 724452965, 411093410, 206755839, 534360400, 751862504, 75680179, 674293820, 598657281, 533138314, 213153573, 60338391, 21506175, 346964753, 603604606, 208980916, 408664791, 13619271, 148780192, 597085465, 719790912}

    914589

    Returns: 608491836

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: