Statistics

Problem Statement for "TheSequencesLevelThree"

Problem Statement

When John and Brus were high school students, they liked to investigate integer sequences. Once, John wrote down a sequence containing distinct positive integers. Brus wanted to reorder the elements to get a "mountain sequence". A sequence a0, a1, ..., an-1 is called a mountain sequence if there exists an index j, where 0 &lt j &lt n-1, such that the sequence a0, a1, ..., aj is strictly increasing, and the sequence aj, aj+1, ..., an-1 is strictly decreasing. A sequence is strictly increasing if each element is strictly greater than the element before it, and a sequence is strictly decreasing if each element is strictly less than the element before it.

Brus also wanted the resulting sequence to satisfy one additional rule. The absolute difference between each pair of adjacent elements must be less than or equal to k.

You are given a int[] sequence containing John's original sequence. Return the number of possible valid mountain sequences Brus could construct modulo 1234567891. If no valid sequences can be constructed, return 0.

Definition

Class:
TheSequencesLevelThree
Method:
find
Parameters:
int[], int
Returns:
int
Method signature:
int find(int[] sequence, int k)
(be sure your method is public)

Constraints

  • sequence will contain between 1 and 50 elements, inclusive.
  • Each element of sequence will be between 1 and 1,000,000,000, inclusive.
  • All elements in sequence will be distinct.
  • k will be between 1 and 1,000,000,000, inclusive.

