1 1 2 0 3 1 4 1 5 2 6 1 7 4 8 2 9 3 10 2 11 11 12 2 13 17 14 3 15 5 16 5 17 37 18 3 19 53 20 5 21 12 22 7 23 103 24 5 25 70 26 10 27 42 28 11 29 255 30 4 31 339 32 23 33 59 34 22 35 130 36 11 37 759 38 32 39 115 40 22 41 1259 42 10 43 1609 44 44 45 94 46 64 47 2589 48 22 49 1674 50 40 51 385 52 84 53 5119 54 30 55 1309 56 79 57 665 58 162 59 9791 60 18 61 12075 62 217 63 556 64 276 65 3511 66 35 67 22249 68 272 69 1845 70 62 71 32991 72 77 73 40025 74 496 75 854 76 468 77 14108 78 68 79 70487 80 236 81 5331 82 833 83 101697 84 67 85 20502 86 1070 87 7342 88 735 89 173681 90 60 91 48280 92 1292 93 11276 94 1737 95 45803 96 232 97 345855 98 880 99 9787 100 658 101 483329 102 197 103 570077 104 1948 105 1719 106 3466 107 789639 108 387 109 927405 110 558 111 37979 112 1796 113 1274117 114 350 115 203452 116 5141 117 33431 118 6680 119 434985 120 183 121 1248879 122 8252 123 81041 124 7901 125 495936 126 333 127 3725409 128 11564 129 116823 130 1446 131 5010687 132 539 133 1183268 134 15289 135 27780 136 11264 137 7755775 138 893 139 8953855 140 1393 141 237151 142 22738 143 3170691 144 1602 145 1526479 146 27617 147 91954 148 26712 149 18108417 150 493 151 20792119 152 25112 153 301595 154 5605 155 2853360 156 1440 157 31316313 158 48803 159 651382 160 9449 161 7560793 162 3081 163 46828031 164 57165 165 48574 166 70545 167 61000703 168 1368 169 36920000 170 8285 171 821897 172 82531 173 90198445 174 3428 175 2235528 176 50410 177 1696838 178 120757 179 132535701 180 1254 181 150473567 182 19048 183 2310668 184 111428 185 16705246 186 5360 187 56982856 188 168073 189 705360 190 18399 191 281138047 192 8657 193 317984255 194 241062 195 203683 196 67980 197 406072421 198 5000 199 458482687 200 44138 201 5675338 202 337234 203 92488402 204 7648 205 50262596 206 397949 207 5276577 208 210828 209 211971049 210 1155 211 938748851 212 463856 213 10115827 214 551695 215 85494689 216 18835 217 201093592 218 648192 219 13427260 220 37862 221 454400240 222 17639 223 1886061683 224 193864 225 1672483 226 891170 227 2370513985 228 17128 229 2655684607 230 81894 231 1486046 232 837752 233 3328423935 234 16928 235 238907030 236 1213748 237 30736746 238 171352 239 4654300705 240 6775 241 5200062975 242 653389 243 41039497 244 1655216 245 65889560 246 36718 247 1930179839 248 1567828 249 52513302 250 252912 251 8994926601 252 16007 253 2414181816 254 2610903 255 2653991 256 2824974 257 12434895063 258 53557 259 1802036535 260 156541 261 65062115 262 3513253 263 17129359743 264 34527 265 1033886267 266 466531 267 114663749 268 4081914 269 23515017983 270 14734 271 26114971539 272 2725764 273 8844889 274 5441195 275 537576595 276 72278 277 35692320959 278 6282860 279 141838338 280 149739 281 43879178239 282 106865 283 48626519093 284 7293951 285 8551942 286 1235409 287 7062961137 288 159340 289 35366748341 290 616462 291 312726825 292 9693300 293 80860419135 294 48074 295 4136979114 296 9220649 297 124660313 298 12716503 299 28085479988 300 30996 301 13644385015 302 14603108 303 508885252 304 8745311 305 6467915010 306 142796 307 162560142889 308 1129935 309 646923766 310 1156396 311 197902232211 312 143581 313 218259394655 314 22002894 315 7728430 316 22263996 317 265235325351 318 292830 319 64194232984 320 2277800 321 1038655100 322 2991702 323 99025079001 324 424480 325 5561754057 326 32912346 327 1311923041 328 27838877 329 48752088805 330 27533 331 519999315039 332 38116475 333 1280825303 334 42881915 335 23725955156 336 135251 337 691031243769 338 19347970 339 2080461172 340 2003264 341 177435563452 342 387731 343 101763793406 344 47437886 345 74886386 346 63424241 347 1104119260917 348 528631 349 1211664556453 350 1034811 351 1132224371 352 24884033 353 1458093818815 354 762838 355 54703020088 356 83466187 357 214275056 358 93216647 359 1921228932215 360 125173 361 1130652999012 362 105840729 363 1396974953 364 6661918 365 82355272671 366 1045915 367 2765837686783 368 75914818 369 5044123832 370 6819321 371 299253431478 372 992568 373 3626048321047 374 22235133 375 370402124 376 133049229 377 1037747552595 378 360239 379 4743946406975 380 6406151 381 9856822500 382 197813970 383 5668311927091 384 1964078 385 3999646426 386 223752966 387 9766540802 388 228413063 389 7391018303853 390 117910 391 2226427301903 392 39652544 393 15140843785 394 285769620 395 272296342742 396 952676 397 10496798204735 398 322670277 399 913829574 400 21730489 401 12493440407999 402 2570103 403 3175381853970 404 372255185 405 956577808 406 36877208 407 3125281962959 408 1776179 409 17654554915429 410 20638611 411 28493912956 412 473576517 413 1665504156110 414 2395266 415 589816145139 416 197458822 417 35075639501 418 82844713 419 27077619952639 420 113427 421 29478499862527 422 660862470 423 35047686758 424 579005534 425 358829600997 426 4564818 427 2895562080867 428 761395921 429 3685557241 430 35201417 431 44950311372459 432 6201200 433 48880168540671 434 80397012 435 1403035033 436 962352616 437 16221740799232 438 6089936 439 62784376939519 440 18888955 441 7776166512 442 177171001 443 74119976256079 444 5730672 445 1819140903051 446 1328072719 447 97108205425 448 181969041 449 94946245905983 450 849922 451 18636655721525 452 1528027005 453 118573093917 454 1669319142 455 52316871512 456 5683443 457 131765175508647 458 1870200280 459 57996197201 460 55436111 461 155064887475475 462 831204 463 168174207315549 464 1404970646 465 3481685071 466 2344113611 467 197711788129023 468 5602219 469 14457328696133 470 98922804 471 214256883294 472 2329670679 473 44060892438903 474 13972925 475 2383095988644 476 159018392 477 216417906783 478 3278191140 479 319989057373737 480 1548591 481 74467616287974 482 3662697070 483 13413228760 484 1028815621 485 7724168761014 486 21138498 487 439684162112801 488 3648908181 489 383027039622 490 30810396 491 514914277284171 492 17057236 493 147565324274056 494 753621869 495 3105802371 496 3473378124 497 40624081130051 498 23846164 499 704890732521791 500 276001102 501 561001545443 502 6336484115 503 823987858076149 504 5262952 505 15574785014709 506 947160458 507 186029665326 508 7267119611 509 1040243150979583 510 1410955 511 67374774329042 512 8304924928 513 347066203372 514 8760412289 515 22004635415087 516 29125003 517 232536838072480 518 726359407 519 986379365397 520 148919255 521 1651411233432319 522 28754007 523 1782753988462273 524 11173369358 525 3017047963 526 12068494588 527 540892662373662 528 16435481 529 1208674430874897 530 431723521 531 1210970026503 532 674238205 533 530448790622458 534 52252518 535 43503040617404 536 13456432594 537 1718250313655 538 16568564584 539 33751094824811 540 4896432 541 3527818029248523 542 18400851984 543 2063341676981 544 7958265548 545 60884964632003 546 4787348 547 4418269447841279 548 21054904966 549 2108855395219 550 240937097 551 1400849901051578 552 48207474 553 295502896382606 554 25150607098 555 45293366713 556 25928917823 557 6412408569364171 558 62557325 559 1366096412056285 560 141624115 561 237813551282 562 30920619422 563 8005917788147073 564 80893386 565 118207823849233 566 34266571129 567 304187659330 568 31131805962 569 9984057165275479 570 4564335 571 10743948315198451 572 2719885629 573 5079603399296 574 2862250769 575 79165680664174 576 143204216 577 13378670620050079 578 18575052900 579 6065868953369 580 1024212129 581 768135175666884 582 143464846 583 2485468070587907 584 46947340024 585 40053505082 586 56986249209 587 19235606795358219 588 26632632 589 5572245601046835 590 1741478292 591 8627378828491 592 44723164730 593 23883607699335167 594 60350140 595 5131063278544 596 71919369842 597 10275732704156 598 11001806028 599 29623482180174911 600 14628830 601 31821031242764409 602 5544009043 603 10578891412318 604 87846433368 605 70666911249921 606 233592751 607 39413984631175423 608 42725570642 609 502223120818 610 2729971978 611 8504821217990881 612 130736146 613 48769012012411665 614 114576090352 615 223805213412 616 2566297309 617 56177664191435967 618 297766489 619 60283911416633535 620 2532252136 621 9518911096367 622 139489882855 623 3089213878636675 624 129631458 625 823629076511496 626 153840560921 627 1579528855688 628 158888100270 629 21088918594767498 630 4385828 631 91840127431009791 632 155980617710 633 28835355423537 634 186956586438 635 1106788762891566 636 350253545 637 1049025820137872 638 25344537881 639 29811706776422 640 6675672888 641 130050574409982719 642 478495580 643 139377036381734911 644 9804499409 645 483354431251 646 38664764190 647 160034561092715411 648 600190447 649 23349273924940863 650 2460922582 651 1543331817535 652 284295011615 653 196748899676004247 654 605865725 655 2050889524625627 656 219656868404 657 49510417461265 658 19911836879 659 241664733752111549 660 13624889 661 258757435450198015 662 366563853640 663 4700765868003 664 338915830208 665 41221489883651 666 555163906 667 89930677173297281 668 416621229609 669 78696268426434 670 10090617220 671 48041039054057793 672 121599189 673 389103956543205483 674 487146312277 675 1526398981229 676 136921278952 677 445433800804233381 678 961833819 679 18431333952637282 680 5943306065 681 109339755820552 682 70202312051 683 545187241854615561 684 552711180 685 5086553251846936 686 51712408784 687 128746717677360 688 473071356136 689 114971992704962300 690 37973052 691 712827068077888959 692 733082747722 693 1342908840750 694 778396943643 695 6855614426504661 696 878062026 697 205972468571383731 698 854224508464 699 178140926095988 700 2335364760 701 994532043192721629 702 543757379 703 273489863201030389 704 198603652720 705 2141988599728 706 1027978161441 707 43820280663083047 708 1404731739 709 1296011538852931583 710 23379078676 711 217991756924700 712 1049955781007 713 415992301106162065 714 110473263 715 300909163934236 716 1277909417782 717 288495359254150 718 1354535227283 719 1800805246224619945 720 113420627 721 67143446825854496 722 594286951734 723 338350718941165 724 1534902393189 725 8865755303692383 726 675227808 727 2339169495422851817 728 33095546939 729 396918663129573 730 35280611784 731 617471759992596806 732 2202845762 733 2843551628300021779 734 1950087748782 735 407327729331 736 959107471376 737 391204172885550358 738 2163105173 739 3454021034668672125 740 32633156957 741 37655532736912 742 123143425451 743 3930517799844061183 744 2167118472 745 29579693663194755 746 2556658627759 747 568004681826591 748 173771535796 749 155760842993836935 750 184544317 751 5084659675675275559 752 2085603629527 753 743761676245484 754 408713098447 755 39397904734589371 756 509787836 757 6162297935619707409 758 3344954489903 759 52481416814595 760 31783218891 761 7001942144914244607 762 4596226175 763 235874437198898557 764 3782520972130 765 3837433420453 766 3996791451735 767 1348160357906753719 768 5596831656 769 9031248611609428977 770 2067693366 771 1184480412208741 772 4517788623750 773 10251877366749901977 774 4183490558 775 38214770863907087 776 4482950270579 777 36638795461619 778 5211619266175 779 3081516925103505472 780 108765149 781 1504519517959989648 782 871176258276 783 825388698967376 784 400747370222 785 92083726669525290 786 7069880771 787 15937437895497941055 788 6427883083578 789 1876553177614241 790 117454560813 791 534984637346710795 792 2090839994 793 2978922470027521466 794 7401826956713 795 17855192649680 796 7657321888212 797 21790951389243426815 798 462417204 799 5154577577482532359 800 173739878186 801 2291943879156658 802 8809895417219 803 2909384197923751497 804 8107087836 805 1947115705198912 806 1252904430150 807 2958066938097153 808 9062947536163 809 31638700427605669253 810 475852273 811 33658554486099838719 812 363405264970 813 3438880035969333 814 1244322546049 815 211888715254583121 816 5135099024 817 9895614999478815798 818 12449683839254 819 31697171570633 820 160445216823 821 45814169485295430239 822 13345840781 823 48717561261903748021 824 12820726050659 825 7650057616962 826 690284222094 827 55076044155484162047 828 7928011450 829 58553713102334907283 830 255535285886 831 5385916447450995 832 3900189164220 833 477169105726334974 834 16453609066 835 366272245462604488 836 1150129821802 837 3288439027098788 838 19095339977429 839 79441670148851154111 840 100882847 841 45720680658027537774 842 20788601257527 843 7244781482263130 844 21507989022018 845 78940800203694308 846 14903730986 847 294099518807305020 848 17267010805557 849 8396076820826641 850 155416820037 851 31223883359667232814 852 18718078778 853 121411173513469673535 854 1202874372445 855 30532610473134 856 25409015904419 857 136968296262749272063 858 1858532541 859 145464242180631569963 860 345752547966 861 262981910253799 862 31700572392790 863 164036365999875151519 864 29746050371 865 822657161851570325 866 34472272765829 867 3609812107624240 868 1113765763008 869 19978443726778974174 870 685762375 871 29840954150242898020 872 35603886121422 873 13729326582380738 874 6347418655105 875 30468069091478604 876 28254795364 877 249267110556045123599 878 44278931506410 879 17422270732543922 880 152887795811 881 280754734449641432203 882 3833652877 883 297930806826997905473 884 3421433939249 885 132619866947998 886 52274061251385 887 335433994275434973759 888 27605439467 889 8453775602161162522 890 793102398415 891 2963260466341292 892 58746141683780 893 94340747027023880437 894 45744965924 895 1822873121735469539 896 3601810793140 897 1767806690639031 898 66963282984982 899 138101981567615323872 900 1856814290 901 105741691232781539317 902 7450563719461 903 679751247718284 904 69285308415640 905 2369628225233543212 906 55928656519 907 604490895403729929375 908 81641070287886 909 32701297685647591 910 26464934023 911 679541947228839136971 912 27481961014 913 69358291670163152638 914 92932988691005 915 252985225880651 916 96142955851999 917 18093101121615316474 918 27338686242 919 858113882624395098111 920 709029455080 921 47456183031879643 922 109367368508082 923 131077052765196515688 924 1865943614 925 2350870154130961488 926 118614059903941 927 50150577423560203 928 63558355229170 929 1147109028938113381599 930 1694693353 931 7672979202619601580 932 133058515080383 933 62930573203745550 934 139448633267734 935 117918731847023350 936 27004133189 937 1445367429957483933183 938 6046440541792 939 72420307903420967 940 1526256178785 941 1621842908304944646195 942 101321892958 943 457988880117223329641 944 127503404790878 945 29114415210416 946 17650120284736 947 1926908413523388671999 948 93846014595 949 270502624475283384551 950 1022913121726 951 95784468346859185 952 3165903803921 953 2288142594734128375807 954 91505094776 955 8616539693707778598 956 215553659231620 957 5880113679819031 958 225699775307486 959 55473890795279593294 960 4442992427 961 1558543484687809386264 962 29543458259574 963 116537327508284175 964 252829240468628 965 11110549073594872060 966 6586351827 967 3409710553449380120289 968 42331058615585 969 10688171680601816 970 3394161702015 971 3819342674540204977855 972 175998183249 973 80159535070993628825 974 310131589216617 975 214959444096634 976 242797484400392 977 4525958074670926499071 978 181580130427 979 424995978885034149603 980 313853759020 981 176620190121845138 982 363198970043930 983 5360588712526733770909 984 134701632139 985 18402771493772549454 986 57960166152702 987 4261636345356834 988 27334099933723 989 1669771020194765182233 990 1747369182 991 6712377610196059013119 992 233040875755267 993 251528521290597031 994 17063625077716 995 23639860375456789729 996 203781254154 997 7940955682115491800173 998 497210474493589 999 162227945219443990 1000 6774209261176