3000 322
702586 652042 940353 271115 255775 734060 658450 302988 684233 396674 777517 118399 223266 901463 358033 260402 804282 631664 149703 551333 663999 164948 651698 123026 337066 83208 204421 978000 403676 990433 438648 607531 872596 686884 111531 589084 633730 181198 94672 874794 513781 193838 452601 218188 798242 500480 102428 818128 89535 280669 27997 740341 113874 525765 92983 480437 685372 534851 455167 484871 437043 595447 94854 474518 236263 865453 939021 66448 143297 703471 571447 19106 704894 943933 423110 347490 569402 939136 263538 302285 188710 628418 469258 256073 387894 34778 312449 982906 586044 282584 936131 358276 251534 35139 146201 199039 230035 872981 264546 248600 603927 917139 291375 761588 368736 561113 595838 942312 757259 508151 841398 366470 384110 959976 545942 773441 314448 915291 612734 247309 933638 468924 339433 262752 103246 200643 692243 140640 258715 447379 544690 380506 785095 256781 368600 425006 128869 222314 146485 725398 146559 668074 222037 646952 656530 353476 933095 656790 557293 46289 406531 266065 469859 933330 863958 61905 680126 934202 542442 96752 866782 426340 980550 874467 828877 931231 68125 793777 305183 135182 379142 588906 4873 449651 784262 495292 528149 296295 971430 248173 681152 645838 576 996497 235461 988839 928302 900969 855256 397752 445414 345748 935999 29258 136857 956410 806460 706041 967894 523627 835266 442865 900696 69650 438320 577015 794336 422506 680595 967801 418845 199546 30282 861808 476035 387994 519669 120484 222055 235782 255105 859589 246619 90473 866715 558260 28000 675183 686238 649603 774589 423930 224884 744265 625066 703758 183649 372694 691135 384570 602462 472971 754565 348378 497894 828495 310621 175734 636611 133118 857014 274965 904141 533776 154155 521025 682518 486139 635145 369000 959194 174452 797736 23735 507161 66484 131750 588494 904333 309272 402772 476026 605060 350309 351421 853465 555628 352466 818078 999019 432210 15211 305312 898102 171845 198711 792341 114320 849450 226252 387903 594380 112119 774987 438455 770274 764049 76785 822527 820834 241731 591304 205526 538517 751840 376848 532979 131417 863130 626385 830395 80706 745350 90440 556492 230754 901545 106231 472991 470866 385907 64560 666095 972012 360963 898800 338775 273182 454743 972807 779431 632567 39641 451360 14870 62021 376366 244011 104025 511675 782383 925709 916046 426084 178390 963648 423307 343005 824160 558080 952408 701187 945934 153159 943265 541608 696599 300943 244126 296686 169983 960650 119372 242701 633505 204600 213677 252975 234105 10230 740005 659201 310158 899213 559352 220010 965042 229696 809570 816540 2909 847063 420676 502211 945852 451617 241652 49498 885479 454907 711167 640902 979947 936203 935809 504495 910298 306584 124212 639404 28521 972323 324901 424153 290824 322937 537490 801060 14390 343134 246583 958541 438925 444274 937257 387011 384513 399263 236702 703940 286918 509420 571602 766682 740018 481222 949844 945710 937810 714183 454326 359897 860280 473627 748117 387580 365384 17983 730166 289821 494045 725739 831935 944715 663507 232878 928857 54385 412523 925026 845387 594635 868393 177073 39320 296754 930309 39775 325405 508110 205907 871288 106723 85443 997470 12175 222608 408356 880297 335646 570276 804536 618291 830940 16330 541460 20905 852562 25369 94608 429106 620910 13936 639896 102811 323466 41958 727012 831247 769852 322257 249825 962452 816668 968586 414933 879732 677499 785736 512165 784132 498663 272875 477632 41026 673632 334817 180598 792777 525885 316188 922965 937680 425043 546811 214 356649 987590 510306 993798 28758 17259 61567 75303 755079 988149 761305 604998 381277 381805 130479 397060 121665 809779 538325 377574 851817 300121 872185 717559 627903 594705 632862 902711 995487 558691 960609 244951 926489 883340 636639 110089 887736 378779 333163 951401 87674 644921 226417 869388 216262 106327 486879 457334 752120 280835 291895 293814 550363 131806 561055 820397 687668 256051 480298 94119 471514 760414 731 646991 921279 279559 318575 681155 155589 269262 617406 518215 167493 198322 491029 867399 200633 684746 531369 277996 413283 821510 102464 546953 478762 110252 414362 170302 403747 30111 567127 804470 873817 932880 251778 800173 358305 714938 471183 743107 400080 959387 465990 798937 180047 727872 210536 408589 379639 665491 577547 275044 933058 40258 476890 130304 108454 218995 944859 21876 719707 577957 836068 850338 122551 923977 141879 120140 237556 698605 575090 689555 215568 474920 326167 962271 568304 699115 448187 115771 96559 225382 736483 202910 480186 341281 132197 370182 490568 917283 779661 434438 293162 238777 352171 530998 970470 74539 190588 396583 565237 67188 21417 553548 17091 823181 670923 468006 997252 483361 945034 219123 78008 417084 530679 665275 126043 709016 292042 945461 796890 773556 44906 58810 32543 442421 34459 143090 57886 993945 465983 261137 150014 279689 107309 796792 923692 815235 75763 606757 854085 394725 779556 12550 518532 743230 429261 100297 970902 811609 284223 729753 167553 615822 711608 599162 438521 825082 412022 70679 153255 149662 779246 64160 965465 576722 70082 944884 989932 233742 562186 232153 135154 75829 885589 221972 203415 175652 284487 945725 209440 183543 57280 707217 104381 819495 940417 276729 467645 802715 487712 316975 915434 999145 237589 843485 37644 825480 344670 987132 25819 208915 404585 504295 774153 132341 58409 241322 99881 946622 515292 201995 322221 264017 452144 321961 626353 215304 685981 914149 753566 81481 480618 819906 70320 938901 110002 106660 8167 859282 27234 470422 589851 483890 994551 597803 4358 395997 158136 891767 227921 663227 442921 437191 537531 254503 645607 599753 811139 815882 97661 819682 321494 973006 572668 196513 519610 544943 510193 385401 585002 540508 796414 342967 455655 10217 746293 58030 874093 517407 570577 387869 552209 99387 156791 534575 299418 503734 494376 978662 649483 18968 663001 318570 182463 364383 895040 791814 458206 860825 516094 148708 707511 863296 679979 293977 476937 130175 246086 65785 964998 720557 484494 683839 695493 470482 251870 492707 540061 379843 224783 583444 649808 230911 128351 755172 985295 729848 821614 725247 389061 580865 460567 976984 111009 994460 129849 305529 571231 942350 879330 760676 642294 753253 306614 45132 589146 217184 455088 768056 978586 128427 922044 232717 517289 800944 679148 380417 893269 170547 824082 986627 842644 115144 388571 98522 345864 399430 158935 461308 833898 662413 300516 119787 112842 813862 258716 557102 193092 699221 85042 472350 439133 511511 209394 683594 958995 210257 73186 278117 339383 864129 32953 42985 533155 467507 212693 685624 395715 967885 217628 524724 127370 102384 954338 886009 745468 502596 671229 225922 183750 217947 268128 397612 502671 269427 351732 799620 798926 252269 563813 107135 627758 620878 179754 842509 611243 966656 268048 152440 777539 750071 230698 442507 175244 463461 980397 263632 359053 866099 986973 514552 551869 505625 703522 910673 916912 565780 460975 853001 675120 991102 102530 736579 799977 351811 9452 336457 971976 759606 338645 850085 85431 737921 552760 985589 294859 347523 352885 438836 462071 192332 446822 53510 625785 835703 324049 449880 967715 836665 687834 577596 966090 474274 618952 883833 358156 428595 660689 714055 700608 407159 279265 769143 720750 520125 256894 71257 517382 908313 867682 745669 423301 868541 880477 306915 535942 364393 193517 489686 223873 947611 977963 257515 166601 197686 917971 329360 824169 995982 344692 843733 104688 43636 674016 310081 231305 506223 793138 442273 550936 758363 92538 508315 37619 203310 123753 179333 921384 18445 484907 75764 10450 926439 503074 857965 629264 574556 767791 5022 208708 679517 993053 192282 395864 680386 572214 732553 46827 243147 675436 742304 663158 804738 802401 958 304434 71580 123459 725169 386855 881479 27165 454467 975849 365625 683379 868853 803592 324116 446444 771598 530406 425689 945873 255641 695918 354408 625948 756221 889195 803772 501898 579958 687378 753392 922804 16344 22571 960170 640711 95492 301369 140372 312752 141017 726309 150663 454488 56853 395181 259725 539255 264312 216516 351830 944306 990735 158617 739718 56547 313161 780297 727709 695122 492556 444682 51313 659314 640340 372451 146411 259111 804920 89418 598569 768348 749390 371547 686484 211703 271794 639042 111349 512407 685500 39313 44834 812240 795764 968184 111081 841986 566719 553759 179706 363725 189868 19620 702649 97749 87667 783083 827864 101201 442718 152112 342612 457922 283314 341012 458709 717427 201629 167378 462222 293920 235377 154172 817360 804316 116580 653652 441500 64644 75478 999665 105918 517530 702440 750179 708248 76157 381112 110628 719680 792561 232390 585185 248195 367642 187580 328152 151309 14026 395749 827602 628725 661549 465626 169820 255714 97140 604870 161352 666865 27829 727964 247327 162038 457576 221168 786200 655766 456606 533932 765842 652738 427310 555689 437664 633221 808798 770204 953008 23599 69832 113927 949156 373069 494219 449434 466815 671222 623925 208328 488035 848540 456278 460130 289493 408446 387731 187576 601768 68218 246221 16073 808200 428891 380716 866287 752351 247473 632128 274356 362449 99178 510826 640553 256743 359822 248114 683147 924248 855820 761876 800158 402656 309694 890551 977846 717692 252336 62319 638587 78249 852043 180413 278906 109596 778025 178319 169794 358322 123031 70085 916645 411452 248549 174573 737842 31373 511439 436425 538653 352672 915771 54207 757638 151253 54135 101364 272886 482159 237040 172700 132340 809628 898968 287602 761664 667224 851153 916490 575601 237047 402343 517166 66285 295831 103745 721542 236457 155841 282599 615806 699255 367497 379658 34753 473918 632677 551931 633876 549237 823913 864766 498926 854080 164427 181452 897761 326035 375844 118160 576695 721492 76687 290586 50401 425192 230720 587888 680240 424696 492345 973450 673997 101720 777364 460376 885638 143538 476221 975906 791203 836910 912826 863456 668154 57738 736421 494454 79369 136334 931267 4315 222966 806519 964563 235006 971504 610944 450620 492916 457458 562950 123947 822197 399272 363589 188409 194499 588093 917593 174988 749386 866149 549366 880981 899260 639822 775417 451305 120048 425526 461399 239064 211427 421124 962363 992634 166676 842128 294068 406449 883194 676089 870129 104780 483189 219021 739173 33516 431821 706619 654660 578294 999912 178765 546040 187063 277917 639255 590631 425892 90801 472975 556076 647867 623853 276513 580399 667099 297307 841890 151433 992014 958529 997899 11027 407860 92619 722233 584668 722829 719402 12229 852879 951102 613788 273251 949709 540249 903158 614880 982361 537185 246711 15936 111778 250125 302258 914501 134598 277203 570887 472191 447140 29177 131474 293254 859552 636334 782108 156477 968675 829781 435683 961260 477101 325191 725964 153284 700437 179337 926227 637680 868941 889854 669304 582280 225454 766209 811056 448778 26622 284366 592814 653296 855108 11037 655317 273721 290588 743686 422006 457235 659921 847445 966749 329187 467967 134435 284269 596618 467248 317071 651073 848751 309666 403165 567904 946456 616555 195902 419840 263655 390595 556603 405935 297247 188862 215780 502887 119084 223658 863586 174912 857996 557445 313612 379918 141126 784458 268542 514657 830863 589989 383247 684268 858308 508778 448448 571044 148113 781685 590532 156469 155205 804577 935822 397068 11730 970101 40959 974618 507766 887708 205381 534195 554745 877071 986505 130597 721208 91635 907340 969292 460689 493011 364711 553490 308122 315185 138792 740966 46242 111373 69119 584066 75481 156723 589459 805616 796725 789686 794505 867925 547874 624591 151881 34849 821371 478219 686236 773028 281560 739805 166456 968538 772103 112692 136603 638028 336707 799350 674752 937825 210533 70912 882250 623277 268800 297224 120889 616140 397900 280212 545644 656363 467479 359009 873119 614213 760120 717287 56874 849112 249620 528706 651848 992834 748568 601954 197256 284329 606133 620055 860611 838597 944330 702311 927572 804771 387452 605275 654574 724053 583144 183807 571114 285330 156490 796057 361652 936337 883586 708403 150237 215327 15453 973944 644131 319500 606162 807120 786760 715437 729002 104015 59309 128986 481366 201132 583025 762733 214973 447133 843589 136624 411148 776893 46346 465194 62897 562009 47677 457372 34247 593434 775171 264703 280585 498859 411577 199190 118533 367935 959239 321808 450364 159587 649535 760683 931463 184645 187282 221164 78096 680188 485779 962605 145488 325578 164135 419795 79249 368009 465474 36455 381968 222205 87049 325265 260302 885818 551986 935436 224735 24946 494043 561694 287629 159821 8949 659334 753637 49316 692881 882997 318445 968083 940157 835339 233446 65513 381620 104301 923233 528752 414924 461071 36684 808059 721749 79013 282959 856988 947410 897911 685493 415081 967574 399518 435584 95054 874271 416427 878078 833904 320050 555520 566624 154773 454595 302954 809817 320758 176585 908944 960827 844560 176117 254262 77572 319289 884505 755332 327476 859412 909249 77991 67535 949561 769573 956735 201122 800732 787810 528003 705529 46592 216582 571346 865367 161611 172578 743173 334236 823978 830007 231611 415284 82912 156850 245934 682359 1968 730258 166147 817804 588968 901616 978954 824018 628250 853091 426148 376665 515848 825575 340914 545386 434183 20698 667439 160825 741124 92740 754540 10188 124343 149699 706271 502113 196750 782408 183260 351701 631618 384588 588486 640270 871807 136555 435882 435088 924475 378205 2328 182745 149306 883678 843430 812219 333260 363081 289759 822502 397800 949497 94986 430838 799252 520211 407488 9856 529226 694200 442560 367756 505589 960533 117000 985647 201594 954051 348862 431669 951138 617843 108175 773341 166731 55173 312910 261993 853661 712670 998789 448026 928270 590562 46740 112807 850042 893690 6059 112339 784662 481752 258600 41762 590117 506645 587567 212930 980890 721784 40573 248473 215355 23382 546465 753866 404507 397621 389653 939333 329152 539995 675052 433430 884151 397009 711512 164178 305031 742964 936820 812249 42396 628787 368795 131062 598269 764877 488242 338396 585504 214556 284064 734584 809480 329127 744122 361040 257318 323343 430039 915534 501128 419826 13586 201861 61591 676384 928164 442812 818297 551472 476817 721030 405980 236947 618905 45357 491362 836976 39016 601874 293221 209670 872534 293965 630174 467826 640518 548090 147889 22100 877185 188027 625878 510196 882507 201206 784279 932830 903038 434738 593659 688034 117846 19952 93891 884847 636438 254882 294973 494428 717939 904962 161258 218494 974335 278625 94202 511410 402713 527709 318103 234556 741980 947666 497219 174548 658566 857850 967122 507323 756529 653437 11955 538756 80302 432792 429588 264516 684250 819197 303167 956617 479116 347606 681707 698209 489811 230596 265709 877745 667878 802973 787099 674688 224799 139190 533173 967167 519236 528568 759640 333126 306288 415556 180830 311537 558265 168652 344449 375835 565589 500938 651161 897751 335665 384006 947050 445909 15564 650406 536163 51299 538768 11982 856374 698138 615536 347605 48504 323102 524583 720988 632857 668830 11576 807097 314180 520919 330098 489735 360068 371719 549779 809525 403678 104458 452253 415284 62729 66465 298915 160746 300427 148116 359889 729574 747829 583450 515747 233770 967423 355316 598255 821931 710531 195420 241713 646041 686428 18545 743395 359286 65186 18602 270637 111615 184649 972459 22640 648174 573717 881211 820022 484598 902009 258107 436504 953435 552275 234291 392426 604378 894633 151291 886439 597155 23603 148132 481733 400705 622112 924065 615931 894154 795590 625509 897097 852791 321751 778885 789624 233566 537329 700608 973012 531421 175227 865470 996649 589607 993206 561486 916116 19098 816249 374713 20513 887809 492365 359629 809730 275555 765394 617590 378322 279600 752998 132138 403346 427615 157415 891813 54683 910432 215527 693514 741122 173769 524532 209689 959381 186267 307233 122235 942639 505063 269962 922852 347463 102822 819825 613349 825780 116871 503940 844880 104595 739259 152624 121917 659109 20313 784668 579209 375296 637166 385822 801073 330060 46110 651878 181026 654031 562326 276421 47106 893837 280539 370247 508527 106419 613859 283055 41729 952600 493863 54127 669806 532505 349856 662145 425082 849528 934761 227804 649225 296370 89036 616388 780026 708727 585959 687026 595369 633930 163408 701908 729625 275902 911808 467168 951339 393594 908739 494045 281568 253417 624674 811863 550212 125648 282361 888995 780437 133014 794703 178334 193497 826682 739595 256627 147447 305186 457423 996994 883852 435848 370738 381127 940112 920483 921189 396312 883885 917287 274561 534430 475788 212029 285019 518986 979221 471788 316676 851343 740661 680678 533496 525900 366851 985707 351048 288603 972805 867718 861687 513961 237557 185086 478167 579992 447206 304189 969783 69823 346468 801638 598284 838969 925126 657936 351854 693289 748136 763744 827018 883298 625042 628035 388146 365727 845402 569046 855351 389949 459991 219936 431219 716316 618975 500087 793730 788958 454526 317652 33358 128905 109863 462121 789339 902439 507708 266027 895953 790580 388484 502035 182345 418969 869539 938429 295516 869438 966386 994140 555174 722758 989832 823011 996158 587974 321716 480815 137248 966339 406154 292163 994222 831985 31314 295863 638134 411561 193444 178557 143189 713618 575334 834885 915283 138676 335894 970695 743028 506368 624979 460652 432048 347670 127896 753549 894728 807516 625412 768491 127115 504388 356417 484270 711832 937449 269216 691963 273708 305760 703916 762266 31407 833007 738371 497342 463390 198678 415044 642899 377115 82606 367868 362128 375674 131467 665710 608618 882820 997691 76287 174452 77011 824903 556681 472949 278159 849894 636610 562388 21958 66753 262975 692404 343251 612617 909851 312535 663770 681642 630986 154426 361955 392228 629899 50484 740741 608860 99600 804267 408437 652038 768473 8334 556365 262782 493342 125646 380262 582664 642308 347138 447437 943334 742641 161519 592108 740082 744222 86838 896830 503938 601483 292075 449056 623772 139939 738988 638403 808468 717482 336667 463688 483711 275820 175940 148528 320075 41886 618404 825109 862063 429362 575611 79122 602284 608235 527253 448223 984601 654391 602796 760005 860653 205690 861326 414821 620892 219083 557804 478586 16264 177297 886693 616439 899160 302173 259447 476800 639422 68295 850396 172950 264039 634593 430745 367203 126356 536895 200284 729926 609206 341385 847483 310567 172486 356042 742611 997582 764031 896035 445904 863314 306545 782338 42578 449152 185851 888715 212557 477131 355582 977872 520605 831987 389123 452573 740407 939353 98398 690116 279361 435612 440651 675167 921572 826355 447043 792137 984252 973500 23176 373303 326786 855334 958255 724612 323701 942260 103833 433333 574093 348934 445341 739300 286389 257008 345464 493936 581676 409630 955697 462847 545490 60438 665949 250926 328677 869938 203885 353781 316471 30050 794725 192333 387869 688882 271121 661893 898272 93034 931360 139230 76050 668528 717217 301097 503546 702397 987327 42020 513172 766380 337714 887203 28013 248549 680098 660813 819790 249546 474051 728568 68718 355156 794686 738945 875163 873305 658761 418381 564787 515061 374049 188753 141893 919557 210711 928296 490804 72616 349072 119044 556466 198627 255372 462548 149631 609935 727187 66953 23338 839423 575343 72486 885681 38586 140358 478428 772485 969252 784344 547406 53335 89422 858825 27200 866596 799141 72215 869061 177299 249174 288212 547979 225542 740050 672767 73737 200559 232541 217273 707596 918728 627363 75677 317347 303638 463135 752459 556157 142011 426189 719047 849396 732438 828451 126179 854086 349827 314575 795107 632741 797125 303690 470414 819234 714057 325360 154388 240477 664698 154883 72948 20543 824728 868267 377295 232001 392212 903265 344342 770763 514306 492053 691671 555916 888832 665431 834159 551787 692111 839492 549992 305891 573073 377889 784746 236138 230390 961338 687347 974429 716724 315545 880958 759625 353360 759522 172255 846249 523774 798917 924426 897003 334207 424142 937491 54162 261558 610258 577057 944995 569180 370457 541182 790706 399538 170179 713702 894537 774537 696450 328141 578289 698791 646171 270910 939319 414017 530516 695844 137729 729750 394798 825792 620013 37475 567613 100450 710050 950401 83779 99820 768999 838595 887992 74627 410944 884964 797847 606017 638103 461842 678280 188607 729837 504109 911363 413078 504517 955646 783962 986329 158278 70438 811591 570868 925280 946757 453341 488881 339234 600356 41990 929907 236054 434670 737104 60620 7143 876959 438568 16529 108863 560136 417156 962776 781582 735039 390320 860556 789138 227027 783800 387318
