3000 527306974
304882 718546 953722 717312 840963 890594 933231 194746 683682 241759 698547 154309 911455 236101 672093 769680 196477 136539 74268 557124 886876 224299 780867 308971 31430 452545 132432 878347 717395 637956 15134 289236 874913 153837 89078 913609 832685 849074 931505 845202 275200 866507 472977 780928 457982 995438 146284 832329 919617 269178 373018 891226 245396 510432 941874 791679 576406 591543 450445 703310 381895 931796 450702 669668 329003 687082 123061 362786 859459 623563 837035 664572 275660 724485 470158 581149 640878 784767 141405 461772 709699 764359 464939 562012 185214 307556 212470 188128 548084 373554 265617 389140 481778 274478 634912 293745 414982 932465 137134 605241 514702 576745 246885 592820 247127 929690 203916 735625 384241 137470 76836 451288 682867 659645 999992 486176 408619 2287 753803 444927 978299 909644 45308 235830 148631 522220 845253 732043 878860 466740 670099 266024 167518 768766 433577 772020 910418 263484 929241 796876 842188 367622 212923 739659 895122 661126 392961 545630 751317 688768 143663 945228 738094 632816 249204 757821 520456 222000 903423 647224 44631 609092 735886 619945 40526 376807 611347 763043 597571 357915 191000 309671 202244 172474 825651 717259 582267 117714 944367 236515 175457 72503 449992 674787 624021 583169 846211 569708 728926 40714 460945 865449 359724 676428 97164 552166 3120 132629 325674 127419 427866 316149 950782 282009 592490 626272 732963 81189 983988 492716 547377 384511 893001 875041 37524 5994 335214 351014 162596 520680 586952 558647 541786 864388 497259 233888 702024 217293 310962 837612 33282 394441 525732 748918 954626 164709 774241 153477 270863 446024 717276 864227 890366 225624 271107 445489 616576 247220 372837 810457 256124 620852 301313 448674 213750 671828 367861 446086 39959 332330 416951 483050 90972 71910 794975 47824 628946 966054 4295 685077 811442 321263 199680 471340 504087 581571 408614 349036 64276 303496 553709 456090 997781 143643 155575 905514 55153 117372 386462 863507 163849 228878 322915 318089 632539 407208 305062 34996 364481 134505 104502 378564 514748 463335 613666 919017 611620 455360 45693 368095 561044 309834 135640 842710 51563 338391 174735 936272 930298 571897 775588 131739 946170 5179 937989 260175 956670 910222 714696 157024 94041 502189 977146 389706 73786 361731 276895 840733 861425 224139 49232 753271 249353 698968 868108 980782 250317 545151 824380 965158 800572 461933 204524 601123 412181 650749 56859 880443 573686 941178 54470 120974 643114 143825 988365 559783 796912 851887 388758 559516 415813 314063 156243 571972 312321 273436 91106 390780 54616 976971 31883 175146 762247 16340 112360 549576 750925 284457 908426 95350 349854 848365 657864 444963 168338 652353 873634 707017 750802 734871 304539 962952 799023 42769 114730 99270 323444 425469 406522 494119 409043 280768 158178 822951 156759 472054 315542 3851 551902 30687 558059 271607 289673 348078 237361 982784 259315 891384 998673 894990 393199 436360 164187 876600 798849 839839 507561 429060 274154 162604 483471 606293 945867 562759 485661 203325 803490 393815 748788 499232 871785 199983 30469 600768 949713 35854 505345 861126 525115 187397 131363 107876 5775 617476 139381 322201 84586 928177 947519 521073 598925 546715 759881 875061 58093 224711 739670 781553 955385 680567 724885 449253 28330 557460 23099 814629 904160 714238 150380 312640 880527 649522 161212 681935 56186 767532 525005 448750 970829 787318 269915 236681 510113 22559 637582 98502 255505 331691 556119 528481 10057 599068 471217 935336 796677 951093 356439 684667 231152 637669 53296 550103 734633 447939 246858 958467 534800 776518 13343 105269 386908 958569 155570 977132 489456 856675 369585 871677 139793 714453 361530 755854 237609 699596 297279 619404 97374 269692 747480 140015 131447 761479 187089 625503 109567 59201 573325 672870 148588 639691 771063 536406 27314 812678 484392 918904 373614 399618 606143 854296 598795 523517 843970 599681 538187 433974 70673 978328 900851 466044 552876 998662 294104 354687 398000 704973 130639 956986 215666 716847 343264 393535 608128 81501 802943 501613 976932 434424 314722 853595 973172 822456 27519 747721 469465 408460 430452 504846 591591 937893 786135 63902 83806 262586 225959 3384 152880 558243 340381 314465 880946 556707 217835 452412 978828 588800 308911 11834 213743 659495 918856 93438 786044 118358 687944 134842 70166 581505 405431 658436 222703 328614 166834 16439 167769 732150 194219 51677 58266 242668 458712 592915 926418 186843 691478 807212 743248 429305 734583 84606 835872 510561 894486 538196 162562 116744 56658 365612 651085 54331 544023 860096 546287 816452 819836 786359 182699 95976 740396 813060 447196 319659 442107 311885 256585 274968 295246 845167 607076 750067 580890 437983 950796 296670 293789 779317 750391 222065 101679 880105 683666 88580 168487 49321 899264 125188 789124 266753 156827 847469 230306 654893 320232 105046 108221 516986 462964 627857 109408 48138 738602 938748 603464 571545 440507 143468 744372 500813 244681 501376 347799 882029 381204 130964 2133 747109 929963 513761 92532 730182 106042 806755 836615 897212 858169 281891 469256 16052 441864 965030 145983 740487 1276 662787 545774 147095 255651 364737 158366 449392 949648 457488 20209 374223 379901 344411 788074 365930 783006 202268 112136 155150 778165 167713 590804 177568 660564 448079 989149 59456 837430 628409 453247 807275 129172 515712 430181 578453 218474 857138 161670 649536 995940 394768 838526 21379 417445 828020 412905 356710 956064 449877 419639 301505 84291 582326 254126 420431 176664 874525 622974 787567 585493 51613 821049 483770 461857 107962 562462 893797 786774 537292 757607 474314 779772 149889 934178 817093 585112 45503 582140 757824 197579 28190 252917 455607 46892 523035 286192 942963 445212 44694 812435 366617 199942 776102 952340 481254 419725 889594 645777 167598 461171 808547 216039 452195 790693 595115 412377 59718 409747 422419 232524 841811 694473 770869 200590 591392 921829 443479 214558 40900 38863 733157 17423 468039 550186 759232 718489 641690 412208 421616 960446 917069 529045 138552 907571 475361 90224 516239 513395 615340 659367 469492 85332 981249 560673 537165 722973 533124 13963 62825 745457 836382 512943 670257 185783 251243 758701 119198 28705 440468 735910 980614 587340 912832 213413 488060 503560 37524 434662 869209 43701 211964 290516 766440 840645 523685 551494 155676 154818 162740 832241 864202 755244 18089 186231 592846 69936 309144 177089 729108 499098 203525 698475 518005 2045 633078 751993 260669 71207 490356 818565 122092 67728 755612 624070 68943 406520 552587 731097 188255 201336 590535 959169 59333 767581 28786 400379 655242 215364 754434 931413 472817 710184 843398 344387 149630 469893 659393 629379 667208 804595 183886 925551 146657 879966 252125 607576 548758 983342 825416 736397 745529 830209 599640 731572 81273 528322 756920 450537 537290 851792 177822 419006 648279 433778 257579 815880 323823 300615 473201 808959 787757 6814 112027 801372 463921 479658 246549 747710 703597 845213 855415 194384 276957 21339 754720 807885 486530 228214 587303 289011 635043 564100 955676 845977 739521 631055 941734 560 694338 819406 965265 608357 133968 443078 346144 252823 462226 18847 725697 419155 284288 105244 145120 37268 921437 344198 463565 29692 74040 886500 934043 79259 114760 982690 382578 89030 649178 802143 696547 808107 942653 184508 782569 597094 509588 922091 599405 490167 603267 749320 740 489225 536420 751242 18943 648617 356325 579893 772865 361625 83317 930742 426239 801111 429067 899476 938994 916261 86233 624248 219561 996631 357527 163019 124383 601726 161998 77926 407006 611504 306482 720452 520033 299050 780593 851503 700944 437650 855482 207019 521008 202756 108455 606157 562294 402886 316618 49100 81494 320658 473111 207024 495304 8436 716338 49634 447172 545591 74581 496404 641890 320618 220331 672438 128077 631337 647018 723120 708438 338756 11206 315888 992087 493935 21735 680444 174067 552657 344695 39881 836107 306021 778629 821740 779351 846483 450631 928 956264 443737 140049 716718 442572 52646 387816 161053 174590 787409 382387 807161 935499 705790 402227 260620 313817 908883 758197 540109 503317 216310 24109 101147 329654 177091 58525 258293 230412 295043 373644 832093 936696 622693 871076 418678 882561 544505 661575 300605 12123 15041 773904 960619 199727 792496 993324 270963 965793 69152 576898 766772 767299 253415 145037 109520 436964 917353 412920 463926 854784 308896 329831 587339 267990 67597 726356 444360 297239 681032 238491 906388 455538 128502 505422 937159 257520 110493 69917 216478 122794 349916 228905 177119 710662 95485 687255 363069 418143 259905 198926 621084 539708 334579 129933 82828 714396 343491 431929 489796 721215 442161 406301 417999 79120 384400 595077 433602 532520 187061 274303 310595 819716 724118 393445 502890 572665 71293 557233 152312 953816 881809 69221 370269 687961 870360 749423 647085 13618 655870 348665 372942 437929 607851 926158 435047 782063 541638 405939 990690 164850 112665 685699 223994 947183 755432 972164 417434 852268 662400 902273 528294 108828 636315 753360 216340 130390 700608 889123 663271 415229 429831 512943 705428 545270 908724 215783 422707 593892 75745 904165 283556 470640 729315 460205 7548 384421 865696 199828 863910 298407 522002 878547 288220 190312 392839 714992 301259 757803 353536 910615 905679 808057 275154 862374 191408 45964 330632 982502 90704 795875 154111 243311 791571 682949 907440 974168 940511 271389 951871 307346 904209 615438 383283 31214 501080 93382 185737 601456 398338 487285 443827 368427 435472 103066 20600 993795 272412 185844 250332 831441 73265 888141 855404 9500 17053 112161 434583 249645 180272 213316 475864 796420 777735 196270 737287 347215 112095 567951 829823 452689 550730 83935 125750 443462 611126 641086 941477 418157 871672 823025 56783 467975 979367 308165 66494 938836 659308 597933 326417 267624 214456 948227 117971 503062 632289 76594 491116 38597 900587 308932 767211 671616 463862 177635 383059 521202 809731 882277 878048 207467 631576 272347 915234 491175 553405 961022 435173 767196 332166 898002 282254 393233 160537 337963 967956 662661 579379 34459 87527 513969 218867 863387 444711 858085 845236 563883 897617 861737 796386 871453 306958 361850 447838 644431 993445 213418 406444 595313 681093 932031 52739 798618 503179 426752 531020 932123 953621 594526 10454 788935 742124 348063 291943 914672 975573 960046 320003 79939 648089 445353 84544 577921 55686 319868 771668 252402 700651 822992 713982 219641 77616 580386 461086 20914 134321 484223 511320 219736 3931 12526 112840 944452 191583 958868 39390 530498 131652 309347 896907 312623 39391 769242 846885 608615 715768 468139 724708 466120 104037 310775 407879 244185 920986 37857 956523 12929 509382 287797 820270 664379 927532 500308 546865 193102 149806 192956 109274 32075 703768 972545 357948 571944 552043 28513 44260 283188 993619 171707 291278 335797 665046 667183 652692 402280 373225 238022 219415 296834 589194 236111 342569 339976 80572 400616 184608 910396 41066 139092 941669 558721 212547 964122 700713 648822 490593 993608 492405 706425 267516 47274 88454 60011 651515 710825 728959 75684 712237 279937 954048 496541 103243 495081 676696 945703 737747 645665 987113 362374 262754 495972 976364 619081 26894 816820 617627 133336 344015 938248 543995 304417 182672 303800 403336 266102 365803 438956 486021 559061 425211 177370 228905 66381 176875 811480 490281 252196 542591 889576 446839 157089 881843 664929 641755 153453 47780 341210 148483 675156 355416 838998 107395 728705 588725 935001 615615 745092 535487 471553 993450 355045 537605 592521 381842 1234 218607 9607 609568 543468 780261 439428 527887 311502 409600 161530 263454 540030 886280 38145 54628 613606 433742 745341 237461 340448 883686 165418 115998 59500 119896 647067 759547 961743 499233 723970 183780 705651 131945 901077 917308 432197 165426 449525 605907 273068 744406 871522 223291 723758 781987 549379 537513 816920 687825 956843 6018 48106 430789 230355 719842 490350 749007 759954 253531 791147 464299 292704 695757 553272 308370 214313 701987 514564 63305 857614 432487 669734 750745 905529 285726 535954 118371 697162 373399 696025 337195 679167 472503 473323 246937 332288 877599 133966 347313 930127 729670 812937 239209 682885 276256 789650 204222 329714 401645 185288 359063 558151 357813 490252 919967 680257 38998 915662 485699 411404 841158 391821 973290 739002 895963 925715 410402 593649 125909 622932 993583 935058 944985 965180 513130 47091 125234 99624 549248 578357 732998 524230 916943 101814 244913 898178 46411 95154 661171 479098 90803 480534 447561 568768 290658 127279 30769 896966 583480 226563 358242 523698 657938 42720 573118 323267 731268 350632 998795 128002 849586 636917 283690 188025 617783 132465 875988 959615 571261 585799 854198 932971 420846 225184 134926 185252 932251 605912 765825 725179 936952 186936 265520 526513 611853 589226 541751 523761 209628 329504 273801 468416 647999 115605 375872 103141 379832 61854 253720 874168 346861 261563 29983 707282 606434 120564 357294 926837 220752 29878 552476 844696 871947 557293 679248 951999 942674 933114 835271 12926 298639 53207 122787 261302 181737 46230 858309 907052 466398 151056 350901 708932 69365 991311 559620 736171 94950 755521 679580 843208 407496 355122 602410 227317 889003 581173 356864 434998 169654 571582 50693 312381 368872 899043 732640 231158 521189 997064 1155 993439 607657 50863 136948 928044 469182 113498 682497 97852 78856 265298 220124 388865 709935 507795 495824 317048 156550 356402 678029 918249 527900 839754 132152 801694 696555 960119 671775 362655 561566 912620 102039 472748 706156 114343 972999 475727 670190 119452 378649 561172 55039 956508 489084 606674 507939 285988 783815 604557 692962 16855 256812 265081 53765 504885 763539 505470 485453 740340 311377 242887 822580 294352 536100 768277 45700 297243 480518 157613 332678 652477 881169 367036 617713 953482 237648 927110 829637 903869 831516 18644 377312 537855 978278 207511 132074 711189 219221 735976 530179 120485 129388 292988 632643 966416 571930 823794 218866 779517 87585 570241 512159 884377 287851 619437 983342 313653 151633 434759 398955 626434 748020 395404 317888 871336 867885 145813 118663 347670 79420 273786 13576 165007 583129 502813 632232 561532 129530 495101 216753 920141 536113 226827 408742 153787 383738 260236 755336 873583 179936 850783 118445 501142 1027 402524 377360 516777 289129 259532 557761 246020 49352 273460 533925 851674 180670 46798 715673 229843 163130 406966 592101 706616 344989 871256 505401 999284 996269 475214 548769 786364 755516 553888 237674 472411 265185 582478 856958 814451 147483 150782 848566 849098 874952 312334 296394 594702 561487 935412 81938 962849 70914 182901 529082 149581 643112 279645 308604 635027 276898 978610 684986 325116 799936 544911 862039 771097 498145 538810 394196 163467 836792 49820 650932 811178 927032 380341 94849 488190 585068 361160 431404 134890 302221 613023 789018 330688 394058 330540 535003 531053 399164 763920 714204 99678 482424 301769 682691 815548 658315 634536 958131 459849 716342 595970 889791 460516 252578 892541 880744 6322 627793 853602 653072 15240 185354 638639 68653 287447 732504 170547 778975 159886 143809 178670 713412 809593 86296 54329 218193 51074 415027 992516 598379 473447 690770 351078 377291 401239 908448 923105 29744 202034 415335 412288 866454 641712 176687 686129 910629 930000 404182 367073 911681 672351 119518 723883 669204 167818 87987 385733 715402 464451 450176 629116 415306 554652 618102 145244 235852 213343 450840 344146 910422 91209 118072 808576 889201 939365 311987 769413 40059 230560 525337 616379 643970 33724 75423 221445 643065 266842 24462 626994 192965 610669 395254 567755 697734 168549 960704 526693 888672 783829 403935 915418 504300 387064 346458 470789 913109 973259 47439 727137 633090 461292 107197 837523 843619 612949 708466 128565 75133 709514 45693 906223 986389 910397 321704 609573 787826 608556 827401 401036 894450 104267 54464 759206 681868 351037 415782 448060 617986 840095 113058 983838 924186 300125 478771 349652 539813 812948 525249 471876 433970 936303 617493 391249 548489 56758 813553 298983 251529 942143 851284 606819 339627 359919 861646 713680 531462 187924 515639 435732 897392 21351 615570 350706 636135 229055 232918 982974 899887 163416 362179 500996 24148 489946 160915 280224 729948 338834 423138 960464 529773 143417 860233 550789 729545 844293 222529 278878 782745 98972 717216 967371 617160 462456 525652 655189 959638 554140 628890 864360 63575 995259 880193 407617 691733 145180 279681 628890 810494 509392 976728 599198 768953 506150 500046 286230 867658 851934 84911 297537 55033 74622 424189 905517 543596 828699 673952 234560 689849 464938 543248 677173 391060 474541 768982 585295 104381 217909 237047 604960 102036 480620 263296 832403 736481 248025 389137 801287 160132 536866 404 702769 384610 307328 680529 580470 846113 808608 126306 363854 445656 732098 451746 424939 749130 221012 199074 531597 716716 195052 117799 231852 586436 84699 759334 676461 374106 785180 15303 580377 221955 282278 633749 379370 31166 936193 166232 480676 712256 589542 166042 135077 507693 325820 853323 691216 628590 167699 869809 143604 653895 575323 140967 237953 832503 289658 422294 231844 31756 620173 368110 438385 895812 383322 292800 21134 818492 431984 509005 203081 218635 389077 694840 887246 95546 615549 152992 166090 989115 690550 699467 477869 375835 384627 139748 156447 761317 252995 289085 343381 287868 293899 726424 660491 729934 255260 669162 57061 404 889716 569954 555130 779516 132463 348220 66374 973552 955915 935587 534615 178936 576269 159940 944167 670557 24833 314954 111738 109078 217105 152869 733515 4445 118906 176977 589810 302260 831918 302456 421018 766885 698288 291446 44443 943962 505809 972328 392451 31433 707809 672001 411513 494466 693257 380149 942644 621064 977554 825207 852104 751311 740497 274350 860282 450854 195664 21502 63011 843790 589494 377227 456963 351394 330204 994643 305311 419781 704880 139683 436078 949419 84393 3116 313526 54507 470134 733904 975943 180986 120527 756392 357968 3407 332465 305944 334538 414916 502095 657341 860376 780353 501367 710390 578386 203592 236313 895210 16229 56272 460985 611737 52887 5383 806631 437893 494923 954929 460870 103167 981118 529886 254216 815560 685832 133598 731236 74447 186849 807742 159089 357564 186595 766514 563307 789720 376676 351519 237305 413860 883378 430862 158812 105096 476128 594275 305990 760612 430668 174802 465763 144411 574589 952263 670864 37338 799935 879478 696210 738274 370209 882632 839576 540143 463856 865791 574127 351631 176141 538156 717494 537181 82891 373088 249495 978230 302039 920844 296306 860103 313794 313511 115619 608947 957147 898223 936698 410188 561536 613966 248581 201460 719451 986681 435568 600354 841680 471795 83485 900766 881254 284072 596788 557249 429511 402865 940914 133674 524343 383409 991628 516178 861704 213008 117150 219380 615024 953377 514836 677648 159962 80875 918864 200884 856951 835658 817561 512080 706290 151143 108292 686385 734792 878584 653659 284075 341835 796198 215709 505620 777702 405347 577627 629822 732645 302749 3711 812587 957450 869123 803307 222485 454710 781554 323960 104078 267737 804982 1793 721743 881704 419301 213375 610315 698326 754214 717054 867103 311322 162868 652615 819346 316933 64290 437682 692013 361010 952766 464683 907851 878928 56024 398673 449206 988773 824532 321857 117204 372062 860626 308497 918573 826304 815520 114805 525187 165155 198618 849323 977193 780774 9312 161086 771967 443646 234865 62248 708247 886154 215464 919821 244350 41549 132098 822771 230998 259147 873287 828402 160445 691051 991424 420209 309624 939008 581784 471936 575685 580497 834512 985529 369892 874492 819988 819915 838942 559615 690590 188153 54259 50301 472162 672867 230850 303000 344393 440689 172389 925320 571193 438081 467312 271727 72593 199688 669293 751635 915844 105968 194226 497985 384599 555823 645434 776829 874855 71347 72986 186123 375284 126304 449429 535258 813455 371867 109407 932837 727520 261094 305089 68876 635291 250321 380189 818513 179330 509687 894705 136571 880071 70155 376020 104975 389773 29418 221338 710795 366763 66204 434652 861890 127026 221005 963120 482980 466742 374767 269516 341418 273184 999476 168912 800637 496948 450316 433968 374554 831944 723769 340050 823583 225718 727340 177196 742995 792750 167437 981272 159973 488530 88307 623318 569735 434159 347865 777319 781317 693487 380421 335827 885256 39916 255467 707794 398333 206377 809747 789112 911435 839982 846925 649558 713030