1000 1361955 207579012 628145516 376140462 883515280 186969585 762888635 326402539 98152102 158176572 61402892 127860889 9580638 570870044 646139319 178509022 484027666 61263304 841082555 558212774 940563715 26389629 579113528 496147999 925801172 837151740 70301173 656585275 285845005 902071050 403573723 727123762 9467290 296231662 631265400 899374333 520690249 798571510 491747709 799313372 643215695 789204466 614608448 162733264 456517316 555253431 806956091 181457954 528156706 751354013 158398859 152040410 743974602 458000642 37883250 164556873 882264704 205461189 877444309 167035008 785986538 300206284 732553407 775142614 132099860 896205950 555144412 457641318 19344367 590064713 506507263 909420687 489726669 55434270 793692316 210461042 901329638 537850352 29523791 614794871 570497239 905203769 706091347 904237001 118054686 337246324 307178252 150625749 896162463 644505508 271356542 1738703 865692962 226102988 593986003 122173997 807688147 583502197 468916697 747545898 468884928 620479531 675026049 541326148 747075167 203959040 191528801 491192254 104714245 101365767 179251 960570655 244081264 440998362 674385236 484916145 641913150 917826069 670850118 607465476 197877363 596079577 260773935 649320808 627715319 530909770 795364951 666130550 863834902 618524433 978767534 781321608 717028606 338249947 328373827 116584252 913989445 166308312 85199310 688253173 585283936 439133757 499892263 163916121 792406061 887651010 937745613 322205908 136611946 842842917 654604897 77623316 702064955 112541861 243836200 987809420 711659177 528855175 533456268 546812145 738903069 650982037 6347419 108056512 926891753 802439066 408151174 593571253 26183359 189607911 141352739 21890133 29895224 60051921 141356140 928042086 774860110 15765552 760106750 233605233 181391330 366127330 394679451 861562695 565366328 857043782 155504809 432087161 146632054 71055042 615622321 588455135 334302761 867602750 305226976 961242386 798641855 387771814 245362313 246358001 582417934 57772652 563361441 101654816 957259211 157356035 311361 50562948 361231636 427997029 15933736 573631433 744665831 278265998 564361782 428089052 628727976 734460158 467628530 7731313 645915808 619188795 238727430 4601214 88331384 918128717 870864062 742483646 569235394 153311297 781575052 33386288 692050544 91768487 17776006 295244437 54166875 313816595 394647782 234755061 258294462 968789407 969193610 86041627 184483000 833089384 226179698 4055060 122467277 334102285 41427012 203235252 164843366 950663219 210101195 693163024 976173644 989222147 161894771 611530245 12548913 621233322 274117327 376079536 853874983 75477464 634292500 212243444 691845671 648862018 473847708 425782008 635869580 19473952 420609636 198996646 616806549 673602224 53290125 279393325 961338087 782168753 422589150 970499968 416729352 379641321 800316993 793940437 214934244 730625183 394969666 117470246 218055244 703117345 738331539 85428659 29863283 329898304 153203338 72865406 778377583 745197263 703186337 105563598 53312702 498269223 781534198 730060973 399552958 53667750 182061001 333472873 228141364 520388908 472301825 650633495 430648518 904788125 669286310 57427979 927216001 329000033 28692072 420020834 33339988 921204711 431545623 656697208 939969170 638880285 851655465 634178418 611182708 722349050 10986039 366747061 827862933 933990133 779079808 959846253 575075188 837614475 211940197 856226312 911405558 675059645 662413803 269147576 846206433 766524815 87516988 918392820 330156386 507863434 206036263 68368375 695392391 186976571 295261851 900777792 398615494 249680305 248748592 42621456 24601205 163022339 9940126 691350511 445134160 97371592 750824259 706015272 574966006 57981854 279164577 926989896 93898860 761717668 927952094 314633891 692477848 889741823 936211523 979813071 472616391 380135769 459249085 939047 830572584 96448861 734324575 165450313 52046926 19955004 695371486 981553560 463536818 260485675 702243860 24537531 148656431 591003106 497589118 322888733 367803780 652840223 57022142 162019947 764116950 832688673 667023641 738895128 608970027 588667694 264619513 528972252 719217136 669333774 857661293 61820977 675902580 634910093 542817956 482898389 9719146 270539260 784365686 671155531 688620651 597378481 479234011 69453402 645203570 185554050 356952177 701772940 459021406 728536398 534233338 861910960 4860788 403607669 888331740 956846680 698565082 788094555 27652512 390041180 971368733 488312297 933552500 42022229 5127852 177019659 125553577 127094563 622876763 785511731 719103541 868495464 71047393 219485653 416880434 623810826 30920282 409872105 129735005 49668789 817164485 1915244 457827992 495370071 804626055 600640479 990016104 920192930 527093990 802316486 274625655 850368909 593593999 560686378 756056852 785696468 981626897 855680792 424066478 56480627 942688 811932704 166168413 720045103 371382611 856995799 54101849 317078797 938805798 108434005 153580928 331493337 873825784 874225336 964075733 289217184 246312014 939356575 907070972 43914806 197307790 482383792 960417727 586642609 561143173 73019922 931392395 157495276 305337826 45552883 769426420 692611078 790194361 133848068 402740013 982938080 34562817 481951992 245478800 168162722 538681110 810120200 229213212 828022071 597649207 914827890 578682610 933450444 244541449 398405366 37570520 427200341 348910354 216365143 134311094 959854856 238506303 601378784 454885916 927830495 287122783 731924445 29524921 846345755 878730918 145801757 21561573 803482300 968637227 824510071 677479192 732757002 537352810 285567298 694307953 283077647 494002115 377520603 511692848 433664282 29664504 640872738 464058172 411223101 10845363 928987133 751217310 646758352 600868094 406101460 6464516 35193837 627018185 437036820 535333439 939271922 839153512 631806893 299911109 938876930 323640594 930487700 204781872 955992451 30932835 63622977 275879357 124689825 531397338 52922929 362554318 553565898 442693212 645375333 510833513 21462064 896492975 860769250 934226102 8411211 12882432 137061167 507745924 28640596 488336991 146145754 228485317 855991243 707044925 839054835 904208142 535528178 81298420 382491535 440014616 319887183 799805759 62538567 385345346 170554158 141525950 194832566 267602188 372491548 713944948 1289982 112956317 599123566 961120584 936634692 416925246 721500600 302152071 54563632 638657245 141695318 644791905 381525358 513726604 18058215 55006311 551427631 964247039 350536908 612870931 373822889 311565329 990863021 866505537 737321618 823396415 774991349 366740910 519996073 899993387 580439377 610624384 687233326 815984410 169653813 844432062 470680933 543629943 73310039 54458067 660900119 394623566 923478834 259728655 54755088 185174226 236365444 844878630 89858466 146545624 604051153 678890927 487186721 358418265 303356126 937642150 932514405 854065140 681824054 638634987 208600395 248579434 256680104 436823488 292582196 407428384 221710023 649145679 387896708 47993504 961817705 23825186 216540196 381666328 312450088 106958249 761654273 721414361 6209252 649230264 312069515 801992665 979495488 650585862 842044215 582637618 423755552 109458607 29480957 277976482 245504049 925786547 51133914 60324617 91277409 33521525 943436880 432878829 707094883 14867005 2412257 53105657 453081644 648485302 444935063 669083513 5213561 423502704 340158848 916432864 212256839 503676767 465186602 449655107 623243353 362295898 21165867 449465820 834013877 162339485 93792412 506613895 357304871 659821128 301427096 471465800 237243837 557261278 7915970 827362755 40658249 970638023 239085244 513746882 444981730 903655886 459005105 789089203 87777380 909431203 386153677 101365032 202255339 980720986 333190079 366712661 292362844 185182954 70271038 34741653 479392988 192495023 506911104 266958821 297903703 883091689 676357572 7741799 310901242 922829371 759668938 988954337 100460985 82355245 412176982 553072444 151125195 80117930 982234289 811014149 109229609 727925634 884992808 291520495 934613778 42367721 236947595 219715919 207133066 27329015 793257390 729965727 989263574 906567974 113215468 970396412 958574081 27223767 355915679 952971431 465229402 286801357 566781609 852680583 522578420 600253359 372770542 978444710 395650085 226830731 53866712 267170736 155578376 652960846 211368401 817936247 683403003 187312461 34214093 212135538 50814753 38703295 88458942 610911289 235014625 327059520 441585949 270264586 546284133 60795728 130720872 759086151 316484637 563832786 555354270 890357494 111296825 16487054 508869060 986629696 392229170 708349871 544804452 300434930 849620801 921395014 498052617 474696447 406999270 598719941 898340805 10423804 43621475 274838660 759773355 142886307 919955263 234387007 336466517 651592017 26016452 415400342 254570846 636130184 17777793 984306572 241021929 37012077 429048008 360032777 671522841 311346250 964934961 352376408 494291607 443217421 129914133 159653802 119803151 740354504 526924308 701609361 687082675 891825967 942686864 33220741 779210935 401729565 915408943 798404194 252995795 841491216 604739165 133423336 444310468 183584168 259041480 241685562 749917642 690751276 353827298 344336224 174993196 296844037 253632866 670916805 625779376 764652352 766771907 752210106 135715876 408994576 927845316 531661809 721307352 375376202 820609766 706050 803218464 852585192 777168370 578368490 109294039 103863687 173791344 720232071 953737431 611492329 119677489 787545373 523869058 860278387 374226374 72115668 17879613 676743600 156301062 491704887 52253679 797117644 698718604 251649462 67868294 959170073 957542198 661380133 784962418 811963278 434589351 769649212 951355432 423873859 524073414 817973781 360499873 386916343 87460926 70564785 425922009 445560714 289618428 241574259 689074768 943765891 442047924 35525795 366926988 647876491 960157531 253005293 570874773 609812975 548584110 42444767 754163575 111190562 500682154 1000 1 235807822 4 4 2 137 858 2 752 819 4 4 2 362 421 1 464745274 4 4 4 1 914140345 1 323286528 2 338 968 1 886235468 3 735959106 1 688154447 2 593 973 1 371440559 2 866 980 1 416615673 1 261303247 3 453167072 1 400430496 2 609 901 3 242639813 3 519287349 1 889627723 1 97608590 1 713139055 1 988974932 4 2 240 704 4 4 2 338 532 2 701 858 1 418147910 1 504369887 3 72002509 1 176340364 4 4 4 3 850307498 3 429923339 2 319 879 2 620 729 2 96 196 1 374043477 3 515142210 3 303080027 1 76049072 1 153085166 4 3 106371913 4 3 924013131 2 12 830 3 98442207 4 2 91 944 1 758503211 2 703 819 3 291749755 3 990712751 2 15 136 3 841052972 4 3 904324014 3 887593800 4 2 586 730 3 794038256 2 114 887 4 3 349327379 3 758539679 4 3 791421668 1 948339497 4 4 1 126516794 1 773271516 1 765301505 1 906087208 1 605669755 2 652 704 4 4 2 242 395 3 216526518 3 291252242 4 1 886128606 3 321450642 3 798261987 1 720283632 2 160 652 3 55633682 3 154513283 1 829127631 2 255 875 2 155 521 2 781 982 3 678091451 3 69559122 3 29044798 4 2 201 322 1 505438338 4 2 411 838 2 94 735 4 3 739549510 2 878 1026 2 1000 1003 1 235070976 1 173398320 3 869097493 1 568813754 4 3 701640076 2 258 533 4 1 479095496 3 16149172 3 927812952 4 2 636 894 2 193 977 2 461 644 3 103064140 3 285984259 3 272187010 3 625387408 2 612 737 3 666990551 1 525495079 2 605 1024 4 2 653 764 3 952495213 4 3 710167189 3 150408291 3 508186885 3 173357382 2 551 564 4 2 141 944 4 4 3 16698684 2 53 121 2 27 804 3 261107363 2 285 1019 2 853 862 1 331146476 1 128769614 4 3 127388916 4 1 629502103 2 13 996 1 832661181 2 879 1038 1 268674352 3 192242737 2 357 596 2 108 288 3 37225812 2 445 808 3 560065531 4 1 68177698 2 382 667 3 307632733 2 394 609 4 2 348 610 4 1 837290043 2 337 931 3 21584438 1 347973163 4 4 3 237899169 4 3 282305139 2 226 437 2 649 911 3 655653271 1 700178177 2 133 343 1 439815137 4 2 87 843 1 188097815 4 1 363934973 1 905990848 2 473 622 2 7 980 4 2 672 745 2 847 873 2 367 852 4 1 651033173 3 940912232 1 723793147 4 3 961565211 2 60 766 1 489280742 1 421274374 4 4 4 3 834389881 4 3 815883566 1 489829001 2 60 123 4 2 380 389 4 4 4 2 227 759 4 4 2 686 697 1 374372573 3 819087012 4 1 531839397 2 311 568 1 428966050 4 2 256 326 1 657636294 1 354967340 2 1 56 3 627486020 4 3 521097183 1 15356881 1 869735307 4 1 823921213 2 697 837 2 132 952 1 650384186 4 1 760767559 2 393 448 2 697 720 4 4 4 2 192 891 4 4 3 564759678 4 2 313 767 2 154 832 3 26868356 2 79 562 2 526 649 2 678 763 2 611 1043 2 318 943 4 2 564 957 4 1 18877157 4 4 1 34193691 3 733867068 3 19752939 2 115 915 3 885621838 1 48532332 1 62538389 3 696630412 1 300198028 2 6 977 2 778 819 1 494372464 3 7363130 3 37185173 4 4 4 3 26769784 3 913115098 3 815252789 4 4 3 55181585 1 576922937 1 960061789 1 77986672 4 1 962018713 2 728 985 2 14 739 2 749 896 2 341 959 1 644645314 2 177 636 2 796 918 4 4 3 729570585 3 692333516 3 541674002 4 1 269347558 4 4 1 272786193 2 152 817 2 988 1044 2 82 870 1 283695068 2 35 329 4 4 4 2 554 592 3 197770081 3 701757784 4 4 1 710857501 2 220 753 1 823825877 4 4 1 31547529 2 457 656 2 532 556 3 22925548 3 711091671 1 947297123 1 205611614 1 790118180 3 633883863 4 1 309358214 2 305 787 4 1 639974872 4 2 670 698 3 26427760 2 194 950 1 813678244 2 805 1080 2 709 999 2 111 766 3 72053582 1 109260637 4 3 456621903 1 465418740 1 532823439 3 439799193 3 9593154 3 945663807 4 4 4 3 450768796 1 531038922 4 4 1 23306990 4 3 922944505 1 151596389 4 3 903001247 4 2 654 953 4 2 924 947 1 706110282 1 384529416 1 471407711 3 289171613 2 424 920 2 420 577 3 771275942 4 3 293074417 2 41 954 3 747290201 2 473 1009 2 360 518 2 667 813 1 18144021 2 273 668 3 283493292 4 3 163201284 4 2 16 443 4 2 999 1019 2 19 75 2 409 440 4 4 1 601059953 4 4 4 1 49193497 3 132314242 3 726662223 4 1 89221675 3 977402515 2 227 789 2 59 811 4 2 133 691 4 1 446303681 1 975730069 1 753627948 1 334707690 3 318427807 4 1 10692472 4 2 308 1092 4 1 837866157 4 2 315 560 2 6 647 4 1 820561907 2 445 557 4 2 218 787 4 3 466958861 4 4 4 3 586188766 3 215129786 2 548 777 2 403 487 4 4 2 769 847 2 12 258 3 537271789 1 137503940 3 212225150 4 1 795783664 1 22343654 1 151255411 3 616959133 1 256977386 1 427117202 4 2 616 1046 3 723320841 4 4 2 25 953 3 142699784 1 784737185 2 135 759 2 363 724 2 127 557 3 362666242 3 507051240 1 57257470 4 3 640384890 3 310452259 3 667652807 1 356653309 3 294541753 1 4154357 3 399337316 3 118226380 4 1 283477570 2 579 722 4 4 3 441089641 3 870863226 2 595 707 2 379 768 4 2 106 1026 2 251 612 4 4 1 477205143 2 664 1025 3 820155578 4 4 2 67 352 3 306263515 3 884433927 2 10 391 3 55873514 4 2 866 993 3 854392027 3 659794797 4 3 75606493 2 507 988 2 547 552 2 289 978 3 14787801 4 3 517892454 3 477946266 4 4 1 225628331 2 767 770 4 4 4 2 660 697 4 2 544 734 4 4 1 850383993 2 807 967 4 3 807476556 4 2 557 967 1 15305212 1 479731444 4 3 860932564 1 19782519 3 569686491 3 690206392 4 1 193625663 2 567 920 3 457358975 1 467276846 3 72092789 2 102 802 2 328 368 4 4 1 861085806 2 381 587 1 262656582 1 580589255 4 1 676175363 4 4 3 59996790 1 335256467 4 2 802 1025 4 2 49 897 3 291881597 4 4 1 89269781 4 3 806082256 3 375430679 1 828449989 2 158 210 1 970483194 2 218 1000 3 267796374 1 97562860 3 587976338 4 4 3 36485467 4 4 4 1 873864349 2 600 940 2 158 747 1 316010524 1 215575103 2 317 914 4 4 4 2 479 662 1 315358933 1 190451957 3 449508490 1 90913645 2 351 390 4 3 716005471 2 20 350 1 102630765 4 1 38680331 4 4 2 847 924 4 1 249991977 3 532246317 3 456504189 4 1 708669593 3 408439344 2 30 618 1 424787296 2 205 637 3 503857541 4 3 154597776 4 1 189226075 1 301513144 1 181304769 1 237545087 2 583 1059 1 243685895 1 278944282 2 142 1102 4 2 377 451 1 431380731 3 877431268 3 186293454 4 2 1027 1140 3 759862167 4 2 253 526 3 575093058 1 820571494 2 251 355 2 600 987 1 13817273 4 1 237659583 1 843220276 1 61708549 1 236304656 1 90940724 3 53313231 1 750285030 4 3 584915494 1 27778613 2 10 443 4 3 966090083 2 510 564 2 161 1137 2 112 558 3 62519414 2 129 689 1 563218164 2 131 911 1 723127639 4 3 142324865 2 541 552 1 328937360 2 635 1091 1 619811224 3 746550340 1 682834406 1 297408098 4 1 983246667 2 23 713 2 440 835 3 637406902 1 47735098 3 319893950 1 471904408 4 3 319037822 4 3 594690121 3 954877427 4 4 1 862684126 4 2 458 957 2 300 806 4 3 189889296 4 2 146 1080 4 4 4 3 181261165 3 11983331 4 2 352 998 2 16 50 3 355700650 4 2 902 1026 1 292191023 2 635 1157 3 738718661 2 346 472 2 885 943 4 3 561525211 4 4 4 1 191569776 1 276236635 2 394 1144 2 118 246 2 314 1098 4 4 4 2 213 369 3 640172288 1 822313610 3 728430505 4 2 458 944 4 4 2 403 1065 1 456745036 1 565209418 4 3 643623837 4 4 1 439623026 4 1 782290344 2 590 974 3 228544950 3 830831651 3 829564875 1 984441380 4 2 384 671 3 452339358 2 1045 1150 4 4 1 895505793 2 535 1000 3 59430349 3 441781864 1 557095018 3 620781821 2 300 915 3 189592657 4 3 841688484 2 973 1024 3 628744293 2 285 876 1 893478929 3 318322342 3 35966168 4 4 2 157 455 4 3 227341534 2 80 618 1 7362583 3 459277942 2 98 447 4 2 482 694 2 330 555 1 13226661 3 721138123 2 221 605 1 271391757 1 62320178 3 663597229 4 1 673092310 1 677505852 2 792 1164 1 388236204 4 2 113 818 4 2 545 1088 3 149908419 2 40 194 2 97 717 3 462867853 4 4 1 48875128 1 962951105 1 738031650 2 506 905 3 108103061 4 1 66614151 1 534588039 4 2 235 628 1 702088046 4 1 391887711 4 3 626739580 3 760608533 4 3 860391398 1 6753548 1 253837171 3 806234088 3 793907039 4 3 740801333 2 547 897 3 999709327 3 99449727 1 851304258 4 3 84059036 4 4 4 4 1 554841792 3 964836121 3 475069221 4 2 458 987 2 80 133 1 67791696 3 693613708 4 4 3 102999255 2 468 988 2 295 829 1 914483153 1 502689747 3 239719483 4 1 58399232 1 874513791 4 3 151171357 4 2 611 1091 1 33528826 2 179 1127 2 595 881 1 615455294 2 814 1126 2 970 1130 1 305850763 3 196719389 3 147504496 3 439074561 3 556482336 1 913060958 4 2 65 539 3 490203354 3 183831285 4 3 137428860 4 4 2 18 580 3 744307202 3 657484936 4 3 364964819 1 792837804 4 4 2 124 1019 1 521980536 4 2 212 847 1 128453424 4 1 952188766 4 1 281744549 3 727606859 3 50386123 3 263946202 1 23149076 1 699691710 2 1042 1162 4 1 144536009 1 945111881 3 279806560 2 580 842 4 3 98635418 3 118811426 3 190480178 4 1 492183502 4 4 4 3 60388066 3 121413382 4 2 86 619 4 3 730730565 3 826352284 2 88 244 3 309418677 1 817330336 4 4 2 318 795 2 668 999 3 679413643 3 610203312 2 373 591 3 269283923 3 880722679 1 33829726 1 517119455 1 860248670 2 407 691 1 72737767 3 238677392 3 191891200 2 36 816 3 773980300 1 523291685 2 89 1064 2 197 940 4 2 536 703 3 204330040 3 28099261 1 696973263 1 929622487 4 2 544 984 1 919787431 1 254209066 2 667 1207 2 606 946 2 813 1228 2 629 1006 3 840501744 2 977 1052 1 756120934 2 605 1075 1 16593207 4 3 931019191 1 141121721 2 185 1007