12431 - Happy 10/9 Day

All about problems in Volume 124. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

12431 - Happy 10/9 Day

Post by brianfry713 »

Random input:

Code: Select all

1000
1208865744 49 40 1388381726
1150423218 31 18 1975270275
198479450 34 29 1500073894
1364480253 57 24 303313633
624837298 17 2 1881924608
989770350 23 15 316641991
378646935 89 18 147753298
1371511613 19 10 104619052
1745985803 94 20 103824166
1920445089 94 18 619339352
1116772285 60 58 1072935984
1699077345 28 13 1689019692
1503501974 42 40 2146684235
1129868185 7 0 415999217
987611231 85 58 61503491
1659123320 49 11 1291782126
1327217083 25 23 644532903
1235801850 41 20 2006550846
160769149 56 6 1071619413
2036616107 47 46 538859376
853902538 12 4 2036277488
868545570 74 33 1738423107
1966049140 75 24 1344802193
1884706961 81 59 2067795995
1828717503 57 50 587830636
1378901015 54 35 17135269
1701910138 5 2 1122126190
51561878 97 95 1252033008
1445619903 51 11 836193380
79575788 13 9 741751489
428170703 81 58 2022838624
360512570 58 54 1375830089
263074909 81 76 1229834409
188240710 31 7 958782128
1594410234 93 60 1034162438
1279538644 27 0 1333709795
449552364 86 83 403952878
1084774399 39 18 744356721
415379017 11 7 427269429
1619276593 44 30 1678339115
2007659552 12 0 817638010
1709844806 75 62 1376843776
402234361 10 0 1938567460
1147213131 58 15 655259853
57433449 50 44 111964253
1476032669 81 35 2125893645
61295294 98 23 507669300
799214641 6 1 519819624
966394122 7 0 1415439739
908322430 96 46 707807156
1623684572 70 59 1685526669
1252515603 28 18 844846146
1813131371 50 0 72695901
456785322 19 12 304673250
850867314 30 25 885608429
595402036 95 68 51168853
2111408456 20 16 161988849
1368686971 24 20 2090551435
1821897328 5 4 35320379
1836976921 95 31 1468301949
1592103745 84 51 89394685
1206410482 19 12 496821387
640374218 53 8 419486034
1937263477 76 64 1559876101
444177305 25 8 650088762
74267355 29 6 625951873
1541438774 69 38 510268522
1372084670 31 10 675610315
1159072932 23 19 586073041
317840593 55 4 718110184
1608251103 88 57 127793912
1262051312 84 30 46507415
1289752723 2 0 1151735566
291476040 77 34 1371609244
1712964586 32 28 1112701110
405832775 77 54 916363211
437847030 75 31 1754270372
1462493124 95 51 1782905471
1450885745 76 37 1713902432
309522373 64 32 173807860
955747215 54 24 124198377
1230201736 88 46 815811524
1569340409 59 58 932654419
1203970232 75 33 1733248279
1664931909 10 0 1392595242
791232798 75 9 250021234
1576849862 78 67 1903201962
1255069599 20 13 660088302
132610649 66 26 1338163681
1935004188 28 23 1310556419
1944744818 32 20 11011408
936811040 71 50 1184550484
1457679140 98 95 495565013
562026263 22 16 1434200684
1119445171 82 14 196063183
1640438162 79 51 1877764710
1074936297 14 7 290364285
1696647893 21 3 988377546
596164991 91 8 71834137
1686046696 74 21 347656815
1588808073 20 6 1987235329
316387714 71 55 1097670476
2401493 75 33 2142226812
793468967 94 55 1662864004
1406665343 67 47 1268404816
1108687665 41 30 583378451
1911597206 96 78 302255001
1493133641 81 80 1090345036
56565433 34 25 298918792
542839276 30 15 937808753
657576140 33 16 1808786029
1129911023 3 2 40596774
1418300301 28 13 1171966721
263074110 31 22 1344922304
149605470 59 53 2084356972
1957315075 3 1 1477347920
1025372329 99 33 429713528
152590547 37 14 239350004
1224818767 75 35 2113452371
1315567084 15 6 113728144
893556386 81 30 596338859
1440954818 61 39 965888053
1929979734 78 42 1183818162
142465495 45 10 1085815749
735567907 53 47 1606208019
1746210406 24 4 588565778
561099996 59 42 1698325139
950264497 51 35 1030791666
1420908037 86 59 315567167
36732946 12 5 852967729
402984674 85 18 157455845
611317221 92 15 1559040191
715838936 13 2 1713287990
708904618 14 0 87559932
1450454703 14 2 1138111217
1648549757 90 30 999188044
448726780 66 15 2097056432
691842753 82 44 1636353351
889597140 80 65 304688755
734009859 91 35 1640277593
1360452052 80 73 700315838
426277190 11 6 1764414486
776461288 43 30 1191877634
1358337238 52 16 2129967442
734597089 83 51 1199501542
334696791 89 84 145040093
165974145 64 41 373783619
1072659497 65 47 577724641
2065916247 78 12 202349148
574322039 33 4 207500922
1442960584 92 42 73958032
2135982050 45 37 1628310723
1368699859 23 8 313394542
908163481 87 71 2051684
242412865 19 3 780206930
488488400 51 29 1974121627
1995750759 26 15 1600700262
1060096089 42 16 751630785
882030641 97 26 1773372475
1934528164 32 17 1009387197
1781216371 70 64 1593624532
1971511517 57 53 711657375
702312226 42 8 1616033828
1471658932 50 24 1381513094
495447241 21 0 1597721622
1027457574 38 29 1742515191
475119918 80 53 1911116353
2095801638 83 51 632533608
1674350706 83 31 1417908807
1473946838 52 29 123946916
1035168901 7 3 1564819306
1633578458 32 24 1219576040
871682771 12 2 1679270226
495222137 4 0 1537085380
2073737985 51 39 1661144910
224869360 85 68 1232506486
485014178 63 14 1604106686
1320550696 88 54 1250114990
1466299398 73 16 1987736429
1729642833 62 55 567580132
1373668477 15 4 933936258
1624256072 50 12 205498651
2012838429 47 6 691749018
279703500 29 6 1425082734
462275724 90 6 1989444204
1759526192 12 2 576195043
1476276643 67 55 1991062366
510525559 70 56 2030736148
1140726745 89 43 1512277781
1436936344 10 8 1605601000
2074121872 71 35 20525928
179830784 69 51 1392515264
179067716 72 66 971059399
1963702264 74 70 277449277
532186843 99 64 869452199
1569893455 77 37 203447436
1286017999 74 29 779422788
387406507 35 28 1180635720
499286660 93 5 1877761818
209785603 81 77 520386453
891216644 62 43 1321223949
1719701218 40 18 179963576
1802120473 35 7 1999930516
1771619519 92 66 1147116813
16596090 96 44 1787666830
2021980548 2 0 1485624563
191212516 78 70 718047327
582395982 12 9 1052901001
1825314525 8 1 789851436
2019230785 23 21 33564236
2089389054 4 0 1501936506
280625622 32 27 750914240
1211916322 100 11 476195145
1030238790 68 0 701224308
510221764 12 8 1460196779
592255431 4 1 1622449422
1234632220 31 15 418746723
338322061 56 11 1667618400
1523640928 11 2 632763317
1774774976 97 6 1993752390
136799944 97 23 2101488260
2074500552 93 53 1925620869
1603948129 24 19 241006389
2128273019 97 11 1529856413
253430444 95 44 318806217
861012226 13 5 174317298
43274521 44 0 871979971
1040712598 50 45 2041436053
503185935 32 28 509773497
1526244716 7 2 197067626
154046176 5 0 867441506
50933756 47 19 1031429107
1189176291 64 38 1350257136
184171398 75 65 896116703
338861737 36 5 139874372
2029267441 62 57 2045495414
695695978 6 0 409603226
1044744865 40 4 815172565
1932428339 72 39 1057166241
1291347021 70 13 1333626586
2060974506 57 6 140242645
656972372 24 15 235744531
409445679 34 15 325108173
630905199 75 45 227924793
1244198869 95 86 676199197
1026502183 24 4 1401058221
251852511 10 3 1340251124
1062794135 74 53 647325319
1823927310 95 11 1876239195
340118979 94 6 1073947247
1622175357 93 1 1329250140
47219301 72 51 1040794127
1060881437 91 40 1432198084
996513469 53 30 1432878253
1152039790 83 79 751346844
38756477 65 5 644081862
337337485 43 24 1043635267
1369154285 37 4 48616170
787557592 51 43 1427021120
2037324921 71 1 949442900
919929991 61 10 2126195061
2037235394 48 18 890622680
893158037 74 72 1017325789
2034245058 47 17 1109141810
2122875941 97 84 647114651
2073597129 6 0 901555357
501424425 49 37 40908922
1224509156 75 72 1548447965
791265394 30 25 1341988406
1727096960 11 10 1913398956
297165098 23 22 1722808673
689760262 41 15 1404685861
600047684 70 23 408025401
1490673584 46 7 2009699131
893476224 65 43 1239832236
20472281 45 33 235880058
1662995900 29 7 2114940876
516613631 31 2 1492754813
1752546671 23 18 1715380558
876899634 40 3 997705235
567827744 36 12 959975837
725315722 82 59 2003108480
1736253619 91 43 1903115688
1569380559 63 4 1589293676
1290123438 61 1 420979925
834330925 91 44 180018372
720498052 74 2 473032148
728984369 16 4 734217230
368900737 29 1 926861353
1877943251 85 68 1207829792
954973927 69 24 565524756
1564085686 72 12 1075955472
1263186484 56 43 1461763647
1389697299 75 58 365978895
162264776 2 1 389427707
670354355 86 11 1560109386
1121973274 53 32 40577608
64385581 75 50 2133471549
558847439 91 74 171662449
597069668 23 3 1396230344
204808711 15 11 682174951
1887164887 59 34 1810289912
1175878906 86 39 1557217711
1309330538 48 43 793195158
2082180164 13 2 738004703
1275505259 60 43 1136253039
408049759 55 11 1018441603
977698639 70 66 1809802172
1392647320 8 4 717891930
432932162 30 7 629529710
1009107221 77 17 1034274572
513758845 20 9 1307560679
622074336 58 55 454774273
751459149 94 89 447537456
1733167355 28 11 1584448642
1591260639 73 26 17144686
1115734807 28 21 1745889693
267199527 37 36 1968752868
535529871 48 42 1009994387
68153150 12 2 1447260856
1345578790 5 4 1497744075
1263776939 39 21 440323430
1124055588 15 9 1109063198
1861244497 21 11 1412842989
1239184787 70 64 1404256888
2081069897 59 29 230678974
1410744778 16 6 635207411
1837019746 100 26 1518404833
666463140 56 23 21641764
339253616 9 6 984669178
1072456609 87 0 632217074
908825447 35 31 2031141780
365957477 62 18 1615713111
939581796 10 4 1506910898
2077102926 67 22 768659843
1008246286 38 23 1681740852
17864159 100 25 654270263
1585188166 84 5 1457465855
1987259342 38 29 1820426976
844516478 89 67 1296378582
463516479 58 34 749127725
103189633 89 13 1510017679
270774901 65 30 1605941199
696097368 58 23 1799447934
1945173987 27 13 806246963
58428450 3 0 1071079300
300624087 9 3 1893039629
1806542605 54 39 646805283
1504487980 41 30 208130870
1849342422 85 21 1525673709
2124329661 80 41 1640486522
1598685354 66 54 1251654859
26647343 10 1 1386904907
1054523185 28 3 631770547
1419261088 7 1 2130763582
2026018222 14 3 352804187
131599956 67 43 1200895479
1563216798 88 72 843216517
1628670197 46 14 1953576050
968165434 77 31 65522543
1762928006 34 9 328763946
1337861019 61 28 1079888567
1693253716 76 49 2025114813
791370407 81 55 1687958502
1320455870 22 5 807327194
1986763099 69 5 756429091
1620268752 28 2 128768182
1646718172 57 18 400337901
1689636337 12 8 1435763312
1431336730 2 0 1932130071
2040196586 53 15 1489652165
1771497349 42 27 401411437
711798691 12 5 1607053706
778520639 58 15 1680658589
2003717493 9 2 2019027788
1000983885 24 15 692256279
348704172 39 31 617630897
64554906 27 20 1423150280
1795445813 89 14 609664049
72330467 70 2 641351187
316920391 51 26 216445435
1559047145 90 89 1335207299
1478633478 47 21 1346746772
2019538992 41 11 770749357
1790657571 96 27 875270287
916255714 35 26 2000800416
1474056302 91 42 1812480320
407269102 81 53 1983677391
1949743200 86 3 183032277
577507365 29 5 1819630521
910413046 99 40 629104036
640749996 26 0 240790907
1266998112 40 38 1003227904
1319525488 39 0 2139136395
2110480923 33 17 599988055
488820974 75 0 45001260
1746273111 7 0 1094455868
1785496384 3 2 1652387220
1533860999 21 7 84954020
1441806120 80 66 1330894169
1043183096 62 48 311051265
2106837076 28 22 597090759
1633260611 20 9 861323075
1134357870 26 11 292617078
6192036 83 32 265678461
2052073287 81 8 909444159
1320143105 6 5 192630551
1710163144 59 45 1465577984
2079333258 98 32 1175786158
822472081 64 28 821087525
441251284 46 6 1961037386
1493243759 48 33 282846979
319107470 100 94 161272838
2065115174 20 8 1143640565
712312187 5 4 1662147746
609387680 17 4 1852240205
505935982 85 43 880854272
1236868746 28 1 432440325
352164877 51 14 1636657105
320545873 14 6 1106245534
190751719 87 22 1197360781
1529788813 23 21 863350450
1358256627 76 10 1346157874
1931457144 28 25 369609032
804921450 46 42 361397946
1039832332 39 28 1618317538
879511428 72 39 1572426575
1798706831 2 1 1089922194
333317024 42 28 1839710642
933591990 37 28 2097841793
199946799 40 7 1957723186
1430311871 22 7 2112009274
1119761841 29 21 273829770
852154653 8 3 2129539866
2085671252 39 14 1404107731
486345602 44 22 784239732
1032044168 21 11 1578869335
678259848 22 0 535284812
525372917 94 84 2110001124
252966672 65 16 862126940
880620369 21 7 2043434458
1432489819 77 53 1384839035
988009392 43 4 1316957453
430180261 99 67 960088208
1920701373 77 48 146533970
1027343130 41 4 1280376936
1169937512 2 0 1329684219
1180284219 63 42 1360917185
1134875021 32 10 648149046
526967548 14 8 1646195960
769383300 53 29 1790558613
994637066 30 0 841848285
1670201035 14 10 514304340
890092039 70 26 1219332363
445860442 22 17 2102776563
425594445 51 21 1335450085
1869103562 85 25 1539565599
1853947674 66 44 1980350656
79105144 59 52 1763564400
1446311290 82 14 1675410885
1836912852 59 49 1841596999
1314978645 38 37 1519089192
643108557 55 6 492067143
1663632709 97 68 1239500099
1669859959 66 5 481688818
1937981445 58 49 1633840082
1707849869 97 8 1852171308
1422330121 35 19 943345149
1550904212 74 47 1975706186
674210187 39 19 1691280565
1863381286 23 21 331754646
55353145 5 0 238538095
1034782738 33 30 617299319
1353576585 80 53 954053438
2038839641 48 5 694883474
128203472 86 78 1920620315
948670933 32 2 277961788
2005106411 89 27 250023243
5548984 33 26 792716213
1751481219 18 9 953050745
1674005814 85 37 1786115230
1251426115 37 26 1464060842
1649689288 32 27 1794041556
1168537426 6 4 308984572
408705063 12 9 1309516794
2141317923 66 4 1592605828
1269092698 100 5 1987331872
215765382 49 36 60285385
291601984 26 13 1511870576
839908435 29 13 622386298
1836122426 14 7 538326558
1434257488 28 22 2120006833
694096365 77 44 826900912
509861482 99 32 2109290375
594553918 68 59 687313897
446516247 89 20 504560800
697395496 69 44 552606847
1443937348 62 41 133662680
1519300366 8 4 1879418004
986497517 65 39 1989752328
941192682 80 40 501553107
265014784 37 2 221040871
1655954048 68 12 1082524694
1456033220 60 33 1669888000
1250004341 87 8 693104875
1498756791 43 21 1543248996
979640890 91 76 1679034165
42988786 40 5 1676647713
494077004 46 12 1499248638
481160627 71 43 287751982
809878520 54 35 1618660488
1216076037 47 28 2092101319
1464490100 88 32 124373157
795321855 21 13 865054769
1917908128 99 59 1686336750
1246217984 100 12 1593617502
518188351 10 7 797594732
308139739 12 5 351903126
964144804 96 49 988980003
1571320219 54 15 1236446348
880958008 56 13 351333920
1612993972 43 25 1704089911
310960177 92 6 1303758957
1695275301 85 5 1196831716
932289511 69 63 1149989500
1324972590 58 10 1065328980
840423008 79 16 210963859
660746062 12 5 174370936
1742093543 6 0 1152586247
1952135521 70 55 1070500282
976668400 53 21 443538669
1487313182 82 23 1672790209
29705037 33 20 590440054
1562594368 74 29 1512548292
1023438708 64 30 1496311370
48903511 84 56 519793304
234088410 73 14 1078405189
228197411 84 69 851117271
787542674 72 25 154352331
354954951 25 6 1729325861
1828051300 92 74 399491250
1488068043 72 10 1739337612
611363989 3 2 1498695745
1543384949 27 21 2048207870
980551231 7 2 303780904
302070464 13 8 1816213640
1650224860 77 73 266130803
20255281 91 87 1216985343
1381032484 39 15 242356148
922375443 68 61 943984950
166202445 35 20 1085639979
1965493609 75 42 46523282
1505202358 12 10 1339577103
831389415 15 10 2007309832
2121413648 79 46 749402309
1435380594 53 37 191826788
268393046 22 2 1842491860
934190207 39 12 1390546307
1315066837 66 61 577024271
973851736 13 7 662496396
862896943 63 58 1931637988
1917421156 69 50 2138843265
559665927 69 20 2028416983
506943056 73 27 1885536435
72054160 45 5 516492300
88257595 23 0 1966104589
1019192762 28 18 2106637017
476239614 56 16 388917579
1964536088 20 16 177131293
909252833 38 36 885939265
839632720 87 57 1478341102
649454886 95 80 1316481630
1592528887 18 14 2121911876
188694378 58 14 1727753411
161072895 42 24 936627263
1498616759 83 79 1053447987
1399070187 73 52 1976449065
1481777280 41 19 902659145
1449910485 52 26 1629758129
484246391 54 26 1520502126
1287979521 61 20 673390767
1940567308 57 35 1610078109
1724766563 66 23 537077389
673621006 89 32 591469062
1135339159 91 26 244085223
1380260964 44 21 86046915
367077505 9 8 643559140
1511507971 69 31 634569522
1561620817 10 2 780615523
642431705 50 25 2128677741
2108796857 48 43 1308861030
173280921 45 8 1295614292
538960232 35 3 560141758
214510068 32 10 1778252868
290905976 53 21 454425347
249471508 17 12 1432911467
309253324 46 12 306934141
806399714 20 7 1018313152
2080020624 89 78 1171399647
1859229804 70 15 1402647136
461493917 44 19 1414437974
1319535551 42 39 22443934
1565864148 42 36 1257591556
609062714 19 15 1265371824
1860434197 43 38 1478944331
529464367 5 1 1870001065
1213447353 29 21 1287063184
357531915 9 6 567819237
879980754 11 8 1175899896
1675213109 13 0 1495029815
1148157095 25 7 1662474183
205184674 7 1 761445614
442680131 45 24 528052197
1144486676 20 16 437485483
119291688 50 29 1434145839
1836738637 45 2 1135643888
1362403964 9 6 1295849434
1248533322 46 27 621268398
916621290 85 27 1983727031
690595292 59 22 2006426576
637564737 67 35 1039941184
1054491684 68 27 2105419919
1246563535 45 40 1992501792
1144722166 9 7 1650606973
1442368358 90 50 1505054265
115097946 69 43 1249775904
1683708281 78 52 792624798
1038562850 19 14 6041549
375925749 15 0 1360095346
562630076 67 60 1310695350
2136375523 67 47 456717155
758813237 30 19 597528485
2081421763 59 39 1493256520
1681568060 20 19 597115976
2041308498 59 6 1080755294
2132779573 88 66 1444612617
1975255930 44 20 461031637
779956830 19 8 1791639105
60713089 27 24 52112319
604739904 33 1 1902462744
1843784390 56 17 873224270
712597370 67 65 587714077
607782563 96 10 448177845
402531127 57 41 1538809918
1624084891 74 15 954300160
699328226 23 17 620705764
1322458886 26 5 1025406775
2028621485 56 4 1579567639
1775648505 82 73 318393159
427092957 34 13 955307378
1148792035 42 12 947184444
190868618 14 2 1627954006
1033226132 39 16 1781626568
927666766 14 8 2071511579
1729820575 56 50 345112022
82504272 69 23 2029840791
1106857536 82 57 1188396988
1399705940 46 37 51431353
1337126509 25 0 421342362
336583235 31 10 1952337487
1841329089 61 14 1195464986
2068927621 26 15 954880074
1077188107 30 17 724154208
807261651 29 9 1114739310
151873367 99 22 870361505
1920408653 96 41 1300586029
1623741109 8 0 1952593631
1196444227 64 55 490562990
658037243 61 34 1182650061
1290038582 49 11 1511801873
694983782 93 35 83262114
1353654073 49 2 1379435418
1024106131 42 16 1268880970
2143911741 10 4 909623096
324696899 5 0 1907082647
1936189963 77 41 1433009896
458222795 63 35 263947143
1864221447 74 53 1026224771
160004660 24 19 1968004415
1302269458 54 13 1913967012
1457347684 60 19 871702522
348575046 6 3 975923074
985684059 88 47 926461328
680163884 65 2 46929420
2086625577 31 27 1221133929
1209361936 91 85 739164405
1759641355 57 19 67601307
869449003 60 43 735541678
1241086167 89 20 1093319103
657280599 13 8 1633088813
624054068 81 22 115449508
473255489 19 0 269871382
1590880361 70 47 295120980
1593970554 12 11 68277144
2117446768 60 39 2022125242
69943821 39 28 2120555423
988149404 3 1 1018725160
916396816 70 61 753207551
1031035984 72 10 1140911011
754304053 20 12 697185185
2026591547 59 25 1916688890
2120844483 95 92 850459413
1335284277 60 21 531723064
1571185715 77 42 782736075
158307910 13 4 568774436
43155395 40 4 2057281472
314007577 55 18 467671960
9679660 78 73 430999203
37686828 12 1 1266012395
694089165 11 9 1361866010
250900264 37 31 2101855263
391085275 23 10 1287117891
1030390664 14 3 86453800
1046960457 64 9 1624097909
1109143363 57 9 253788
631457433 81 72 281796015
1516796567 38 18 1007610580
2115582014 94 23 680191922
1371671226 70 58 2092775525
940818444 51 47 2041084607
2123790029 93 78 164666036
1733050163 67 24 897271517
1328778294 17 14 236751223
2066355645 88 85 1813532899
895652770 75 37 481896338
1796651796 26 13 1499070646
529288640 43 22 1082749764
956405480 51 4 636112224
442058554 29 26 1293832542
941145714 21 8 1955978697
563793507 5 3 722334945
1062044024 68 6 2082676084
1579177033 92 88 1918334066
566799937 49 47 673964280
585581117 31 30 101700904
1538591386 85 65 418712011
1756164962 83 22 327214808
180956127 63 7 2008275007
971510497 68 32 672267385
1024548594 79 35 1227415136
120702967 44 37 1843767664
2126962339 78 60 1684587157
376617538 74 24 1783591479
1767364393 77 11 2107046403
422487417 6 0 1748375214
44809226 80 22 1925872733
1058116290 56 25 1348193176
1426390215 55 12 902390593
968922903 27 11 391423212
1714814779 70 12 87112436
1925523754 14 7 1513461400
1759801715 86 64 1859157591
921732079 28 26 773966557
1003012110 91 0 638249026
267083215 74 34 1982861025
1336442576 71 30 1996309633
168775915 56 22 1093082961
903415661 62 2 1106283423
1945285327 89 32 1827539361
851778810 13 7 79376617
1405698813 2 1 1592408876
2069616453 97 66 592568543
1165713887 6 0 174872025
263947205 84 33 1882689447
2008484155 13 10 512554644
2091099240 67 34 168830164
1388099178 73 3 1445871933
231108073 100 38 1299020663
827120142 95 15 1865905226
738936038 35 0 1898034160
2096604193 31 3 938468964
1501963521 58 51 111839090
95748151 41 1 645790869
663506908 28 26 2127380193
803533378 80 4 1928264661
1823747565 63 10 2144000424
25928473 45 17 523964688
199937734 80 29 1252637004
717297081 49 33 522030786
1258263607 2 0 362126028
1822537927 75 7 1434740979
692922352 91 53 1393375500
106474538 79 46 242683623
2101622398 64 21 383613532
1182093417 76 29 286122512
1582381833 41 33 744931732
1900832391 19 1 1531089428
753648702 44 32 223972217
925867070 74 38 218140458
638188820 96 76 767264166
1249148185 81 63 967761502
111469603 86 46 527401811
204800188 40 18 1183354156
1047764755 23 2 528110521
1804931755 48 24 1939377285
1674579048 16 7 1812725846
1494898612 5 3 839799788
469528093 24 22 2071751890
95921128 45 7 730267140
2071193272 78 39 774479564
1738635958 18 17 1500953749
1940780568 68 11 1915691832
1723451321 7 6 1440030561
988655412 30 20 2009325482
161221926 11 2 1703509189
372323525 27 21 321674158
162126599 67 9 201942648
786772281 62 12 675635381
2058169749 76 73 214346034
1690139684 99 51 1016841654
1414661323 4 0 1302211694
1865695148 44 13 369170429
1552973399 75 72 591903461
1965518914 75 47 510183443
1688548300 83 23 246057926
950798787 40 12 65998087
262898336 79 77 705761522
2031991740 8 2 565467907
884249479 52 9 1071661727
1366028124 16 1 1555002500
912999929 79 2 481894403
1704203935 34 3 549331148
1717082378 7 1 711197058
1057539263 100 15 1573105518
1853986566 97 71 1381882403
1667546261 15 12 1125991969
1491002202 16 11 890180423
297121585 38 36 1006773069
333261668 17 6 1481064550
678301121 45 16 1941156707
1282065260 15 9 1135250539
692255800 87 78 768297366
1950046428 54 36 1512558472
541236838 63 8 2137253374
1177649422 35 18 1874421132
74894375 70 16 594302067
1958278664 16 9 537408871
835952045 91 73 298137995
1994260941 6 5 736995986
1507989470 35 16 162654529
18796143 44 16 937791809
1807511682 43 34 633177641
1093825676 51 7 444788371
966973405 2 1 164964814
1033455613 68 60 1576876091
1160918969 22 6 1266864556
1361670243 57 44 1839941312
1530325192 81 70 1546729353
1264599047 33 23 2032728313
878537429 94 27 2109154314
1445549474 84 11 1762304535
482159384 16 13 993599505
150522383 93 40 1042807650
18565450 27 23 1237539004
785108858 73 18 171653964
2055420829 25 0 2102411756
358595077 58 48 1717071735
2085201436 94 8 2097163307
1491769893 63 11 1062011960
331119762 17 13 1648306491
705819049 10 3 1342060623
1362112644 86 48 1793083494
1535637126 91 60 2104620191
1899721070 17 10 167688254
1416018739 68 45 468626885
2130290735 62 6 1347965002
170621128 61 5 589520139
633973473 37 20 1301022606
927715557 37 24 983383032
446236686 40 31 2064177019
1933378211 70 0 142082405
47046997 55 51 1277964469
17414247 90 84 1796448129
1259422794 77 34 669318613
1349181732 95 85 1474798312
1123936849 11 7 1931784809
1396667068 78 74 1175464077
965987360 41 1 46513309
498366370 21 0 1677293916
406882440 77 35 290013905
935907866 8 5 2008479100
1789152816 73 36 424518019
380169950 44 26 1477890931
2029876282 7 4 826522455
946660329 18 4 1408275555
1643384575 100 87 974479806
1312064809 14 3 517045961
746038249 85 68 539680661
930990176 46 43 2143243934
172110985 40 22 1729793124
174908848 2 0 1563510242
97051930 39 28 2056387732
624484852 83 39 1336361182
667647412 14 1 808876298
2132982123 13 5 114653073
1055009845 65 7 1551175821
1967214410 24 19 265999189
908509070 31 17 411175715
69751355 79 66 544122680
1770206401 92 15 1140719398
492954269 93 26 1210515541
1197830448 36 20 367593382
1136580187 32 25 992830253
1943458530 3 1 1914865644
2029173496 68 18 2030106403
121000776 31 19 1755031037
604696831 89 31 1873616833
1196449512 69 68 357555413
1439979143 54 10 474627188
1324467023 48 37 702521813
2091874489 34 23 1673654863
1474418042 86 73 357669944
534091166 97 67 1503555013
1262772468 58 36 2146306805
591808923 25 23 845844070
623986787 33 16 2094888882
1264252989 75 53 1330178566
1580568794 6 5 406808222
1374016293 63 29 754799925
1352762566 38 25 1265325356
1732499120 55 25 2057058574
1780838071 13 10 394462024
296221927 38 6 567773589
937211242 49 31 2013421778
1081333425 83 38 836690993
1176478649 13 3 495216946
215003089 4 0 2039378204
1778616630 2 1 1103961979
921934986 51 16 1307135737
794420204 17 13 63936392
1146888802 89 84 780452752
1842507576 82 14 2010850842
1943557399 81 54 2138080625
1735830791 34 10 1290775923
192406741 45 44 1375563692
1345578925 82 29 1371115885
84882084 66 21 1187171823
1882818193 71 18 675319669
2102163301 92 17 1969944417
385886148 11 0 818839741
1295250639 46 44 426060932
752023684 41 15 1154512297
714634361 10 3 686948012
441348221 22 9 767970145
1058766532 76 72 32759899
16368339 87 50 1405532592
913821322 34 2 1676324422
1157117231 39 21 1768235219
1763649356 56 4 1481667368
871288356 40 30 1188482001
1786010261 51 42 1312619814
1888248277 19 10 1498652353
92008171 63 49 606105137
1092147440 2 0 1593632236
1470153523 22 4 79424500
1894472219 48 32 1158192582
981072317 99 93 784671325
1701099690 68 7 1878827316
977069791 67 27 1290799739
25897047 74 8 1419501134
1889760350 41 40 1517365578
2085987175 33 0 226281725
5882293 66 40 692909254
195994488 34 25 1888444154
351301507 43 25 1263508789
2038815937 72 11 881943827
667228360 68 54 1244543849
394683957 27 8 1586236497
1919632592 89 70 811030622
1343018570 50 17 971384799
1367912238 4 2 1119309518
1385901853 20 4 1101771726
1212649322 35 23 593489880
1500693623 77 39 1642120907
1255742441 83 81 1972383689
219771316 43 9 713563740
414423059 5 1 1787387055
128098608 34 22 1850056376
1682152268 86 80 958858843
130943785 19 8 912433922
833873859 53 17 510290182
744108547 13 0 300091069
1536127646 46 20 207522166
298196618 4 0 1502793736
1753985346 38 13 1747819219
124790543 70 42 322577656
1194583417 2 1 1230611149
1501485223 90 1 580029633
1095247254 46 24 521636660
946718836 9 5 374959265
1503567335 81 72 1691723138
42246718 19 12 2091261794
994505662 8 6 366899979
1970914132 56 11 1530832367
609521289 83 59 778755365
301621163 98 74 196057454
1539421840 49 33 151398295
1108838989 3 1 1088740567
1680013281 94 84 674019860
161911722 90 17 119202978
AC output:

