Problem:


Score : 400 points

Problem Statement

Given is a string S consisting of digits from 1 through 9.

Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:

Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

Constraints

1 ≤ |S| ≤ 200000

S is a string consisting of digits from 1 through 9.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

Sample Input 1

1817181712114

Sample Output 1

3

Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

Sample Input 2

14282668646

Sample Output 2

2

Sample Input 3

2119

Sample Output 3

0

No pairs satisfy the condition.



Sample input:
1817181712114


Sample output:
3

Submission status: Runtime Error

Solution code:
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderDictionary[sum] = remainderDictionary.get(sum,0) + 1

ansDictionary = {0:0,1:0,2:1,3:3,4:6,5:10,6:15,7:21,8:28,9:36,10:45,11:55,12:66,13:78,14:91,15:105,16:120,17:136,18:153,19:171,20:190,21:210,22:231,23:253,24:276,25:300,26:325,27:351,28:378,29:406,30:435,31:465,32:496,33:528,34:561,35:595,36:630,37:666,38:703,39:741,40:780,41:820,42:861,43:903,44:946,45:990,46:1035,47:1081,48:1128,49:1176,50:1225,51:1275,52:1326,53:1378,54:1431,55:1485,56:1540,57:1596,58:1653,59:1711,60:1770,61:1830,62:1891,63:1953,64:2016,65:2080,66:2145,67:2211,68:2278,69:2346,70:2415,71:2485,72:2556,73:2628,74:2701,75:2775,76:2850,77:2926,78:3003,79:3081,80:3160,81:3240,82:3321,83:3403,84:3486,85:3570,86:3655,87:3741,88:3828,89:3916,90:4005,91:4095,92:4186,93:4278,94:4371,95:4465,96:4560,97:4656,98:4753,99:4851,100:4950,101:5050,102:5151,103:5253,104:5356,105:5460,106:5565,107:5671,108:5778,109:5886,110:5995,111:6105,112:6216,113:6328,114:6441,115:6555,116:6670,117:6786,118:6903,119:7021,120:7140,121:7260,122:7381,123:7503,124:7626,125:7750,126:7875,127:8001,128:8128,129:8256,130:8385,131:8515,132:8646,133:8778,134:8911,135:9045,136:9180,137:9316,138:9453,139:9591,140:9730,141:9870,142:10011,143:10153,144:10296,145:10440,146:10585,147:10731,148:10878,149:11026,150:11175,151:11325,152:11476,153:11628,154:11781,155:11935,156:12090,157:12246,158:12403,159:12561,160:12720,161:12880,162:13041,163:13203,164:13366,165:13530,166:13695,167:13861,168:14028,169:14196,170:14365,171:14535,172:14706,173:14878,174:15051,175:15225,176:15400,177:15576,178:15753,179:15931,180:16110,181:16290,182:16471,183:16653,184:16836,185:17020,186:17205,187:17391,188:17578,189:17766,190:17955,191:18145,192:18336,193:18528,194:18721,195:18915,196:19110,197:19306,198:19503,199:19701,200:19900,201:20100,202:20301,203:20503,204:20706,205:20910,206:21115,207:21321,208:21528,209:21736,210:21945,211:22155,212:22366,213:22578,214:22791,215:23005,216:23220,217:23436,218:23653,219:23871,220:24090,221:24310,222:24531,223:24753,224:24976,225:25200,226:25425,227:25651,228:25878,229:26106,230:26335,231:26565,232:26796,233:27028,234:27261,235:27495,236:27730,237:27966,238:28203,239:28441,240:28680,241:28920,242:29161,243:29403,244:29646,245:29890,246:30135,247:30381,248:30628,249:30876,250:31125,251:31375,252:31626,253:31878,254:32131,255:32385,256:32640,257:32896,258:33153,259:33411,260:33670,261:33930,262:34191,263:34453,264:34716,265:34980,266:35245,267:35511,268:35778,269:36046,270:36315,271:36585,272:36856,273:37128,274:37401,275:37675,276:37950,277:38226,278:38503,279:38781,280:39060,281:39340,282:39621,283:39903,284:40186,285:40470,286:40755,287:41041,288:41328,289:41616,290:41905,291:42195,292:42486,293:42778,294:43071,295:43365,296:43660,297:43956,298:44253,299:44551,300:44850,301:45150,302:45451,303:45753,304:46056,305:46360,306:46665,307:46971,308:47278,309:47586,310:47895,311:48205,312:48516,313:48828,314:49141,315:49455,316:49770,317:50086,318:50403,319:50721,320:51040,321:51360,322:51681,323:52003,324:52326,325:52650,326:52975,327:53301,328:53628,329:53956,330:54285,331:54615,332:54946,333:55278,334:55611,335:55945,336:56280,337:56616,338:56953,339:57291,340:57630,341:57970,342:58311,343:58653,344:58996,345:59340,346:59685,347:60031,348:60378,349:60726,350:61075,351:61425,352:61776,353:62128,354:62481,355:62835,356:63190,357:63546,358:63903,359:64261,360:64620,361:64980,362:65341,363:65703,364:66066,365:66430,366:66795,367:67161,368:67528,369:67896,370:68265,371:68635,372:69006,373:69378,374:69751,375:70125,376:70500,377:70876,378:71253,379:71631,380:72010,381:72390,382:72771,383:73153,384:73536,385:73920,386:74305,387:74691,388:75078,389:75466,390:75855,391:76245,392:76636,393:77028,394:77421,395:77815,396:78210,397:78606,398:79003,399:79401,400:79800,401:80200,402:80601,403:81003,404:81406,405:81810,406:82215,407:82621,408:83028,409:83436,410:83845,411:84255,412:84666,413:85078,414:85491,415:85905,416:86320,417:86736,418:87153,419:87571,420:87990,421:88410,422:88831,423:89253,424:89676,425:90100,426:90525,427:90951,428:91378,429:91806,430:92235,431:92665,432:93096,433:93528,434:93961,435:94395,436:94830,437:95266,438:95703,439:96141,440:96580,441:97020,442:97461,443:97903,444:98346,445:98790,446:99235,447:99681,448:100128,449:100576,450:101025,451:101475,452:101926,453:102378,454:102831,455:103285,456:103740,457:104196,458:104653,459:105111,460:105570,461:106030,462:106491,463:106953,464:107416,465:107880,466:108345,467:108811,468:109278,469:109746,470:110215,471:110685,472:111156,473:111628,474:112101,475:112575,476:113050,477:113526,478:114003,479:114481,480:114960,481:115440,482:115921,483:116403,484:116886,485:117370,486:117855,487:118341,488:118828,489:119316,490:119805,491:120295,492:120786,493:121278,494:121771,495:122265,496:122760,497:123256,498:123753,499:124251,500:124750,501:125250,502:125751,503:126253,504:126756,505:127260,506:127765,507:128271,508:128778,509:129286,510:129795,511:130305,512:130816,513:131328,514:131841,515:132355,516:132870,517:133386,518:133903,519:134421,520:134940,521:135460,522:135981,523:136503,524:137026,525:137550,526:138075,527:138601,528:139128,529:139656,530:140185,531:140715,532:141246,533:141778,534:142311,535:142845,536:143380,537:143916,538:144453,539:144991,540:145530,541:146070,542:146611,543:147153,544:147696,545:148240,546:148785,547:149331,548:149878,549:150426,550:150975,551:151525,552:152076,553:152628,554:153181,555:153735,556:154290,557:154846,558:155403,559:155961,560:156520,561:157080,562:157641,563:158203,564:158766,565:159330,566:159895,567:160461,568:161028,569:161596,570:162165,571:162735,572:163306,573:163878,574:164451,575:165025,576:165600,577:166176,578:166753,579:167331,580:167910,581:168490,582:169071,583:169653,584:170236,585:170820,586:171405,587:171991,588:172578,589:173166,590:173755,591:174345,592:174936,593:175528,594:176121,595:176715,596:177310,597:177906,598:178503,599:179101,600:179700,601:180300,602:180901,603:181503,604:182106,605:182710,606:183315,607:183921,608:184528,609:185136,610:185745,611:186355,612:186966,613:187578,614:188191,615:188805,616:189420,617:190036,618:190653,619:191271,620:191890,621:192510,622:193131,623:193753,624:194376,625:195000,626:195625,627:196251,628:196878,629:197506,630:198135,631:198765,632:199396,633:200028,634:200661,635:201295,636:201930,637:202566,638:203203,639:203841,640:204480,641:205120,642:205761,643:206403,644:207046,645:207690,646:208335,647:208981,648:209628,649:210276,650:210925,651:211575,652:212226,653:212878,654:213531,655:214185,656:214840,657:215496,658:216153,659:216811,660:217470,661:218130,662:218791,663:219453,664:220116,665:220780,666:221445,667:222111,668:222778,669:223446,670:224115,671:224785,672:225456,673:226128,674:226801,675:227475,676:228150,677:228826,678:229503,679:230181,680:230860,681:231540,682:232221,683:232903,684:233586,685:234270,686:234955,687:235641,688:236328,689:237016,690:237705,691:238395,692:239086,693:239778,694:240471,695:241165,696:241860,697:242556,698:243253,699:243951,700:244650,701:245350,702:246051,703:246753,704:247456,705:248160,706:248865,707:249571,708:250278,709:250986,710:251695,711:252405,712:253116,713:253828,714:254541,715:255255,716:255970,717:256686,718:257403,719:258121,720:258840,721:259560,722:260281,723:261003,724:261726,725:262450,726:263175,727:263901,728:264628,729:265356,730:266085,731:266815,732:267546,733:268278,734:269011,735:269745,736:270480,737:271216,738:271953,739:272691,740:273430,741:274170,742:274911,743:275653,744:276396,745:277140,746:277885,747:278631,748:279378,749:280126,750:280875,751:281625,752:282376,753:283128,754:283881,755:284635,756:285390,757:286146,758:286903,759:287661,760:288420,761:289180,762:289941,763:290703,764:291466,765:292230,766:292995,767:293761,768:294528,769:295296,770:296065,771:296835,772:297606,773:298378,774:299151,775:299925,776:300700,777:301476,778:302253,779:303031,780:303810,781:304590,782:305371,783:306153,784:306936,785:307720,786:308505,787:309291,788:310078,789:310866,790:311655,791:312445,792:313236,793:314028,794:314821,795:315615,796:316410,797:317206,798:318003,799:318801,800:319600,801:320400,802:321201,803:322003,804:322806,805:323610,806:324415,807:325221,808:326028,809:326836,810:327645,811:328455,812:329266,813:330078,814:330891,815:331705,816:332520,817:333336,818:334153,819:334971,820:335790,821:336610,822:337431,823:338253,824:339076,825:339900,826:340725,827:341551,828:342378,829:343206,830:344035,831:344865,832:345696,833:346528,834:347361,835:348195,836:349030,837:349866,838:350703,839:351541,840:352380,841:353220,842:354061,843:354903,844:355746,845:356590,846:357435,847:358281,848:359128,849:359976,850:360825,851:361675,852:362526,853:363378,854:364231,855:365085,856:365940,857:366796,858:367653,859:368511,860:369370,861:370230,862:371091,863:371953,864:372816,865:373680,866:374545,867:375411,868:376278,869:377146,870:378015,871:378885,872:379756,873:380628,874:381501,875:382375,876:383250,877:384126,878:385003,879:385881,880:386760,881:387640,882:388521,883:389403,884:390286,885:391170,886:392055,887:392941,888:393828,889:394716,890:395605,891:396495,892:397386,893:398278,894:399171,895:400065,896:400960,897:401856,898:402753,899:403651,900:404550,901:405450,902:406351,903:407253,904:408156,905:409060,906:409965,907:410871,908:411778,909:412686,910:413595,911:414505,912:415416,913:416328,914:417241,915:418155,916:419070,917:419986,918:420903,919:421821,920:422740,921:423660,922:424581,923:425503,924:426426,925:427350,926:428275,927:429201,928:430128,929:431056,930:431985,931:432915,932:433846,933:434778,934:435711,935:436645,936:437580,937:438516,938:439453,939:440391,940:441330,941:442270,942:443211,943:444153,944:445096,945:446040,946:446985,947:447931,948:448878,949:449826,950:450775,951:451725,952:452676,953:453628,954:454581,955:455535,956:456490,957:457446,958:458403,959:459361,960:460320,961:461280,962:462241,963:463203,964:464166,965:465130,966:466095,967:467061,968:468028,969:468996,970:469965,971:470935,972:471906,973:472878,974:473851,975:474825,976:475800,977:476776,978:477753,979:478731,980:479710,981:480690,982:481671,983:482653,984:483636,985:484620,986:485605,987:486591,988:487578,989:488566,990:489555,991:490545,992:491536,993:492528,994:493521,995:494515,996:495510,997:496506,998:497503,999:498501,1000:499500,1001:500500,1002:501501,1003:502503,1004:503506,1005:504510,1006:505515,1007:506521,1008:507528,1009:508536,1010:509545,1011:510555,1012:511566,1013:512578,1014:513591,1015:514605,1016:515620,1017:516636,1018:517653,1019:518671,1020:519690,1021:520710,1022:521731,1023:522753,1024:523776,1025:524800,1026:525825,1027:526851,1028:527878,1029:528906,1030:529935,1031:530965,1032:531996,1033:533028,1034:534061,1035:535095,1036:536130,1037:537166,1038:538203,1039:539241,1040:540280,1041:541320,1042:542361,1043:543403,1044:544446,1045:545490,1046:546535,1047:547581,1048:548628,1049:549676,1050:550725,1051:551775,1052:552826,1053:553878,1054:554931,1055:555985,1056:557040,1057:558096,1058:559153,1059:560211,1060:561270,1061:562330,1062:563391,1063:564453,1064:565516,1065:566580,1066:567645,1067:568711,1068:569778,1069:570846,1070:571915,1071:572985,1072:574056,1073:575128,1074:576201,1075:577275,1076:578350,1077:579426,1078:580503,1079:581581,1080:582660,1081:583740,1082:584821,1083:585903,1084:586986,1085:588070,1086:589155,1087:590241,1088:591328,1089:592416,1090:593505,1091:594595,1092:595686,1093:596778,1094:597871,1095:598965,1096:600060,1097:601156,1098:602253,1099:603351,1100:604450,1101:605550,1102:606651,1103:607753,1104:608856,1105:609960,1106:611065,1107:612171,1108:613278,1109:614386,1110:615495,1111:616605,1112:617716,1113:618828,1114:619941,1115:621055,1116:622170,1117:623286,1118:624403,1119:625521,1120:626640,1121:627760,1122:628881,1123:630003,1124:631126,1125:632250,1126:633375,1127:634501,1128:635628,1129:636756,1130:637885,1131:639015,1132:640146,1133:641278,1134:642411,1135:643545,1136:644680,1137:645816,1138:646953,1139:648091,1140:649230,1141:650370,1142:651511,1143:652653,1144:653796,1145:654940,1146:656085,1147:657231,1148:658378,1149:659526,1150:660675,1151:661825,1152:662976,1153:664128,1154:665281,1155:666435,1156:667590,1157:668746,1158:669903,1159:671061,1160:672220,1161:673380,1162:674541,1163:675703,1164:676866,1165:678030,1166:679195,1167:680361,1168:681528,1169:682696,1170:683865,1171:685035,1172:686206,1173:687378,1174:688551,1175:689725,1176:690900,1177:692076,1178:693253,1179:694431,1180:695610,1181:696790,1182:697971,1183:699153,1184:700336,1185:701520,1186:702705,1187:703891,1188:705078,1189:706266,1190:707455,1191:708645,1192:709836,1193:711028,1194:712221,1195:713415,1196:714610,1197:715806,1198:717003,1199:718201,1200:719400,1201:720600,1202:721801,1203:723003,1204:724206,1205:725410,1206:726615,1207:727821,1208:729028,1209:730236,1210:731445,1211:732655,1212:733866,1213:735078,1214:736291,1215:737505,1216:738720,1217:739936,1218:741153,1219:742371,1220:743590,1221:744810,1222:746031,1223:747253,1224:748476,1225:749700,1226:750925,1227:752151,1228:753378,1229:754606,1230:755835,1231:757065,1232:758296,1233:759528,1234:760761,1235:761995,1236:763230,1237:764466,1238:765703,1239:766941,1240:768180,1241:769420,1242:770661,1243:771903,1244:773146,1245:774390,1246:775635,1247:776881,1248:778128,1249:779376,1250:780625,1251:781875,1252:783126,1253:784378,1254:785631,1255:786885,1256:788140,1257:789396,1258:790653,1259:791911,1260:793170,1261:794430,1262:795691,1263:796953,1264:798216,1265:799480,1266:800745,1267:802011,1268:803278,1269:804546,1270:805815,1271:807085,1272:808356,1273:809628,1274:810901,1275:812175,1276:813450,1277:814726,1278:816003,1279:817281,1280:818560,1281:819840,1282:821121,1283:822403,1284:823686,1285:824970,1286:826255,1287:827541,1288:828828,1289:830116,1290:831405,1291:832695,1292:833986,1293:835278,1294:836571,1295:837865,1296:839160,1297:840456,1298:841753,1299:843051,1300:844350,1301:845650,1302:846951,1303:848253,1304:849556,1305:850860,1306:852165,1307:853471,1308:854778,1309:856086,1310:857395,1311:858705,1312:860016,1313:861328,1314:862641,1315:863955,1316:865270,1317:866586,1318:867903,1319:869221,1320:870540,1321:871860,1322:873181,1323:874503,1324:875826,1325:877150,1326:878475,1327:879801,1328:881128,1329:882456,1330:883785,1331:885115,1332:886446,1333:887778,1334:889111,1335:890445,1336:891780,1337:893116,1338:894453,1339:895791,1340:897130,1341:898470,1342:899811,1343:901153,1344:902496,1345:903840,1346:905185,1347:906531,1348:907878,1349:909226,1350:910575,1351:911925,1352:913276,1353:914628,1354:915981,1355:917335,1356:918690,1357:920046,1358:921403,1359:922761,1360:924120,1361:925480,1362:926841,1363:928203,1364:929566,1365:930930,1366:932295,1367:933661,1368:935028,1369:936396,1370:937765,1371:939135,1372:940506,1373:941878,1374:943251,1375:944625,1376:946000,1377:947376,1378:948753,1379:950131,1380:951510,1381:952890,1382:954271,1383:955653,1384:957036,1385:958420,1386:959805,1387:961191,1388:962578,1389:963966,1390:965355,1391:966745,1392:968136,1393:969528,1394:970921,1395:972315,1396:973710,1397:975106,1398:976503,1399:977901,1400:979300,1401:980700,1402:982101,1403:983503,1404:984906,1405:986310,1406:987715,1407:989121,1408:990528,1409:991936,1410:993345,1411:994755,1412:996166,1413:997578,1414:998991,1415:1000405,1416:1001820,1417:1003236,1418:1004653,1419:1006071,1420:1007490,1421:1008910,1422:1010331,1423:1011753,1424:1013176,1425:1014600,1426:1016025,1427:1017451,1428:1018878,1429:1020306,1430:1021735,1431:1023165,1432:1024596,1433:1026028,1434:1027461,1435:1028895,1436:1030330,1437:1031766,1438:1033203,1439:1034641,1440:1036080,1441:1037520,1442:1038961,1443:1040403,1444:1041846,1445:1043290,1446:1044735,1447:1046181,1448:1047628,1449:1049076,1450:1050525,1451:1051975,1452:1053426,1453:1054878,1454:1056331,1455:1057785,1456:1059240,1457:1060696,1458:1062153,1459:1063611,1460:1065070,1461:1066530,1462:1067991,1463:1069453,1464:1070916,1465:1072380,1466:1073845,1467:1075311,1468:1076778,1469:1078246,1470:1079715,1471:1081185,1472:1082656,1473:1084128,1474:1085601,1475:1087075,1476:1088550,1477:1090026,1478:1091503,1479:1092981,1480:1094460,1481:1095940,1482:1097421,1483:1098903,1484:1100386,1485:1101870,1486:1103355,1487:1104841,1488:1106328,1489:1107816,1490:1109305,1491:1110795,1492:1112286,1493:1113778,1494:1115271,1495:1116765,1496:1118260,1497:1119756,1498:1121253,1499:1122751,1500:1124250,1501:1125750,1502:1127251,1503:1128753,1504:1130256,1505:1131760,1506:1133265,1507:1134771,1508:1136278,1509:1137786,1510:1139295,1511:1140805,1512:1142316,1513:1143828,1514:1145341,1515:1146855,1516:1148370,1517:1149886,1518:1151403,1519:1152921,1520:1154440,1521:1155960,1522:1157481,1523:1159003,1524:1160526,1525:1162050,1526:1163575,1527:1165101,1528:1166628,1529:1168156,1530:1169685,1531:1171215,1532:1172746,1533:1174278,1534:1175811,1535:1177345,1536:1178880,1537:1180416,1538:1181953,1539:1183491,1540:1185030,1541:1186570,1542:1188111,1543:1189653,1544:1191196,1545:1192740,1546:1194285,1547:1195831,1548:1197378,1549:1198926,1550:1200475,1551:1202025,1552:1203576,1553:1205128,1554:1206681,1555:1208235,1556:1209790,1557:1211346,1558:1212903,1559:1214461,1560:1216020,1561:1217580,1562:1219141,1563:1220703,1564:1222266,1565:1223830,1566:1225395,1567:1226961,1568:1228528,1569:1230096,1570:1231665,1571:1233235,1572:1234806,1573:1236378,1574:1237951,1575:1239525,1576:1241100,1577:1242676,1578:1244253,1579:1245831,1580:1247410,1581:1248990,1582:1250571,1583:1252153,1584:1253736,1585:1255320,1586:1256905,1587:1258491,1588:1260078,1589:1261666,1590:1263255,1591:1264845,1592:1266436,1593:1268028,1594:1269621,1595:1271215,1596:1272810,1597:1274406,1598:1276003,1599:1277601,1600:1279200,1601:1280800,1602:1282401,1603:1284003,1604:1285606,1605:1287210,1606:1288815,1607:1290421,1608:1292028,1609:1293636,1610:1295245,1611:1296855,1612:1298466,1613:1300078,1614:1301691,1615:1303305,1616:1304920,1617:1306536,1618:1308153,1619:1309771,1620:1311390,1621:1313010,1622:1314631,1623:1316253,1624:1317876,1625:1319500,1626:1321125,1627:1322751,1628:1324378,1629:1326006,1630:1327635,1631:1329265,1632:1330896,1633:1332528,1634:1334161,1635:1335795,1636:1337430,1637:1339066,1638:1340703,1639:1342341,1640:1343980,1641:1345620,1642:1347261,1643:1348903,1644:1350546,1645:1352190,1646:1353835,1647:1355481,1648:1357128,1649:1358776,1650:1360425,1651:1362075,1652:1363726,1653:1365378,1654:1367031,1655:1368685,1656:1370340,1657:1371996,1658:1373653,1659:1375311,1660:1376970,1661:1378630,1662:1380291,1663:1381953,1664:1383616,1665:1385280,1666:1386945,1667:1388611,1668:1390278,1669:1391946,1670:1393615,1671:1395285,1672:1396956,1673:1398628,1674:1400301,1675:1401975,1676:1403650,1677:1405326,1678:1407003,1679:1408681,1680:1410360,1681:1412040,1682:1413721,1683:1415403,1684:1417086,1685:1418770,1686:1420455,1687:1422141,1688:1423828,1689:1425516,1690:1427205,1691:1428895,1692:1430586,1693:1432278,1694:1433971,1695:1435665,1696:1437360,1697:1439056,1698:1440753,1699:1442451,1700:1444150,1701:1445850,1702:1447551,1703:1449253,1704:1450956,1705:1452660,1706:1454365,1707:1456071,1708:1457778,1709:1459486,1710:1461195,1711:1462905,1712:1464616,1713:1466328,1714:1468041,1715:1469755,1716:1471470,1717:1473186,1718:1474903,1719:1476621,1720:1478340,1721:1480060,1722:1481781,1723:1483503,1724:1485226,1725:1486950,1726:1488675,1727:1490401,1728:1492128,1729:1493856,1730:1495585,1731:1497315,1732:1499046,1733:1500778,1734:1502511,1735:1504245,1736:1505980,1737:1507716,1738:1509453,1739:1511191,1740:1512930,1741:1514670,1742:1516411,1743:1518153,1744:1519896,1745:1521640,1746:1523385,1747:1525131,1748:1526878,1749:1528626,1750:1530375,1751:1532125,1752:1533876,1753:1535628,1754:1537381,1755:1539135,1756:1540890,1757:1542646,1758:1544403,1759:1546161,1760:1547920,1761:1549680,1762:1551441,1763:1553203,1764:1554966,1765:1556730,1766:1558495,1767:1560261,1768:1562028,1769:1563796,1770:1565565,1771:1567335,1772:1569106,1773:1570878,1774:1572651,1775:1574425,1776:1576200,1777:1577976,1778:1579753,1779:1581531,1780:1583310,1781:1585090,1782:1586871,1783:1588653,1784:1590436,1785:1592220,1786:1594005,1787:1595791,1788:1597578,1789:1599366,1790:1601155,1791:1602945,1792:1604736,1793:1606528,1794:1608321,1795:1610115,1796:1611910,1797:1613706,1798:1615503,1799:1617301,1800:1619100,1801:1620900,1802:1622701,1803:1624503,1804:1626306,1805:1628110,1806:1629915,1807:1631721,1808:1633528,1809:1635336,1810:1637145,1811:1638955,1812:1640766,1813:1642578,1814:1644391,1815:1646205,1816:1648020,1817:1649836,1818:1651653,1819:1653471,1820:1655290,1821:1657110,1822:1658931,1823:1660753,1824:1662576,1825:1664400,1826:1666225,1827:1668051,1828:1669878,1829:1671706,1830:1673535,1831:1675365,1832:1677196,1833:1679028,1834:1680861,1835:1682695,1836:1684530,1837:1686366,1838:1688203,1839:1690041,1840:1691880,1841:1693720,1842:1695561,1843:1697403,1844:1699246,1845:1701090,1846:1702935,1847:1704781,1848:1706628,1849:1708476,1850:1710325,1851:1712175,1852:1714026,1853:1715878,1854:1717731,1855:1719585,1856:1721440,1857:1723296,1858:1725153,1859:1727011,1860:1728870,1861:1730730,1862:1732591,1863:1734453,1864:1736316,1865:1738180,1866:1740045,1867:1741911,1868:1743778,1869:1745646,1870:1747515,1871:1749385,1872:1751256,1873:1753128,1874:1755001,1875:1756875,1876:1758750,1877:1760626,1878:1762503,1879:1764381,1880:1766260,1881:1768140,1882:1770021,1883:1771903,1884:1773786,1885:1775670,1886:1777555,1887:1779441,1888:1781328,1889:1783216,1890:1785105,1891:1786995,1892:1788886,1893:1790778,1894:1792671,1895:1794565,1896:1796460,1897:1798356,1898:1800253,1899:1802151,1900:1804050,1901:1805950,1902:1807851,1903:1809753,1904:1811656,1905:1813560,1906:1815465,1907:1817371,1908:1819278,1909:1821186,1910:1823095,1911:1825005,1912:1826916,1913:1828828,1914:1830741,1915:1832655,1916:1834570,1917:1836486,1918:1838403,1919:1840321,1920:1842240,1921:1844160,1922:1846081,1923:1848003,1924:1849926,1925:1851850,1926:1853775,1927:1855701,1928:1857628,1929:1859556,1930:1861485,1931:1863415,1932:1865346,1933:1867278,1934:1869211,1935:1871145,1936:1873080,1937:1875016,1938:1876953,1939:1878891,1940:1880830,1941:1882770,1942:1884711,1943:1886653,1944:1888596,1945:1890540,1946:1892485,1947:1894431,1948:1896378,1949:1898326,1950:1900275,1951:1902225,1952:1904176,1953:1906128,1954:1908081,1955:1910035,1956:1911990,1957:1913946,1958:1915903,1959:1917861,1960:1919820,1961:1921780,1962:1923741,1963:1925703,1964:1927666,1965:1929630,1966:1931595,1967:1933561,1968:1935528,1969:1937496,1970:1939465,1971:1941435,1972:1943406,1973:1945378,1974:1947351,1975:1949325,1976:1951300,1977:1953276,1978:1955253,1979:1957231,1980:1959210,1981:1961190,1982:1963171,1983:1965153,1984:1967136,1985:1969120,1986:1971105,1987:1973091,1988:1975078,1989:1977066,1990:1979055,1991:1981045,1992:1983036,1993:1985028,1994:1987021,1995:1989015,1996:1991010,1997:1993006,1998:1995003,1999:1997001,2000:1999000,2001:2001000,2002:2003001,2003:2005003,2004:2007006,2005:2009010,2006:2011015,2007:2013021,2008:2015028,2009:2017036,2010:2019045,2011:2021055,2012:2023066,2013:2025078,2014:2027091,2015:2029105,2016:2031120,2017:2033136,2018:2035153}
ans = 0
for i in remainderDictionary:
  ans += ansDictionary[ remainderDictionary[i] ]
print(ans)