1000 1000000
308 530 786 340 960 855 601 163 220 643 905 794 223 47 373 877 43 329 351 481 575 822 63 273 488 483 115 839 25 93 189 249 370 959 846 745 952 843 377 103 32 333 439 575 370 515 543 662 977 941 371 754 405 378 888 395 417 103 519 859 616 305 330 883 152 907 96 661 231 896 124 908 956 118 646 772 662 521 520 251 391 698 925 131 52 420 743 160 788 517 371 889 24 786 65 18 370 845 280 400 561 153 739 730 699 542 619 161 293 570 388 818 127 711 314 670 61 379 156 396 802 917 736 985 563 821 130 613 43 836 515 305 456 297 146 719 949 375 38 174 7 276 214 935 975 75 600 959 995 145 441 517 513 732 832 774 460 368 600 485 846 213 815 614 509 160 845 189 34 883 121 717 660 662 565 196 919 844 763 92 209 985 114 485 19 247 161 77 329 851 257 757 969 254 480 793 146 582 103 428 313 766 27 39 59 985 42 120 507 820 117 768 991 854 242 559 375 663 183 985 646 313 294 39 401 433 776 331 803 122 580 359 129 543 656 211 45 7 57 169 711 333 86 315 354 40 303 855 863 842 319 83 795 988 726 371 794 987 484 785 220 242 411 615 787 551 193 947 478 389 134 913 403 223 447 138 614 996 116 134 751 393 235 713 777 967 854 305 584 215 223 585 82 215 961 643 817 697 721 103 908 931 43 981 923 660 343 261 354 47 105 564 234 777 582 134 240 355 777 904 705 416 248 962 167 444 284 35 924 793 841 907 45 981 692 72 332 883 271 98 921 446 6 955 947 108 762 743 883 184 371 74 617 841 656 60 745 813 296 528 923 657 332 154 657 472 987 121 903 781 186 379 165 107 697 899 285 172 316 853 791 64 740 567 399 743 492 338 60 735 455 703 970 564 986 794 805 469 337 319 297 642 506 7 643 31 45 951 486 465 817 512 174 646 17 394 235 165 143 206 102 491 68 792 627 434 356 457 811 787 932 209 971 174 39 839 910 510 10 339 9 194 926 778 387 716 404 195 874 581 705 205 385 816 39 534 27 396 2 120 420 118 359 963 476 168 126 795 886 146 884 411 569 553 427 112 529 723 81 274 724 538 41 371 380 585 243 944 46 614 142 958 729 714 183 715 370 30 914 573 131 490 576 379 225 165 290 937 82 116 6 992 938 815 7 657 633 656 808 426 123 922 370 691 989 478 721 757 93 226 401 300 139 702 265 136 338 649 778 195 45 589 39 751 732 243 799 955 341 994 568 930 258 507 162 178 698 401 9 181 891 143 522 514 240 754 964 278 233 208 624 595 717 214 784 897 891 729 519 937 793 294 530 914 849 256 961 525 602 113 108 82 933 815 983 926 94 527 158 423 619 844 210 312 317 329 575 6 867 822 194 506 613 257 348 297 985 841 363 483 896 548 303 821 16 98 498 51 415 255 656 741 349 962 262 893 159 117 231 877 781 518 910 178 869 856 620 111 666 463 304 434 886 282 995 576 428 630 523 162 367 534 766 153 881 447 539 132 93 812 421 401 178 65 243 257 619 446 652 655 369 121 824 402 567 138 546 949 445 635 780 540 929 54 301 521 202 349 130 701 953 676 707 448 231 726 396 553 706 389 890 766 95 360 318 548 283 728 944 861 232 380 826 369 297 6 968 478 732 156 913 226 389 444 600 908 913 291 549 143 605 657 428 702 296 145 616 896 164 573 68 784 929 64 815 643 725 752 550 394 281 457 619 190 486 463 122 909 295 33 520 920 194 425 671 488 432 19 702 650 399 422 89 706 933 420 717 582 861 114 350 414 174 56 664 654 529 39 511 494 370 312 503 615 988 675 590 445 273 790 895 454 684 982 317 634 616 567 712 904 877 147 670 778 60 825 721 237 804 871 572 803 326 804 401 263 935 719 416 114 791 72 777 290 385 526 175 669 996 928 785 39 72 226 616 439 91 143 619 818 225 162 829 564 808 317 476 749 172 912 184 858 99 713 375 958 450 650 826 887 206 598 832 851 750 896 294 143 664 545 76 32 866 189 29 515 796 992 239 305 931 420 740 804 818 584 268 606 89 390 715 546 724 456 997 201 494 586 932 536 543 368 582 860 571 406 387 610 933 46 727 561 391 473 159 415 361 114 920 923 628 96 565 483 835 237 914 361 760 236 534 483 486 30 61 290 167 695 258 134 127 473 833 433 689 13 26 49 173 3 212 967 587 678 280 607 211 88 255 7 579 845 667 940 135 874 351 308 808 224 130 536 391 971 292 353 960 469 997 765
82710 519059 276262 540484 846647 474652 932743 214784 535385 603547 673793 837814 953778 242680 820913 757211 226029 994720 367425 749659 114754 361490 832444 193504 509205 926308 796199 26093 621415 986954 675313 256295 26121 256985 354629 399967 890514 74143 594008 691734 22453 349410 480382 908204 834945 351283 835037 150679 319932 677907 486187 937502 105347 177069 489917 320186 764359 568971 607287 181931 481708 285211 159845 677366 561675 402749 700082 60977 550344 596684 743876 257810 612140 147354 81262 86165 667995 831323 551578 501900 31976 805244 669567 650303 164567 732688 986130 736155 598957 815708 135128 246288 271166 286105 532800 728573 322936 842752 425264 68964 34706 956615 792038 774142 106613 913498 518262 667731 537646 795821 548112 179603 218066 318330 845268 507523 405708 635150 139155 839300 898389 242382 440201 973986 495917 548828 821572 446477 998602 150904 379649 933283 391924 93721 903364 690321 636594 517135 164741 394858 573416 308194 322240 445261 521130 773980 216023 120111 708851 475432 496743 895041 707845 943892 578049 172299 459554 446321 818504 342657 720989 573663 243820 394860 765459 116890 444453 999947 145323 179429 759194 169688 924169 76619 131061 526416 760257 258725 77131 197474 279751 439526 328175 397988 611274 438465 48039 624983 645557 143956 111624 389515 950389 238648 631118 340663 764072 10848 815526 48952 264941 823657 518335 905669 466229 202251 100971 676887 403688 661380 520871 543491 626857 972917 116033 115334 956409 119094 828215 444183 727473 890795 120510 255209 912822 807623 75098 805078 1759 983901 130621 518401 403219 257021 856582 611460 601711 257093 780020 385391 851870 101168 92439 93519 78532 298879 517088 329519 49229 226484 589898 205948 743804 732350 903725 670878 609411 677779 674783 400781 484785 151538 824663 682009 880629 91480 964914 893244 935626 211080 666956 637212 10441 563316 772528 836468 412272 498328 927845 762275 749330 348341 994276 138932 736787 607557 221807 827918 842832 252205 363374 816491 431761 476537 410627 609486 799424 224287 96085 371230 921466 778371 586814 605703 271853 709903 49521 640557 837344 560138 87071 359365 397596 746208 926099 507535 105389 95356 256285 118021 189179 432218 922539 945901 530738 519546 473013 806927 391607 453930 167632 114636 98838 559536 235743 398165 262640 535859 643063 899662 955455 719486 909369 301076 481822 372547 101853 806218 251088 561114 769996 1048 608897 135585 39673 670878 91955 44604 261069 688838 944052 931000 669558 908825 740940 973119 872514 718188 31381 282882 813488 670527 77351 869529 498382 330956 678168 598884 574274 304214 785504 652603 350748 421493 45455 422436 812795 134436 98630 710969 41788 963427 537820 574456 153194 141938 133204 591979 508041 394819 732534 545939 620178 528542 274789 61622 461601 865128 145268 712516 596479 467182 727489 343453 959182 308648 210484 298752 536560 538928 174544 486856 587116 462133 764380 762639 827474 900410 154887 285032 778809 51933 950287 858159 977733 821174 376369 952220 55649 139361 120287 425284 866022 472531 854038 612162 465689 429978 72351 454619 792803 750709 485911 709495 212826 124843 537895 696221 215125 76420 962804 750645 775001 968335 732526 940197 820063 342068 839129 863745 918094 279259 486348 904414 117989 470905 45004 620014 77026 688110 399576 407617 174066 484727 357363 771620 560881 814520 763929 567352 221957 564386 998205 617089 982756 892944 886701 497507 150008 876519 432474 586856 468587 220770 963002 627734 342512 911765 336376 474498 47039 791719 150604 226206 900620 464125 979847 910978 557665 484607 449335 706804 539743 714052 675502 291009 36228 148461 781170 55613 677804 390163 48061 598087 444500 52749 499558 692648 557096 484003 63605 354002 870981 829546 788548 756009 859985 187702 138653 261275 56863 564173 975117 338024 802951 545360 840934 397411 69955 54049 434392 805407 587248 815185 926332 478740 508134 979055 415232 617508 970267 797165 804311 694862 217237 713251 507119 258173 678570 86879 12556 884409 777228 666739 286400 919545 416326 311478 826073 941688 249605 621574 272118 372271 945186 24462 272769 251765 910572 337271 261291 725198 348106 866856 647288 792384 799340 343566 677342 793402 590817 679661 654837 488732 476033 491762 88650 115402 863719 247652 229169 830648 319430 258500 203449 117458 271091 528068 227700 989414 656798 349544 953686 289284 315183 91048 496789 868398 971016 106991 922329 412198 643016 975134 961351 660672 10276 161658 566341 885919 326468 82459 228119 769139 951693 980594 30066 752653 467270 263672 219809 781407 671412 410249 511753 437210 226417 247874 486347 781934 301284 70244 199034 835213 61871 592545 563333 601352 129084 391820 840314 559205 111642 262368 99980 271374 330998 190496 489194 538649 844385 566999 20353 979247 305170 148936 100096 652516 602100 703682 676278 896707 708116 824038 716390 8089 606622 123425 734954 316962 994084 396363 35643 955771 708643 493792 234613 118906 267166 388953 942088 387272 207423 3612 163374 843887 690326 123502 723264 729040 951480 670261 327378 470873 200820 79183 536312 95029 309734 533046 428832 114339 857763 844281 899344 762475 295828 961191 705081 280298 529118 226867 752042 193669 121215 845282 93875 318962 391911 698738 370708 990538 382502 30719 877490 295470 669259 844408 923712 798526 717823 90934 260768 271570 148825 765952 264119 82584 487675 663531 456304 156104 525886 351628 493905 14810 430508 399210 488099 22332 171397 521049 745282 342218 144552 830348 572677 483383 114406 714441 7363 661165 896675 760270 623723 187365 568521 215420 799179 559240 55109 596894 849778 88454 141651 647943 652590 220387 706654 749198 843416 706977 990310 55010 406430 297826 371702 765542 386886 516575 337100 851128 476181 645166 895625 6270 777487 890836 806537 472216 231056 51211 360257 596120 52627 419355 541554 525108 844547 841344 165581 89633 907796 10615 962847 454285 56219 715491 736390 491818 304355 363744 777915 753080 169824 375773 785908 562836 43101 654471 498793 842631 403989 374124 392641 360192 573540 478743 996795 154906 177065 579828 660181 17476 565846 484474 325791 917789 720805 265462 933303 99877 928460 969097 963949 529102 99254 428652 216811 324477 786274 368559 402318 791750 522623 834238 75703 2248 514058 609824 551935 855273 464006 82575 713791 988899 759896 678887 435954 180824 644820 371188 810843 297832 540144 87922 732819 520164 937242 982633 223405 433744 499825 37164 809079 794492 772870 354931 518198 986564 158336 719794 631112 244684 621793 460395 76568 692980 58961 552457 285224 147929 720681 9749 142096 426105 571270 755563 657969 451219 142467 752260 90249 320190 521436 307263 964693 289097 406992 205323 450524 351587 614321 235350 667910 347387 996063 847531 645291 725495 506883 731239 649211 657899 336008 401840 937349 258068 271319 944075 965717 500185 919416 571970 421231 993132 767346 615929 712656 235941