Code: Select all

Case 1: 492347670
Case 2: 1496111319
Case 3: 784300215
Case 4: 117353973
Case 5: 932379268
Case 6: 280104523
Case 7: 17524666
Case 8: 91656818
Case 9: 73399748
Case 10: 436233406
Case 11: 1061848450
Case 12: 532408881
Case 13: 166200530
Case 14: 0
Case 15: 4281224
Case 16: 952801828
Case 17: 367547021
Case 18: 1729369206
Case 19: 644875893
Case 20: 80648158
Case 21: 306564980
Case 22: 842057451
Case 23: 670981968
Case 24: 118026824
Case 25: 160365278
Case 26: 14579545
Case 27: 580318002
Case 28: 386750506
Case 29: 5253303
Case 30: 720217832
Case 31: 1198587110
Case 32: 1333970291
Case 33: 453371539
Case 34: 488717776
Case 35: 527032444
Case 36: 0
Case 37: 268852647
Case 38: 271764405
Case 39: 415770631
Case 40: 179006145
Case 41: 0
Case 42: 490656888
Case 43: 0
Case 44: 648244839
Case 45: 18739759
Case 46: 321201620
Case 47: 439332597
Case 48: 315516283
Case 49: 0
Case 50: 682403842
Case 51: 1455638335
Case 52: 696987126
Case 53: 0
Case 54: 269930640
Case 55: 490456468
Case 56: 3852493
Case 57: 146454456
Case 58: 963072235
Case 59: 2615452
Case 60: 1033064491
Case 61: 66047356
Case 62: 354069408
Case 63: 21462102
Case 64: 524106080
Case 65: 117506284
Case 66: 29767755
Case 67: 135663306
Case 68: 210806600
Case 69: 515426282
Case 70: 512004332
Case 71: 67948265
Case 72: 23493065
Case 73: 0
Case 74: 1358210444
Case 75: 109943844
Case 76: 738226174
Case 77: 1266571092
Case 78: 738972355
Case 79: 1168662257
Case 80: 31572952
Case 81: 111136383
Case 82: 175324382
Case 83: 349066402
Case 84: 2221431
Case 85: 0
Case 86: 92437818
Case 87: 1296830839
Case 88: 36722401
Case 89: 345404300
Case 90: 96653578
Case 91: 660
Case 92: 716318636
Case 93: 338529453
Case 94: 1102467032
Case 95: 8185770
Case 96: 428729310
Case 97: 181324822
Case 98: 982695327
Case 99: 36081432
Case 100: 62850915
Case 101: 1271650223
Case 102: 618555288
Case 103: 1636999881
Case 104: 1386956633
Case 105: 98957387
Case 106: 341681950
Case 107: 162646368
Case 108: 931592148
Case 109: 182890567
Case 110: 865305505
Case 111: 1316707190
Case 112: 7322876
Case 113: 368442020
Case 114: 296712768
Case 115: 352974640
Case 116: 1134813693
Case 117: 228788497
Case 118: 26735878
Case 119: 1018217626
Case 120: 37220160
Case 121: 280654705
Case 122: 256601644
Case 123: 5501064
Case 124: 256050646
Case 125: 1495353737
Case 126: 47815780
Case 127: 303025513
Case 128: 547811699
Case 129: 66410139
Case 130: 357168774
Case 131: 21475408
Case 132: 1486897577
Case 133: 657681390
Case 134: 0
Case 135: 246858373
Case 136: 625656086
Case 137: 917607377
Case 138: 937006164
Case 139: 155428875
Case 140: 733758469
Case 141: 130637601
Case 142: 1559760084
Case 143: 916736886
Case 144: 1004891158
Case 145: 1039034295
Case 146: 83704126
Case 147: 173100972
Case 148: 68599357
Case 149: 108189780
Case 150: 144857890
Case 151: 63708162
Case 152: 508694146
Case 153: 48039928
Case 154: 411155
Case 155: 326951443
Case 156: 706252916
Case 157: 325617561
Case 158: 222324466
Case 159: 1116445426
Case 160: 576411468
Case 161: 223711092
Case 162: 397873178
Case 163: 439792000
Case 164: 670122086
Case 165: 0
Case 166: 1250644482
Case 167: 1846118673
Case 168: 227079468
Case 169: 669734289
Case 170: 52713669
Case 171: 877993311
Case 172: 664000992
Case 173: 374049548
Case 174: 0
Case 175: 989413005
Case 176: 412871608
Case 177: 652664180
Case 178: 557882350
Case 179: 1869140301
Case 180: 525075193
Case 181: 263065906
Case 182: 27906050
Case 183: 322537614
Case 184: 445999338
Case 185: 1012139394
Case 186: 114782129
Case 187: 1322226953
Case 188: 1620710924
Case 189: 624812266
Case 190: 747643888
Case 191: 2433024
Case 192: 1383382336
Case 193: 872593613
Case 194: 13082048
Case 195: 724317768
Case 196: 52066615
Case 197: 306697043
Case 198: 201254188
Case 199: 1001116802
Case 200: 245365970
Case 201: 140378292
Case 202: 122155194
Case 203: 1473724311
Case 204: 710807058
Case 205: 45830050
Case 206: 0
Case 207: 319624330
Case 208: 869295846
Case 209: 694557001
Case 210: 9486605
Case 211: 0
Case 212: 702250171
Case 213: 273784451
Case 214: 0
Case 215: 644672583
Case 216: 1329293439
Case 217: 10872228
Case 218: 1045051571
Case 219: 489103729
Case 220: 664851180
Case 221: 957359720
Case 222: 972663335
Case 223: 93292426
Case 224: 631791454
Case 225: 187980339
Case 226: 110031482
Case 227: 0
Case 228: 33932319
Case 229: 484294612
Case 230: 102859388
Case 231: 0
Case 232: 262590001
Case 233: 43156182
Case 234: 424709223
Case 235: 50160537
Case 236: 1507914721
Case 237: 0
Case 238: 359656824
Case 239: 233166384
Case 240: 208060391
Case 241: 8591603
Case 242: 205024821
Case 243: 266441568
Case 244: 217960731
Case 245: 374733920
Case 246: 1146771253
Case 247: 1023980001
Case 248: 24102115
Case 249: 945578151
Case 250: 329823481
Case 251: 1205586841
Case 252: 490816681
Case 253: 1184952512
Case 254: 1134905698
Case 255: 687128016
Case 256: 242752661
Case 257: 587404219
Case 258: 46760384
Case 259: 1045306256
Case 260: 561416221
Case 261: 1085222260
Case 262: 147181922
Case 263: 211767439
Case 264: 36812146
Case 265: 249294767
Case 266: 0
Case 267: 31137575
Case 268: 447729337
Case 269: 366102061
Case 270: 1144134300
Case 271: 61051102
Case 272: 292586831
Case 273: 145276147
Case 274: 350144559
Case 275: 820881312
Case 276: 148587975
Case 277: 1602182364
Case 278: 69200837
Case 279: 99087384
Case 280: 632716443
Case 281: 813484871
Case 282: 936605877
Case 283: 612783919
Case 284: 30541332
Case 285: 301872618
Case 286: 142426664
Case 287: 287030238
Case 288: 454682206
Case 289: 331387594
Case 290: 129854108
Case 291: 242756772
Case 292: 360180732
Case 293: 488424786
Case 294: 359854858
Case 295: 127941684
Case 296: 492433337
Case 297: 27622912
Case 298: 1273530506
Case 299: 57754988
Case 300: 1064541464
Case 301: 493478734
Case 302: 1213676762
Case 303: 957533560
Case 304: 529060273
Case 305: 122094082
Case 306: 728672920
Case 307: 427307599
Case 308: 345149058
Case 309: 142713540
Case 310: 526197007
Case 311: 972639617
Case 312: 152185417
Case 313: 136815307
Case 314: 420036435
Case 315: 1539077957
Case 316: 11176854
Case 317: 524298411
Case 318: 456322428
Case 319: 975917000
Case 320: 1420190138
Case 321: 1083366924
Case 322: 408936191
Case 323: 844947288
Case 324: 539003183
Case 325: 559751400
Case 326: 45166665
Case 327: 179860018
Case 328: 213857142
Case 329: 5911339
Case 330: 392347882
Case 331: 0
Case 332: 1652553571
Case 333: 1460563857
Case 334: 121857734
Case 335: 347566352
Case 336: 91142085
Case 337: 402536862
Case 338: 666203075
Case 339: 155418279
Case 340: 1197504132
Case 341: 634174977
Case 342: 62206867
Case 343: 1255937574
Case 344: 1696490721
Case 345: 753550315
Case 346: 0
Case 347: 1508808951
Case 348: 335244177
Case 349: 98010390
Case 350: 1496876472
Case 351: 1291255827
Case 352: 715554553
Case 353: 327090753
Case 354: 401679318
Case 355: 247712628
Case 356: 62083889
Case 357: 996291912
Case 358: 4360395
Case 359: 14065788
Case 360: 16475578
Case 361: 32895303
Case 362: 3729649
Case 363: 936728137
Case 364: 1285106323
Case 365: 766742471
Case 366: 544603985
Case 367: 55165264
Case 368: 51671133
Case 369: 1090306952
Case 370: 0
Case 371: 248122155
Case 372: 189267518
Case 373: 1418245581
Case 374: 1368394719
Case 375: 1713731650
Case 376: 527274960
Case 377: 509857301
Case 378: 266816520
Case 379: 481800483
Case 380: 326761132
Case 381: 50887786
Case 382: 368634351
Case 383: 105530124
Case 384: 516819492
Case 385: 630268982
Case 386: 1746566856
Case 387: 704584104
Case 388: 314072936
Case 389: 74398977
Case 390: 907713017
Case 391: 170958036
Case 392: 0
Case 393: 788874646
Case 394: 0
Case 395: 213172146
Case 396: 0
Case 397: 0
Case 398: 906394580
Case 399: 34280653
Case 400: 884271344
Case 401: 211454670
Case 402: 214406773
Case 403: 20080639
Case 404: 331875
Case 405: 220144041
Case 406: 452305061
Case 407: 15376802
Case 408: 44245872
Case 409: 763475728
Case 410: 769862153
Case 411: 1304873198
Case 412: 149589805
Case 413: 10072692
Case 414: 1016876253
Case 415: 979121194
Case 416: 821170175
Case 417: 309293102
Case 418: 388106214
Case 419: 389434253
Case 420: 626171532
Case 421: 462431197
Case 422: 252262901
Case 423: 57620122
Case 424: 176137429
Case 425: 170743104
Case 426: 1523803582
Case 427: 957438490
Case 428: 778110565
Case 429: 1173044348
Case 430: 1554278471
Case 431: 455931569
Case 432: 664750579
Case 433: 73424361
Case 434: 1929017469
Case 435: 261695656
Case 436: 302156910
Case 437: 839325948
Case 438: 0
Case 439: 1295295288
Case 440: 813986696
Case 441: 1296214771
Case 442: 832833441
Case 443: 541264454
Case 444: 876349915
Case 445: 327408
Case 446: 747070416
Case 447: 0
Case 448: 955320256
Case 449: 217568854
Case 450: 1644559520
Case 451: 844650954
Case 452: 0
Case 453: 288888490
Case 454: 630816299
Case 455: 492015887
Case 456: 464731695
Case 457: 926495432
Case 458: 282003668
Case 459: 896647440
Case 460: 673226732
Case 461: 528803399
Case 462: 699987391
Case 463: 323104374
Case 464: 379921216
Case 465: 260419411
Case 466: 679635327
Case 467: 623559832
Case 468: 702430309
Case 469: 1290877839
Case 470: 1032582609
Case 471: 181344606
Case 472: 0
Case 473: 169307114
Case 474: 631178175
Case 475: 532599843
Case 476: 1318705161
Case 477: 199221674
Case 478: 54210612
Case 479: 224858400
Case 480: 683893237
Case 481: 703673372
Case 482: 591340918
Case 483: 1222515555
Case 484: 28720892
Case 485: 1176264783
Case 486: 250603104
Case 487: 1920536489
Case 488: 53798215
Case 489: 1321222251
Case 490: 213712585
Case 491: 103335855
Case 492: 580328764
Case 493: 397100636
Case 494: 1406733325
Case 495: 567547321
Case 496: 164355020
Case 497: 464144391
Case 498: 122576555
Case 499: 1537754748
Case 500: 571399779
Case 501: 479446479
Case 502: 193577229
Case 503: 623593014
Case 504: 1058672813
Case 505: 48370858
Case 506: 1101375405
Case 507: 948246655
Case 508: 1226152349
Case 509: 821837832
Case 510: 117607703
Case 511: 309611705
Case 512: 277734415
Case 513: 72861664
Case 514: 515349966
Case 515: 543392600
Case 516: 35718054
Case 517: 641227605
Case 518: 26713205
Case 519: 235810882
Case 520: 802221309
Case 521: 31605349
Case 522: 505786820
Case 523: 70897584
Case 524: 565576813
Case 525: 767497013
Case 526: 798217350
Case 527: 170526090
Case 528: 166766257
Case 529: 0
Case 530: 311873847
Case 531: 358668051
Case 532: 75415579
Case 533: 193809950
Case 534: 1315099047
Case 535: 786746680
Case 536: 369048736
Case 537: 512779861
Case 538: 54978996
Case 539: 96415261
Case 540: 1413814120
Case 541: 68417250
Case 542: 17507170
Case 543: 381235982
Case 544: 296131651
Case 545: 156292082
Case 546: 308169120
Case 547: 48868268
Case 548: 635659860
Case 549: 83086644
Case 550: 930245023
Case 551: 614809580
Case 552: 42366756
Case 553: 587224885
Case 554: 1184234106
Case 555: 728409763
Case 556: 48466654
Case 557: 6878566
Case 558: 440136472
Case 559: 201985417
Case 560: 57747316
Case 561: 554161442
Case 562: 437351225
Case 563: 1594734938
Case 564: 23461605
Case 565: 316756580
Case 566: 0
Case 567: 1794514947
Case 568: 318014835
Case 569: 85975577
Case 570: 159468011
Case 571: 872752326
Case 572: 930841080
Case 573: 983729502
Case 574: 870455222
Case 575: 225312087
Case 576: 24639253
Case 577: 1042192731
Case 578: 335870280
Case 579: 1406558058
Case 580: 1052031578
Case 581: 340336161
Case 582: 548328692
Case 583: 334653880
Case 584: 139243824
Case 585: 207131540
Case 586: 19416870
Case 587: 101150008
Case 588: 450293395
Case 589: 347903677
Case 590: 209364160
Case 591: 1300505623
Case 592: 544543068
Case 593: 273839806
Case 594: 319772502
Case 595: 372560547
Case 596: 104663188
Case 597: 237872590
Case 598: 784214083
Case 599: 499861527
Case 600: 20134685
Case 601: 1143754201
Case 602: 6013067
Case 603: 66436552
Case 604: 16256316
Case 605: 1069634670
Case 606: 221726881
Case 607: 454482653
Case 608: 271769877
Case 609: 766929528
Case 610: 0
Case 611: 1614419498
Case 612: 357663508
Case 613: 490675053
Case 614: 104436449
Case 615: 1003326483
Case 616: 750251530
Case 617: 506560134
Case 618: 3989259
Case 619: 529195216
Case 620: 159428896
Case 621: 714487139
Case 622: 756130092
Case 623: 1109544376
Case 624: 1233677043
Case 625: 386844965
Case 626: 1134558490
Case 627: 388254694
Case 628: 2958831
Case 629: 0
Case 630: 971631150
Case 631: 355281959
Case 632: 309960664
Case 633: 514464619
Case 634: 202657799
Case 635: 940909500
Case 636: 682731759
Case 637: 311663955
Case 638: 1605602475
Case 639: 45317562
Case 640: 457739464
Case 641: 779321655
Case 642: 169818496
Case 643: 390170485
Case 644: 1459153201
Case 645: 811436905
Case 646: 91942524
Case 647: 145985955
Case 648: 663048944
Case 649: 216553605
Case 650: 347270723
Case 651: 603251112
Case 652: 1412909178
Case 653: 1026074040
Case 654: 1089286840
Case 655: 218803878
Case 656: 871003280
Case 657: 729561783
Case 658: 18221985
Case 659: 0
Case 660: 296696879
Case 661: 412261692
Case 662: 363050457
Case 663: 607817147
Case 664: 1113745779
Case 665: 38274672
Case 666: 1015167611
Case 667: 0
Case 668: 281947925
Case 669: 21317351
Case 670: 1229877729
Case 671: 3924896
Case 672: 1239134384
Case 673: 582297872
Case 674: 558558364
Case 675: 0
Case 676: 970572927
Case 677: 100259789
Case 678: 811808322
Case 679: 1703394170
Case 680: 979497763
Case 681: 365907163
Case 682: 259548723
Case 683: 797077207
Case 684: 41061732
Case 685: 135702723
Case 686: 724199050
Case 687: 60579871
Case 688: 217057121
Case 689: 305688056
Case 690: 1455008650
Case 691: 63026392
Case 692: 0
Case 693: 258110977
Case 694: 11082695
Case 695: 565631865
Case 696: 1708771470
Case 697: 346152080
Case 698: 658289846
Case 699: 695568433
Case 700: 430466182
Case 701: 1524777715
Case 702: 559550810
Case 703: 375804665
Case 704: 276170739
Case 705: 206966180
Case 706: 667637412
Case 707: 49271618
Case 708: 362832664
Case 709: 586131015
Case 710: 1037840825
Case 711: 354688321
Case 712: 1107845317
Case 713: 6960665
Case 714: 1514713992
Case 715: 158751
Case 716: 233831406
Case 717: 736502674
Case 718: 248034523
Case 719: 1158934293
Case 720: 1439296772
Case 721: 31707054
Case 722: 756906716
Case 723: 103808771
Case 724: 232964072
Case 725: 162623318
Case 726: 836766145
Case 727: 321475436
Case 728: 109372384
Case 729: 152225754
Case 730: 440490569
Case 731: 61796208
Case 732: 578095406
Case 733: 815780328
Case 734: 557323367
Case 735: 12605366
Case 736: 274561726
Case 737: 92190304
Case 738: 1996723539
Case 739: 168780532
Case 740: 804254032
Case 741: 654183793
Case 742: 313021656
Case 743: 184613931
Case 744: 609442229
Case 745: 0
Case 746: 1028719716
Case 747: 486428305
Case 748: 132140268
Case 749: 47792711
Case 750: 41918220
Case 751: 725609285
Case 752: 1259341579
Case 753: 611501007
Case 754: 0
Case 755: 1817359609
Case 756: 184023130
Case 757: 403032331
Case 758: 804684533
Case 759: 496605983
Case 760: 42001003
Case 761: 233325467
Case 762: 134262964
Case 763: 0
Case 764: 1144625250
Case 765: 124570414
Case 766: 31495448
Case 767: 843342867
Case 768: 1233428042
Case 769: 1083551406
Case 770: 0
Case 771: 23549655
Case 772: 22167031
Case 773: 475993612
Case 774: 1272525959
Case 775: 73035945
Case 776: 431942410
Case 777: 339778313
Case 778: 1251110505
Case 779: 145812375
Case 780: 0
Case 781: 1432733827
Case 782: 243652676
Case 783: 88707743
Case 784: 132819441
Case 785: 62129385
Case 786: 85195513
Case 787: 998988365
Case 788: 157112865
Case 789: 13432890
Case 790: 164804122
Case 791: 898476231
Case 792: 303914430
Case 793: 645500726
Case 794: 148301817
Case 795: 1471717572
Case 796: 677797041
Case 797: 233913428
Case 798: 302898982
Case 799: 246122332
Case 800: 174965161
Case 801: 1351938260
Case 802: 543737223
Case 803: 533216124
Case 804: 1267403026
Case 805: 170635773
Case 806: 319515459
Case 807: 69029037
Case 808: 394905382
Case 809: 66618681
Case 810: 964647222
Case 811: 0
Case 812: 340165282
Case 813: 7708136
Case 814: 292569042
Case 815: 106272318
Case 816: 19115498
Case 817: 254904524
Case 818: 266339354
Case 819: 488474078
Case 820: 26121289
Case 821: 441260585
Case 822: 361502665
Case 823: 177612638
Case 824: 633557055
Case 825: 1112592189
Case 826: 128610061
Case 827: 164662553
Case 828: 248737182
Case 829: 419468640
Case 830: 154694978
Case 831: 856571137
Case 832: 189342312
Case 833: 1454187884
Case 834: 1598795966
Case 835: 531879324
Case 836: 570133793
Case 837: 322621224
Case 838: 240578385
Case 839: 23583867
Case 840: 56688348
Case 841: 237105401
Case 842: 224830258
Case 843: 68461803
Case 844: 158524185
Case 845: 1400617775
Case 846: 965601474
Case 847: 667464292
Case 848: 525791050
Case 849: 1276975162
Case 850: 342772365
Case 851: 211262120
Case 852: 269479667
Case 853: 860325520
Case 854: 878227628
Case 855: 3213240
Case 856: 0
Case 857: 1624922133
Case 858: 1738966524
Case 859: 128655131
Case 860: 265041777
Case 861: 617197719
Case 862: 301966056
Case 863: 360193845
Case 864: 42847312
Case 865: 72648625
Case 866: 675055572
Case 867: 362400680
Case 868: 273120498
Case 869: 528235728
Case 870: 608933767
Case 871: 0
Case 872: 176761712
Case 873: 1450185261
Case 874: 416919556
Case 875: 452867584
Case 876: 342276449
Case 877: 189103580
Case 878: 5983167
Case 879: 0
Case 880: 93399640
Case 881: 1410749145
Case 882: 112993426
Case 883: 205941608
Case 884: 253145452
Case 885: 91225609
Case 886: 524800509
Case 887: 259513837
Case 888: 135161770
Case 889: 592622131
Case 890: 267433606
Case 891: 0
Case 892: 677646592
Case 893: 285934428
Case 894: 737036737
Case 895: 25702065
Case 896: 1175042005
Case 897: 6951849
Case 898: 188877755
Case 899: 384226586
Case 900: 939169313
Case 901: 625915542
Case 902: 202884422
Case 903: 521433870
Case 904: 1751297560
Case 905: 365084322
Case 906: 103247891
Case 907: 1202412911
Case 908: 7046091
Case 909: 58027590
Case 910: 531252045
Case 911: 521665970
Case 912: 248903819
Case 913: 262481247
Case 914: 595468700
Case 915: 678819553
Case 916: 1681298002
Case 917: 942813519
Case 918: 201582017
Case 919: 714659159
Case 920: 143926571
Case 921: 615635444
Case 922: 88129238
Case 923: 473109759
Case 924: 844430618
Case 925: 273582067
Case 926: 395456225
Case 927: 0
Case 928: 986242877
Case 929: 503512273
Case 930: 62107500
Case 931: 181835080
Case 932: 1099789782
Case 933: 620126141
Case 934: 632356970
Case 935: 601918928
Case 936: 916160459
Case 937: 1160264814
Case 938: 6478980
Case 939: 1668770243
Case 940: 0
Case 941: 197821448
Case 942: 514147458
Case 943: 613003261
Case 944: 534755999
Case 945: 19050681
Case 946: 708709202
Case 947: 322855328
Case 948: 1641495924
Case 949: 1321230364
Case 950: 500915247
Case 951: 281451894
Case 952: 333675675
Case 953: 244626211
Case 954: 0
Case 955: 30110328
Case 956: 19496840
Case 957: 776501468
Case 958: 908863323
Case 959: 1180347916
Case 960: 1227969756
Case 961: 1282713720
Case 962: 0
Case 963: 565286404
Case 964: 815723193
Case 965: 33940948
Case 966: 613218009
Case 967: 756531450
Case 968: 3540755
Case 969: 758807784
Case 970: 285593484
Case 971: 422999078
Case 972: 467425960
Case 973: 565518348
Case 974: 1413781569
Case 975: 1773291283
Case 976: 456923700
Case 977: 62510986
Case 978: 1149783362
Case 979: 118101901
Case 980: 773684302
Case 981: 129536569
Case 982: 0
Case 983: 45172148
Case 984: 0
Case 985: 976709495
Case 986: 215150870
Case 987: 841753348
Case 988: 28956376
Case 989: 52712276
Case 990: 88207365
Case 991: 1547240922
Case 992: 667274826
Case 993: 350256183
Case 994: 644030383
Case 995: 663700459
Case 996: 151852332
Case 997: 85647495
Case 998: 663339135
Case 999: 37688864
Case 1000: 71927747
Check input and AC output for thousands of problems on uDebug!
Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 12431 - Happy 10/9 Day