Examples

  1. {1, 5, 10, 4}

    10

    Returns: 6

    There are six ways for Brus to get the "mountain sequence" - {1, 4, 10, 5}, {1, 5, 10, 4}, {1, 10, 5, 4}, {4, 5, 10, 1}, {4, 10, 5, 1}, {5, 10, 4, 1}.

  2. {1, 5, 10, 4}

    6

    Returns: 4

    Because of the additional rule where adjacent elements cannot differ by more than k=6, the following sequences are not valid: {1, 10, 5, 4} and {4, 5, 10, 1}.

  3. {4, 44, 7, 77}

    1

    Returns: 0

    No possible ways.

  4. {96, 29, 21, 90, 46, 77, 31, 63, 79}

    44

    Returns: 126

  5. {13, 81, 85, 38, 1, 60}

    1

    Returns: 0

  6. {77, 37}

    9

    Returns: 0

  7. {91, 96, 89, 85, 11}

    1

    Returns: 0

  8. {4890852, 379268590, 118341523, 597007, 35766291, 247776868, 116752252, 480572137, 84970744, 653352031, 26239573, 40873981, 683447134, 392289611, 37215529, 675016434, 336971125, 706221269, 473038165, 194041605, 160567226, 222071041, 80835681, 86546365, 106923811, 82426873, 33557677, 950090227, 436291073, 69909135, 168544291, 301413357, 366496749, 278840199, 374079501, 8670529, 659598369, 21417563, 326051437, 170427799, 257655784, 119255907, 3615545, 391749388, 549646417, 37379061, 466701607, 36629217}

    167851001

    Returns: 0

  9. {456277933, 175661017, 26251201, 28813551, 213861391, 202752005, 442531277, 250585851, 68665077, 656926309, 50647921, 192772201, 611472343, 52809583, 178898386, 289056665, 14555683, 250903, 686164677}

    119372137

    Returns: 0

  10. {64330753, 104482891, 136198441, 299339510, 439816011, 236010407, 63360106, 63932449, 149331196, 794252593, 27851201, 437904637, 92223251, 74219097, 438442529, 82147847, 20271344, 123774176, 849265278, 330283357, 30983497, 255966471, 292941209, 437791390, 488776302, 196833889, 122674666, 339141601, 46521319, 52717531, 480265849, 70778345, 186901672, 582531183, 555958105, 186501223, 407678041, 596993853, 479907210}

    188605873

    Returns: 0

  11. {90335786, 228487851, 13459343, 11961136, 18288337, 202792311, 52890320, 119602407, 60751697, 177873991, 759510676, 19800257, 96124225, 263356167, 140024951, 272277715, 462468469, 144162639, 466145677, 126052505, 37192363, 456152068, 569458429, 75402983, 366428517, 786077677, 523707697}

    394379241

    Returns: 63850876

  12. {627050926, 486760961, 25942713, 110659253, 480197161, 391464293, 491542653, 36905331, 607749264, 21208253, 408720305, 105095949, 2445525, 33999096, 151577301, 605882857, 56474001, 441998981, 456892043, 1757001, 187372681, 6854951, 538865644, 439653544}

    4050376

    Returns: 0

  13. {13772401, 892697482, 455212561, 324308881, 103003941, 49556358, 3025309, 333243725, 314309232, 725063961, 547331701, 258076799, 108803556, 33084517, 103267725, 163781818, 444585961, 167787463, 331592376, 102239781, 656981445, 44985669, 452452851, 10440641, 50335433, 29386281}

    179722713

    Returns: 0

  14. {584621542, 587153344, 199147873, 29941836, 359842316}

    216593161

    Returns: 0

  15. {117129546, 28761175, 2262014, 106814401, 7724542}

    323762309

    Returns: 14

  16. {404222456, 387610043, 485556471, 316477283, 630631849, 57251857, 8148876, 758024551, 257282897, 147422905, 29056621, 372197731, 477573241, 419768385, 20280769, 4323901, 330407056, 178958211, 620371, 167512789, 276793294, 127236921, 20845559, 326644411, 521863129, 759808281}

    57414326

    Returns: 0

  17. {3460867, 789222661, 114462269, 310692889, 185394433, 7656526, 593009368, 26998479, 149926090, 517142305, 13483279, 368634529, 603205, 237289207, 23634370, 618600041, 451039817, 199760711, 53073945, 480931524, 312840401, 16399813, 159336148, 189268951, 327724189, 37190692, 175526846, 293743777, 592933461, 511396804, 197046297, 271929124, 52924537, 119138216, 70562761, 850328911, 811416463, 125192278, 50890065, 253761476, 681162225, 501399361, 18903751, 77993476, 386985061, 50869922, 53117101, 144640225}

    816269961

    Returns: 452484489

  18. {159222273, 49486465, 897950775, 236306497, 791597317, 577607501, 382282839, 138297331, 498490546}

    512120673

    Returns: 158

  19. {2109889, 188435617, 221719849, 437524103, 88916563, 161456047, 9342301, 235659163}

    82422341

    Returns: 0

  20. {122027171, 9558836, 884849057, 478694305, 43755429, 366934345, 719201914, 18181525, 178401601, 443114781, 36808450, 214644046, 55704871, 196127875, 169745492, 434750965, 30415086, 37398047, 827355406, 859407685, 797663488, 852601, 17503147, 719906254, 328437569, 78564403, 245122156, 191897326, 710743573, 261338905, 429941953, 705153, 249849701, 37435123, 54872229, 333120351, 124592189, 38282536, 204338391, 25705788, 75543237, 53066023, 68096281, 74202640, 606566617}

    580927751

    Returns: 323669202

  21. {135766290, 649646416, 347776867, 216752251, 100597006, 250378795, 237583462, 474079500, 466496748, 182426872, 322071040, 759598368, 126239572, 103615544, 180835680, 566701606, 492289610, 260567225, 137215528, 137379060, 783447133, 206923810, 121417562, 133557676, 108670528, 219255906, 268544290, 491749387, 294041604, 186546364, 269909134, 753352030, 401413356, 580572136, 140873980, 136629216, 806221268, 270427798, 479268589, 536291072, 184970743, 104890851, 573038164, 357655783, 436971124, 150090226, 218341522, 378840198, 775016433, 426051436}

    167850999

    Returns: 30

  22. {389056664, 588776301, 236135826, 538442528, 682531182, 696993852, 275661016, 539816010, 756926308, 288605872, 278898385, 163360105, 507678040, 204482890, 150647920, 711472342, 392941208, 170778344, 286501222, 101740976, 467082664, 500354781, 556277932, 542531276, 819413688, 537791389, 146521318, 250953621, 537904636, 336010406, 186708231, 100250902, 350585850, 439141600, 236198440, 164330752, 163932448, 114555682, 244208960, 134644510, 152809582, 222674665, 399339509, 459490600, 655958104, 302752004, 292772200, 168665076, 174219096, 128813550}

    126251200

    Returns: 228519564

  23. {311859639, 213190750, 219711628, 523188884, 161474686, 591315148, 357244834, 232727578, 170953718, 138371240, 115405769, 569069512, 130391024, 286085235, 109856896, 340524736, 493186913, 858987916, 432152310, 871804540, 209615218, 725352805, 104476635, 101993264, 126304960, 445474072, 673534710, 761662372, 322807551, 104703684, 311951914, 197979505, 644418700, 205043115, 498713616, 300494797, 420516970, 225370428, 216936618, 747333036, 653902118, 216869478, 360860996, 340430120, 181507654, 136982250, 795134188, 309071423, 167311552, 555546030}

    170778792

    Returns: 1040070501

  24. {114829017, 911705544, 468415840, 430411000, 640395691, 296465632, 253032690, 741080800, 294536440, 191915252, 244254383, 235195895, 247039970, 605147590, 179777782, 491854309, 137994250, 550525712, 701131216, 249281339, 346995320, 661782220, 397753660, 435803054, 297272881, 164825600, 652455050, 631386520, 137749216, 489121362, 689677586, 391407004, 151228520, 655455499, 117353260, 207509220, 203134999, 527316100, 207845204, 140269138, 101840326, 296845040, 131269600, 464023761, 394777487, 141111600, 140823480, 115052548, 303465940, 263038312}

    125942712

    Returns: 0

  25. {173435176, 952544847, 407740784, 413830439, 143436158, 297046296, 170562760, 348171352, 193502520, 214462268, 468634528, 250633604, 647596650, 185115160, 598727740, 275526845, 618678244, 107818980, 486985060, 908417747, 113483278, 255265662, 115185844, 593496025, 767415472, 111073108, 209137987, 339846733, 458595208, 916269960, 361574080, 493618550, 116399812, 473783842, 911416462, 117563000, 104764300, 962897840, 225192277, 102934265, 132312136, 150477733, 244640224, 275664124, 630819520, 289268950, 589955200, 249926089, 580931523, 291041647}

    105755574

    Returns: 0

  26. {387659896, 165633007, 527963875, 182422340, 780345260, 270927460, 208351263, 259222272, 731623916, 238297330, 612120672, 931600386, 100155820, 140913200, 152659132, 222443104, 598490545, 646050421, 120618130, 128475325, 336306496, 107433428, 891597316, 799041549, 448720690, 119163760, 482282838, 375225490, 222775912, 288486650, 105484810, 335659162, 383182533, 360924625, 389151646, 784689808, 233611687, 169345414, 106144984, 413747404, 589351810, 477970535, 109342300, 395481648, 149486464, 474821405, 677607500, 997950774, 276473664, 106895936}

    146676567

    Returns: 745561358

  27. {123534154, 984849056, 959407684, 115529137, 534750964, 175543236, 291897325, 154872228, 933807942, 107619240, 138282535, 189268144, 155704870, 543114780, 251226204, 125705787, 433120350, 473857135, 100705152, 136808449, 224592188, 130415085, 308388616, 174432700, 466934344, 223910884, 819906253, 347283505, 278401600, 296127874, 100852600, 769898600, 137435122, 345122155, 118181524, 140747176, 698343235, 349849700, 361338904, 222027170, 160158016, 309803656, 652623484, 170216902, 109558835, 304338390, 706566616, 240954880, 269745491, 359151711}

    127355397

    Returns: 2

  28. {481703248, 989728924, 294481716, 105017050, 689381608, 383859136, 269037022, 105615080, 315330670, 285087448, 481128814, 915196360, 133409185, 117709912, 626423196, 339776504, 483045676, 313688512, 670931848, 134217125, 510130882, 207799270, 115838254, 105764770, 334532104, 141789475, 423386400, 111375850, 382437315, 613899716, 471428416, 517019725, 355311760, 677996946, 226247086, 428584025, 481724115, 140086150, 620702092, 301694244, 115290100, 164841920, 263435348, 113777212, 371667552, 175185672, 206258800, 107417125, 399553232, 111136650}

    123804011

    Returns: 0

  29. {253445144, 116273168, 311217253, 104137602, 873142975, 286996012, 230029956, 169690456, 328784986, 146441544, 386843420, 783216388, 832878406, 187718362, 450593409, 132861484, 252704200, 117307387, 867733792, 168314980, 663579659, 721626684, 425337968, 112322622, 579416826, 153045208, 288395564, 179386336, 207761320, 158249854, 306237981, 301104964, 414222013, 128045464, 163257360, 350581468, 765723850, 567020046, 319372300, 299133850, 273948250, 110806789, 259361670, 870254684, 102510772, 455366236, 373580008, 767338734, 410837406, 656633155}

    102114040

    Returns: 0

  30. {356713030, 640028800, 123526912, 391956118, 397217522, 208696960, 132712660, 291079575, 187459820, 327844462, 211438800, 455213036, 134370350, 332556544, 391860904, 261301440, 237297363, 800149944, 935566609, 181280771, 708692735, 343320950, 274964636, 112124813, 495197942, 104211751, 100677221, 718952040, 139017160, 585833374, 110856538, 187719145, 392360322, 189370396, 105072949, 266214120, 315091456, 276908320, 781554092, 223703775, 129134560, 684404660, 418973200, 141490696, 955869003, 144574876, 244014752, 207758044, 641414755, 466674036}

    169353643

    Returns: 805360407

  31. {53, 91, 26, 86, 34, 90, 68, 27, 61, 31, 45, 52, 38, 23, 17, 22, 25, 63, 11, 65, 77, 99, 73, 7, 46, 35, 100, 79, 29, 71, 97, 1, 57, 84, 69, 41, 89, 44, 6, 49, 13, 96, 37, 21, 85, 5, 88, 81, 55, 60}

    1

    Returns: 0

  32. {16, 73, 71, 78, 63, 76, 89, 36, 1, 44, 31, 25, 49, 23, 7, 29, 41, 9, 37, 35, 67, 39, 51, 65, 72, 68, 43, 96, 47, 5, 97, 11, 15, 22, 10, 18, 57, 17, 91, 86, 93, 69, 66, 77, 20, 81, 58, 53}

    3

    Returns: 0

  33. {33, 83, 63, 10, 13, 67, 5, 28, 82, 87, 51, 58, 85, 9, 40, 80, 18, 86, 34, 95, 68, 37, 17, 26, 21, 1, 55, 81, 99, 25, 45, 69, 59, 53, 61, 32, 56, 97, 76, 41, 73, 48, 71, 16, 57, 89, 77}

    1

    Returns: 0

  34. {66, 11, 38, 31, 92, 9, 18, 76, 24, 19, 13, 7, 79, 33, 57, 90, 1, 30, 17, 68, 21, 37, 97, 26, 8, 41, 70, 81, 5, 83, 67, 69, 77, 61, 65, 48, 53, 51, 89, 16, 4, 22, 63, 58, 45, 25, 56}

    1

    Returns: 0

  35. {81, 93, 89, 71, 47, 50, 3, 75, 1, 53, 43, 37, 23, 85, 65, 83, 6, 15, 41, 36, 77, 97, 26, 27, 31, 91, 45, 73, 12, 51, 25, 33, 38, 35, 52, 56, 29, 17, 92, 86, 9, 57, 55, 14, 54, 5, 63, 88}

    1

    Returns: 0

  36. {44, 46, 18, 15, 45, 48, 42, 17, 30, 2, 11, 32, 5, 20, 27, 37, 28, 7, 50, 12, 22, 21, 43, 9, 10, 35, 38, 26, 25, 13, 3, 36, 34, 19, 47, 8, 41, 4, 1, 49, 40, 16, 39, 23, 31, 14, 6, 29, 33, 24}

    1

    Returns: 0

  37. {27, 14, 43, 26, 25, 6, 5, 4, 45, 40, 28, 1, 23, 7, 24, 13, 31, 48, 18, 21, 3, 34, 38, 12, 49, 41, 39, 32, 22, 9, 17, 19, 37, 35, 47, 29, 2, 16, 44, 42, 10, 8, 20, 30, 36, 15, 46, 11, 33}

    1

    Returns: 0

  38. {20, 29, 44, 23, 38, 12, 33, 30, 35, 43, 26, 18, 28, 45, 8, 22, 42, 47, 21, 5, 17, 4, 34, 31, 40, 16, 3, 13, 39, 25, 10, 6, 48, 14, 9, 27, 1, 7, 19, 36, 32, 46, 2, 41, 15, 24, 37, 11}

    1

    Returns: 0

  39. {34, 8, 31, 41, 38, 12, 44, 45, 14, 7, 32, 30, 28, 47, 46, 5, 35, 15, 24, 40, 33, 36, 19, 23, 3, 22, 18, 4, 21, 10, 9, 42, 25, 17, 16, 26, 39, 11, 37, 43, 6, 29, 13, 27, 20, 2, 1}

    1

    Returns: 0

  40. {27, 21, 16, 20, 12, 18, 5, 19, 38, 22, 14, 40, 2, 15, 35, 17, 44, 45, 13, 31, 43, 42, 28, 34, 11, 46, 36, 24, 23, 6, 26, 1, 41, 29, 30, 33, 9, 7, 39, 25, 32, 10, 37, 3, 8, 4}

    1

    Returns: 0

  41. {44, 46, 18, 15, 45, 48, 42, 17, 30, 2, 11, 32, 5, 20, 27, 37, 28, 7, 50, 12, 22, 21, 43, 9, 10, 35, 38, 26, 25, 13, 3, 36, 34, 19, 47, 8, 41, 4, 1, 49, 40, 16, 39, 23, 31, 14, 6, 29, 33, 24}

    2

    Returns: 96

  42. {27, 14, 43, 26, 25, 6, 5, 4, 45, 40, 28, 1, 23, 7, 24, 13, 31, 48, 18, 21, 3, 34, 38, 12, 49, 41, 39, 32, 22, 9, 17, 19, 37, 35, 47, 29, 2, 16, 44, 42, 10, 8, 20, 30, 36, 15, 46, 11, 33}

    2

    Returns: 94

  43. {20, 29, 44, 23, 38, 12, 33, 30, 35, 43, 26, 18, 28, 45, 8, 22, 42, 47, 21, 5, 17, 4, 34, 31, 40, 16, 3, 13, 39, 25, 10, 6, 48, 14, 9, 27, 1, 7, 19, 36, 32, 46, 2, 41, 15, 24, 37, 11}

    2

    Returns: 92

  44. {34, 8, 31, 41, 38, 12, 44, 45, 14, 7, 32, 30, 28, 47, 46, 5, 35, 15, 24, 40, 33, 36, 19, 23, 3, 22, 18, 4, 21, 10, 9, 42, 25, 17, 16, 26, 39, 11, 37, 43, 6, 29, 13, 27, 20, 2, 1}

    2

    Returns: 90

  45. {27, 21, 16, 20, 12, 18, 5, 19, 38, 22, 14, 40, 2, 15, 35, 17, 44, 45, 13, 31, 43, 42, 28, 34, 11, 46, 36, 24, 23, 6, 26, 1, 41, 29, 30, 33, 9, 7, 39, 25, 32, 10, 37, 3, 8, 4}

    2

    Returns: 88

  46. {44, 46, 18, 15, 45, 48, 42, 17, 30, 2, 11, 32, 5, 20, 27, 37, 28, 7, 50, 12, 22, 21, 43, 9, 10, 35, 38, 26, 25, 13, 3, 36, 34, 19, 47, 8, 41, 4, 1, 49, 40, 16, 39, 23, 31, 14, 6, 29, 33, 24}

    4

    Returns: 451652028

  47. {44, 46, 18, 15, 45, 48, 42, 17, 30, 2, 11, 32, 5, 20, 27, 37, 28, 7, 50, 12, 22, 21, 43, 9, 10, 35, 38, 26, 25, 13, 3, 36, 34, 19, 47, 8, 41, 4, 1, 49, 40, 16, 39, 23, 31, 14, 6, 29, 33, 24}

    47

    Returns: 575372103

  48. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}

    100

    Returns: 575372111

  49. {1000}

    1000000000

    Returns: 0

  50. {100,1}

    98

    Returns: 0

  51. {100,1}

    99

    Returns: 0

  52. {100,1}

    100

    Returns: 0

  53. {1, 5, 10, 4 }

    10

    Returns: 6

  54. {784592781, 393747479, 630711365, 640300397, 802238565, 673629101, 246206605, 147481293, 549710613, 952389982, 527294538, 11229426, 649340534, 442669998, 763972693, 534538531, 561938670, 846323783, 56140228, 945463653, 433425905, 315654719, 190034456, 787898445, 703414090, 7629572, 807392990, 425977761, 525814215, 692529554, 648377666, 124050406, 83778742, 762283712, 947148395, 938580706, 694759944, 898768516, 638076529, 964001489, 196193711, 608647549, 890938527, 311455215, 478294409, 808863655, 635032701, 567524298, 187672549, 50 }

    1000000000

    Returns: 575372111

  55. {96, 29, 21, 90, 46, 77, 31, 63, 79 }

    44

    Returns: 126

  56. {479486253, 284222518, 874095071, 756038148, 815416615, 38337765, 500958246, 359927047, 227116660, 66387119, 930586145, 412642448, 16691959, 11647848, 183790220, 364443252, 964398340, 420166104, 625028106, 607802040, 246927456, 448477049, 708280707, 659071684, 178835319, 937419910, 272835901, 134478389, 990592716, 351755151, 903195572, 564591716, 620166104, 499303403, 547976354, 991666979, 454128723, 555936853, 832368690, 625639001, 32260986, 952694710, 269900185, 820700190, 911709864, 162392001, 351774174, 879927293, 676499127, 366517779 }

    200000000

    Returns: 529098457

  57. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    47

    Returns: 575372103

  58. {1, 5, 10, 4 }

    6

    Returns: 4

  59. {13, 2, 10, 99, 97, 28, 59, 83, 87, 91, 19, 63, 33, 41, 72, 52, 92, 42, 95, 18, 9, 48, 65, 67, 66, 8, 7, 77, 6, 100, 78, 82, 55, 36, 57, 40, 26, 4, 88, 17, 62, 69, 15, 14, 25, 56, 98, 20, 21, 60 }

    40

    Returns: 1010350755

  60. {757148, 167851001, 301413357, 336971125, 659598369, 160567226, 391749388, 4890852, 35766291, 26239573, 473038165, 597007, 3615545, 326051437, 392289611, 118341523, 170427799, 37215529, 675016434, 168544291, 683447134, 950090227, 82426873, 116752252, 194041605, 706221269, 106990913, 257655784, 84970744, 21417563, 37379061, 40873981, 8670529, 80835681, 436291073, 653352031, 106923811, 374079501, 466701607, 86546365, 247776868, 480572137, 222071041, 36629217, 366496749, 549646417, 278840199, 119255907, 33557677, 379268590 }

    500000000

    Returns: 276505745

  61. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    100

    Returns: 575372111

  62. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    50

    Returns: 575372111

  63. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    1000

    Returns: 575372111

  64. {23947014, 29946939, 38694283, 45958121, 62060280, 69040531, 112979906, 147864617, 162654038, 169196882, 205779557, 266700308, 271188716, 274077789, 319634332, 348712326, 381319124, 433333678, 446788887, 488037425, 495536274, 511744560, 520818484, 530411997, 550995135, 635520606, 669315635, 685515459, 692927183, 694541641, 716187921, 720188087, 720939677, 729825005, 732640103, 789063606, 832938465, 837125819, 859820735, 869464831, 870997295, 898581855, 907087125, 908598379, 927068846, 935415170, 958010784, 976189171, 981761887, 995714854 }

    400000000

    Returns: 899269515

  65. {374592500, 902786786, 62801091, 998574303, 59891470, 880630500, 325697503, 782671450, 991667950, 229549775, 671878274, 106000767, 180023494, 744649053, 560144777, 764566194, 965156751, 217438761, 106949811, 295437934, 165218756, 481305829, 229228333, 451463128, 73212664, 451467606, 981205204, 531612025, 972303939, 928907829, 186179416, 199412791, 684210967, 248980506, 197987093, 744102436, 129611005, 376200947, 379290237, 973795306, 605750721, 51168511, 79796072, 785774215, 648333915, 639940848, 402856760, 613490665, 709895961, 362322922 }

    908928598

    Returns: 575371759

  66. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    10

    Returns: 347659197

  67. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    1000000000

    Returns: 575372111

  68. {1 }

    100

    Returns: 0

  69. {5 }

    5

    Returns: 0

  70. {1 }

    10

    Returns: 0

  71. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    10000

    Returns: 575372111

  72. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    4

    Returns: 157302

  73. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    1000000

    Returns: 575372111

  74. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    100000000

    Returns: 575372111

  75. {1, 2 }

    10

    Returns: 0

  76. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    5

    Returns: 1156502765

  77. {8 }

    8

    Returns: 0

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: