1000 1000000
437 341 202 441 59 953 180 506 793 193 503 14 344 794 928 820 815 532 926 248 562 902 313 23 905 388 965 185 467 633 738 778 847 692 418 687 87 251 894 88 736 756 801 949 117 762 132 116 24 538 727 693 645 724 595 736 484 849 57 425 773 71 950 208 119 133 497 583 747 658 818 644 951 710 99 183 818 133 324 244 920 254 909 133 781 526 222 722 554 398 893 835 396 609 136 488 859 89 63 851 88 602 769 940 523 426 380 271 110 447 374 655 215 662 527 575 654 606 827 55 771 63 991 618 409 437 892 269 350 229 799 214 107 844 646 691 586 491 719 815 856 272 685 272 935 144 245 781 341 284 889 715 642 847 734 464 593 610 387 793 259 75 757 614 441 206 288 859 986 909 32 894 762 574 656 749 649 115 772 951 365 853 832 769 86 538 932 214 151 532 948 467 883 555 548 582 276 486 553 900 215 757 765 855 164 428 584 803 377 127 31 913 466 375 499 74 64 878 300 548 664 71 459 123 656 70 430 884 687 950 881 802 940 441 735 517 183 645 126 24 549 55 424 618 422 701 551 790 438 647 571 184 422 553 469 922 137 470 538 407 934 450 790 6 529 914 276 827 365 18 867 109 234 616 848 943 755 979 115 562 498 486 548 897 857 677 73 470 907 539 88 243 1 963 629 506 578 165 264 96 692 234 148 925 157 437 524 718 278 621 821 555 332 832 581 304 361 931 665 90 971 197 453 617 545 186 691 198 333 742 490 605 861 81 191 825 183 886 242 657 831 380 424 768 170 757 876 475 252 313 347 494 709 186 370 589 340 723 606 435 88 249 167 281 895 164 530 412 21 531 718 385 163 502 151 603 997 703 908 193 764 118 218 555 196 489 136 630 766 590 150 785 46 440 378 620 757 158 946 294 567 774 817 630 354 866 210 241 884 267 905 505 318 986 736 844 878 228 848 102 573 726 521 742 417 394 179 130 525 181 144 222 907 933 887 206 599 247 87 927 264 803 683 914 532 583 989 407 906 693 983 73 198 660 144 475 469 881 779 927 331 802 183 303 867 623 538 469 907 918 51 315 500 652 703 102 589 146 135 725 250 328 914 543 531 584 437 869 153 130 311 332 736 61 496 704 542 226 310 248 261 580 433 518 281 798 924 77 747 343 187 684 666 90 447 107 118 199 892 108 740 581 528 244 479 715 541 459 373 950 162 471 421 804 124 37 23 17 258 251 347 920 662 738 991 229 157 612 547 664 75 958 828 77 816 418 493 751 649 318 376 539 666 762 149 691 691 46 285 872 107 588 287 275 889 442 9 39 40 33 346 355 893 613 293 252 288 832 313 474 88 78 886 517 963 293 336 947 202 214 616 668 75 22 574 914 109 847 809 66 210 615 769 618 427 44 770 510 660 396 104 397 421 630 838 406 476 574 219 620 589 796 824 948 178 785 812 445 845 247 76 801 572 655 508 896 335 429 418 279 983 526 277 363 889 77 160 20 562 534 206 85 446 132 878 71 472 950 366 821 727 983 696 544 779 409 191 509 699 636 56 994 788 760 74 109 521 379 912 274 831 790 218 400 222 185 538 458 783 775 886 514 511 782 488 568 396 256 450 575 350 757 653 525 415 898 429 315 547 66 933 970 858 677 765 352 793 263 124 932 222 483 668 855 757 108 297 974 449 628 464 936 446 513 593 789 52 978 592 358 499 421 838 211 832 214 315 862 664 940 677 669 746 163 287 586 587 135 383 121 742 881 903 158 808 247 134 209 113 54 674 872 790 675 475 368 348 348 355 900 497 668 118 657 337 679 537 558 103 46 99 534 614 448 186 192 886 690 373 554 232 474 570 287 631 608 490 425 72 60 372 889 302 689 528 524 144 109 115 991 947 548 565 425 744 7 953 208 106 132 930 620 914 898 640 867 148 549 284 349 473 35 514 310 880 261 147 499 490 771 661 726 857 949 51 606 793 127 916 567 611 338 875 915 475 221 219 678 729 895 872 424 600 77 849 64 474 138 305 539 42 582 274 226 31 161 291 394 307 375 932 524 104 461 130 490 883 533 846 236 632 340 739 593 63 989 475 930 208 335 972 747 361 50 979 334 797 727 447 762 508 234 141 64 80 538 26 924 702 643 855 211 467 326 33 685 676 360 533 131 793 527 277 157 735 945 608 488 450 406 697 872 61 638 156 810 394 443 802 922 76 17 281 837 507 360 103 25 242 838 507 456 881 363 575 864 289 517 83 221 204 983 472 825 225 386 820 771 552 49
46939 617912 959927 145054 246497 646597 918476 241030 606003 731142 864416 78998 510000 455890 499552 897519 62996 318123 430860 968953 482343 132649 98953 459868 803610 434765 530223 711276 731171 12103 724371 261907 323229 136306 678543 690735 815333 58659 500100 624646 276910 920287 473283 17887 752757 274985 378498 684325 949468 615318 349078 817368 150329 626767 884752 184027 145253 696383 226834 704232 153047 792133 168477 201702 261595 622799 358481 932329 434405 80015 854556 967190 137636 446670 163958 351583 735621 314550 339183 122324 963632 441047 370334 685896 852134 489092 734640 415122 35776 966835 894215 187170 720387 582565 402345 419850 718388 336603 311954 599669 58906 836210 544748 631627 639731 167556 844428 709319 470601 721411 908329 787773 806077 280640 192749 961380 32059 344026 162739 410746 838567 867461 676700 40477 30060 340826 175307 111972 491443 712122 963784 401390 780898 58786 741555 271772 768366 888879 952612 999787 29038 962538 930872 840945 260084 265988 899906 488902 274701 796574 954254 539987 184264 679763 211441 886050 539034 847524 294928 994549 986920 437130 716734 45413 295517 358692 852649 372288 572931 621555 541030 332300 216208 406629 967884 614043 671731 650619 673678 699691 810952 946219 953804 271660 643800 795317 398604 111926 620458 286309 999455 261247 911194 383004 17277 187110 944360 545149 586876 565935 712671 447279 536225 80784 68015 697673 737963 232089 743448 108245 421324 844803 681413 229294 117640 222485 80029 994729 658869 633409 410499 934408 362413 35423 735112 318311 567274 197406 841430 146533 45454 78018 636846 132285 21536 123103 920856 512914 252462 13732 56374 265602 757132 907020 981774 418713 441197 156825 614898 70482 335590 467201 487543 368116 893510 158377 958885 361877 802762 738525 645949 952839 879260 732268 588721 631347 787987 123426 830030 898496 439273 346565 809562 256312 477506 994110 120722 266954 698635 63559 389673 675848 839359 268511 165697 685999 260123 666303 811490 554994 406849 157356 159465 675732 452366 794829 89446 124541 194135 141396 863767 261617 537877 248088 269776 961522 311429 571779 907079 205729 676548 73507 93634 472762 942353 88299 350361 31080 772514 335028 641939 878513 788304 94854 627767 953467 650866 605472 770660 633443 45016 856692 675931 309561 354106 9594 797299 499944 339520 545167 956577 260884 262178 600875 208506 963665 77515 955785 932957 93058 722308 954228 457397 369588 727792 122135 410640 670642 108896 589160 206401 121460 336736 452429 372848 51653 42455 527268 548866 471560 264307 970485 242390 623170 563751 867785 619503 732289 402204 300685 889270 435009 418815 490576 42481 114410 806770 167385 963371 454881 417656 775608 939090 478899 231850 77301 706858 190773 539850 174556 381408 670888 189741 455899 485358 955968 162972 877421 563520 753464 332171 485612 651701 409991 467360 639409 931084 331487 683780 403122 167608 435738 480647 633204 80031 101951 211804 998233 28381 715774 856406 631840 4775 434110 740992 531104 244801 222336 600920 980940 965536 897112 816576 428991 708264 724099 45273 80585 901601 416454 556033 829300 297887 318948 412082 403966 811896 904795 809807 579645 685736 511408 746002 305694 234550 834990 801530 766777 902255 13883 332552 762451 57255 338676 391020 930769 458365 249581 586597 514613 190240 207316 159625 896037 734536 745817 75371 147882 396643 928658 904013 106609 975699 905131 747416 919590 570353 908993 396619 837694 194013 891215 724117 190726 105607 589222 602540 579313 644577 495932 830420 177876 590539 375000 819753 751237 568894 377446 399872 27539 127713 46544 485780 260741 289445 598862 185453 779849 410688 524171 607862 214246 850214 335320 624109 681724 386493 446683 740166 945322 737741 76466 480057 132548 46324 689926 427518 790112 40872 778650 289662 899411 494929 478028 980013 588461 96269 885454 288543 752788 383724 209717 101730 650437 133348 535762 980860 731129 524636 950910 392010 573399 491546 812473 822610 386528 831093 803963 782646 40677 401862 112241 818033 158218 792987 273478 675031 323754 701508 66850 20406 380794 718170 312100 238637 162006 735401 715824 950062 802986 22579 194921 472168 682357 964873 906966 18852 942079 687276 347685 16432 973496 701954 603300 437202 880481 813967 140346 1111 716343 527204 275944 441559 54439 714428 865989 49890 187957 331859 596132 641767 274667 6843 875549 998369 117601 234514 964900 434863 248001 126580 121983 191176 308614 42544 963676 323409 157699 232809 570744 512490 771160 177219 994206 974599 486661 260024 927953 306018 402302 908968 352829 181579 900634 916678 444746 668092 690061 860795 854054 621014 811539 129968 742918 251852 707479 27138 33330 219040 888949 574757 955714 412422 872637 877308 529442 41548 841304 402527 799226 912430 58372 963365 589271 140962 301930 177801 101938 595316 736484 981630 888853 882448 356100 674837 267609 826612 539016 290709 34504 657788 393702 471560 697141 124906 783265 440001 721534 467090 591266 296917 533703 984113 280137 43828 580565 777840 22640 651774 460066 17305 502313 529248 628083 12937 825382 783579 798965 916834 274749 168318 916572 206472 478509 800274 553386 807911 605346 817349 871297 150068 224787 516236 77464 582087 291457 265223 214589 294162 328398 93131 882487 348950 148597 637243 196674 757762 538392 636622 39659 888546 193064 755806 2977 846722 359401 34493 729605 704967 429026 635255 809460 424005 236364 306491 312783 154396 677913 416352 241230 79243 922815 564086 787989 309653 822618 703810 198354 45609 673482 6933 481061 715194 159709 712658 628844 854156 842960 925099 444472 244178 318510 334803 265311 529346 3585 92829 803912 964331 176267 216152 777248 135805 859451 389268 474990 454436 336185 952102 51483 712414 105562 994581 875372 188380 475796 238512 508300 413102 265622 202042 279400 993364 502711 776135 205858 980496 598797 882008 492107 440961 319036 713400 96798 369067 109331 28094 465395 547674 147005 703012 532318 799612 995189 582912 505371 495153 149417 692920 32977 629859 553766 344104 753185 72692 430345 777547 92244 158886 862292 616877 158780 28180 852395 972883 989893 748985 589274 308032 691994 112943 63883 190473 189632 463277 778154 945226 321707 466790 89134 564509 399182 36338 969075 42803 219203 153824 661509 579272 49885 497399 648288 957678 42493 856332 75537 497171 553992 575997 441518 283114 783087 474944 649014 909502 477799 712804 291735 500697 400389 800235 668066 47289 71863 831249 834635 480211 675430 262789 202592 524368 569313 539738 694123 950048 833419 474558 44430 390077 794028 582089 337049 368412 760352 483418 729945 226178 111232 455224 695710 792609 185814 511164 288124 806824 709393 734097 988377 236784 314912 671233 163414 425574 915600 845496 598245 864800 822273 267918 651793 24846 939427 29797 765038 837435 4238 593476 436811 979446 578119 143387 521177 950699 245684 938954 32058 298682 534548 314244 89889