Post by Leonid »

How did you handle overflow in this problem? Or there is a way to solve it without using fast exponentiation?

An intermediate step in fast exponentiation can result in numbers that are close to 10^12, and squaring those can be close to 10^24 - but that doesn't fit in long long. An obvious choice would be to use Big Integer, but I was wondering if there is really no way to avoid it?
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12431 - Happy 10/9 Day

Post by brianfry713 »

long long is big enough for my solution.
Check input and AC output for thousands of problems on uDebug!
magurmach
New poster
Posts: 26
Joined: Mon May 14, 2012 8:19 pm

Re: 12431 - Happy 10/9 Day

Post by magurmach »

Providing an important test case which delightfully provided me 5 REs
:P
be careful when n=1
  • 1
    1 10 2 10
Masum
New poster
Posts: 9
Joined: Tue Jul 10, 2012 11:39 am

Re: 12431 - Happy 10/9 Day

Post by Masum »

There is a solution except matrix exponentiation.
Say, you want to find d*(1+b+b^2+b^3+b^4)%M. What can you do? You don't need d at first. Let f(b,n,M) gives you the remainder. We can write it as

Code: Select all

1+b+b^2+b^3+b^4=1+b+b^2(1+b)+b^4=(1+b)*(1+b^2)+b^4
f(b,n,m)=f(b,n/2,m)*(1+b^{n/2})+b^n if n even
and f(b,n,m)=f(b,n/2,m)*(1+b^{ceil(n/2)}) otherwise
So basically it's a simple recursion. Hope you get it
Post Reply

Return to “Volume 124 (12400-12499)”