1000 1000000
27 34 18 17 37 9 2 25 43 2 16 2 37 16 38 8 25 35 31 43 4 41 19 10 44 24 25 24 43 4 43 38 26 5 7 26 42 19 36 28 7 37 35 30 44 42 10 27 9 7 12 34 22 3 15 12 48 46 42 24 31 44 7 48 39 43 39 33 13 40 26 15 8 11 11 2 13 36 15 36 8 4 30 13 5 16 42 21 26 46 50 22 33 15 35 12 31 40 23 27 9 35 5 8 29 34 42 22 30 40 6 13 41 6 4 19 10 37 26 41 31 15 39 32 30 44 22 2 23 38 33 2 26 39 9 50 31 35 14 27 31 37 22 15 12 35 50 4 21 43 44 14 9 43 42 18 34 34 7 6 45 16 29 16 30 12 13 23 21 43 9 47 40 47 43 19 27 50 32 35 34 27 6 11 36 13 28 44 37 48 43 23 17 50 37 47 25 6 11 10 49 18 23 38 14 5 6 33 47 50 17 32 44 40 19 22 4 34 27 39 11 18 38 7 22 42 38 25 4 3 39 26 23 25 25 46 4 23 22 33 13 32 47 31 37 44 7 31 22 5 37 42 28 29 35 2 17 10 20 35 40 44 17 39 40 37 15 43 20 11 46 49 38 24 18 36 17 41 38 27 30 31 13 38 50 6 18 40 17 31 42 34 24 12 3 42 43 20 3 19 27 40 36 47 47 41 45 4 38 15 41 33 42 24 19 45 15 31 36 4 31 48 33 15 3 29 24 18 38 35 29 11 37 35 3 49 32 31 13 24 10 15 37 43 19 36 39 31 26 4 9 14 3 2 48 31 26 13 41 16 29 23 48 3 48 47 25 33 38 43 13 15 18 3 27 5 44 41 26 48 21 50 8 23 47 34 37 26 47 23 38 26 27 3 24 37 35 49 26 24 16 12 39 6 34 18 30 25 18 21 44 42 38 26 2 2 27 36 27 14 18 33 30 18 18 28 25 30 34 33 11 10 40 34 27 19 7 34 25 36 40 14 45 30 47 41 29 33 46 36 21 36 14 2 39 48 47 12 44 42 32 44 2 27 18 44 13 35 27 33 32 11 40 34 50 34 17 8 19 23 44 40 13 24 26 7 13 50 44 3 30 32 44 32 11 2 42 43 6 46 50 30 32 22 44 16 13 43 40 25 50 21 31 7 37 33 13 31 18 7 38 34 18 20 2 36 41 9 20 49 29 35 28 24 43 12 18 38 2 13 38 21 23 41 18 19 24 13 3 38 33 28 31 25 3 42 6 39 36 24 2 24 27 37 34 35 42 40 12 9 12 44 19 21 26 21 27 48 19 6 34 32 6 41 11 27 14 19 5 8 11 9 49 13 31 19 29 25 22 12 12 50 3 6 12 27 5 36 5 31 19 33 47 14 35 40 50 22 48 44 13 32 4 9 22 29 26 27 10 46 31 24 7 44 24 27 33 39 25 9 40 18 9 36 28 30 4 34 46 20 5 39 24 27 49 26 47 14 25 14 34 24 35 11 32 13 28 19 46 47 43 46 15 7 32 31 7 2 46 6 10 13 19 16 4 49 14 15 30 10 45 50 48 31 10 8 26 19 49 32 21 36 24 6 47 41 8 45 27 37 46 49 44 22 48 45 8 12 44 3 48 8 20 34 3 38 49 5 25 20 22 19 43 32 8 16 3 45 20 17 11 50 28 18 44 30 3 41 10 39 5 27 22 41 16 50 22 43 44 3 33 40 21 19 43 9 25 5 39 32 5 10 11 23 6 4 6 35 23 21 5 3 16 4 16 47 15 4 13 7 34 32 39 32 13 50 32 14 39 32 13 29 34 35 17 15 40 8 27 25 34 25 35 29 12 13 35 37 40 42 44 2 40 11 32 20 17 14 31 5 42 42 21 14 18 20 45 13 24 9 27 3 24 21 31 14 11 26 49 15 10 48 40 24 40 13 24 12 13 45 29 8 26 39 48 21 35 28 14 30 25 19 4 4 45 50 7 34 12 19 8 36 39 2 27 48 7 45 13 27 45 26 11 24 15 36 47 35 32 44 28 36 16 11 7 43 11 25 38 36 8 11 10 23 36 47 38 50 40 21 21 39 38 3 34 22 2 49 8 50 43 32 26 22 5 4 48 12 13 6 35 44 42 30 49 49 19 34 13 33 30 49 10 36 5 25 44 40 7 44 32 49 18 6 19 26 25 23 43 12 4 45 10 35 29 40 31 9 17 27 13 50 18 4 15 17 46 7 44 12 26 41 4 29 5 12 23 38 5 12
171341 621126 563958 107486 324780 462596 482804 554671 390240 439395 489472 934825 704481 978152 750830 918611 446825 971315 536475 386815 186104 311637 643564 279595 687208 780884 632647 581284 116119 395018 881358 745181 577030 768387 502217 775079 571757 357210 637543 15868 144702 146393 793473 161124 275610 102291 718370 853387 280725 400870 626102 91061 648592 659257 271968 679845 921348 976998 63071 351830 8314 549464 822991 973679 180426 556000 379976 193133 444957 271952 740841 838641 39827 708216 716550 544032 452260 685627 181131 479521 302758 885585 615319 993853 162153 337074 664230 192282 483485 3288 260210 958661 212510 254842 211300 577098 215811 374967 913248 689724 40798 191343 783381 483232 696576 500850 249832 630597 226887 88838 69533 579795 108812 107688 949938 670212 50368 662920 284215 649263 332303 257492 432200 651365 187618 719719 461626 853243 778752 953942 447875 761000 430338 835197 23014 210884 857924 840896 238797 57582 104930 84577 395896 975590 151221 147725 607484 251351 659434 44507 626646 250262 694243 760965 374814 741796 181828 522969 186507 755449 755929 18606 60158 937309 553848 103397 638856 186751 76456 547122 139747 630941 142169 237859 952667 88688 236254 293469 342757 342668 339711 856052 436736 84243 470556 747270 299587 737462 194991 36986 622862 273075 368311 175084 263369 553415 112490 314850 475881 550854 232494 825397 503941 51327 207244 316735 556412 939953 987844 913486 391855 648459 546888 901913 313362 193138 363108 564629 922195 938597 784491 75939 481326 637351 257118 593503 950219 711673 639416 204755 37774 228728 821943 68985 303381 366895 144699 737567 927470 334043 567118 816760 130483 372248 698505 636605 862822 632620 32826 88156 201942 233841 331061 891787 673527 672109 398336 512184 163235 893978 591825 670454 250556 482009 929289 96693 158086 846762 48927 725074 612628 565609 122546 888048 994742 961634 421935 280537 854507 77835 188037 957098 316710 537225 197980 889179 366010 567391 802861 984963 557215 361554 739796 397471 407961 893344 935760 213712 517261 160673 234879 564286 524291 446556 833118 882303 352390 72451 24265 270490 342873 505727 466441 213923 273094 651153 107121 30014 203945 96784 779681 108375 481792 630765 74123 385209 438525 520851 282431 662425 16055 404945 89862 173758 42125 12509 790053 66621 397063 480515 790653 280600 374828 279841 114819 731862 766239 433832 169699 256661 217490 546505 379590 811978 685767 426987 625250 411843 341526 164331 540868 888786 644165 930000 325134 459434 233051 645419 758648 326557 618176 964119 738081 974066 713038 648224 642493 841188 658796 818987 681062 438812 228910 197695 870500 547285 751116 677665 767989 352178 993795 632867 602285 774168 20375 615904 753331 849349 978445 851238 878824 812767 325887 747608 504753 186290 471691 727668 156566 294243 104891 417538 797457 707982 441245 500265 267537 148315 175608 222128 280207 587518 462418 256900 400468 436337 959648 406571 778376 842070 344465 370152 216139 510326 764691 382380 70478 469755 12004 266793 397291 748568 666217 435057 4398 785198 460499 955771 639840 70273 281067 328197 485796 613938 862376 480838 191698 74387 587782 51068 780510 778984 99238 238299 278660 41521 702907 417823 433880 628365 536438 602314 389319 148610 497213 997211 334811 696176 108642 27200 821336 297211 775368 668556 716533 947136 484939 900768 533761 668465 7171 106394 986941 815797 616222 855176 642448 560365 829214 172506 641143 734368 553519 515665 52502 865180 39145 708149 142983 607896 891483 408717 388234 196029 592305 924179 186608 737229 147657 955941 119659 292843 903557 812543 288201 767950 314649 715099 694244 799524 366980 832560 263266 437145 647091 639090 687513 95735 543040 833281 37447 350797 615486 612263 353415 396432 857493 371446 991524 813588 129197 925004 97858 884554 687296 101011 739793 567592 695464 459145 563753 443529 566447 288797 520422 221211 204075 776214 802780 336299 834260 750599 36087 749545 417750 835696 577497 217165 634061 557305 999921 955690 207563 179518 52527 453532 862188 517193 188828 900652 146195 726556 83797 73550 232115 528297 120615 830062 292878 824095 427566 485240 868910 113211 545271 986081 949944 314685 645616 77984 433164 89449 822124 6746 344985 951771 75265 219163 477875 250907 728516 28642 977140 249791 102206 833771 808730 724474 438130 761558 330934 539813 883442 637463 134049 661717 800116 144828 627421 62113 93611 114514 107935 91817 101378 262853 710845 791553 186174 555480 334404 13230 587637 825128 276313 395179 226331 534619 729591 381368 607760 704113 941263 782780 37694 311291 236049 83578 82707 311373 663045 682026 217693 878095 898790 800507 193666 107575 364455 227392 1994 472080 586102 844269 259723 654840 991422 402362 202756 238129 817050 468727 717743 265949 64216 141734 807398 162872 947889 680334 264608 390435 984023 234370 872505 818765 588095 553824 176065 582144 522950 932971 491605 901058 459444 570572 769595 140193 603894 82670 907573 475311 316479 614070 938034 82415 264065 855908 890328 915110 323280 356910 290677 161070 587581 666346 862904 248996 172735 467423 433046 198239 270081 94635 217402 540 678234 780358 396190 877607 928265 658040 616896 325513 67716 163478 145715 939131 545715 142646 218686 594101 202153 363372 842654 812409 197692 873681 331877 47294 890492 499686 402081 789011 424936 976216 688561 96269 165506 353805 481147 106268 759269 852535 569712 915015 569732 964031 588834 595832 432155 478426 402970 754943 387729 607698 989493 643200 434722 533472 272561 490615 981866 646303 212166 156336 997817 828398 906666 616360 115935 703131 851466 994878 277955 710056 125881 941441 496313 56931 322270 573392 111363 674380 115728 882913 967982 736426 878467 340460 672274 374718 696100 196814 394913 677921 178869 949452 744835 931519 263755 216610 538136 529412 624476 847666 670732 737270 164437 693563 263172 335132 196305 211874 214337 554923 645411 550803 232046 367204 180704 198820 52744 356201 935133 286374 566862 311658 119904 722523 422439 405053 687099 610650 622783 481443 210492 770493 233737 229877 661844 749176 71143 887104 562874 425303 438233 175144 846316 805495 781929 611331 798205 473513 366834 268720 401694 509677 878025 987736 178694 332462 278650 686595 362701 811810 135038 156860 831796 78086 999960 545824 591470 821069 710176 998214 288911 276710 482307 783080 574208 266788 994392 516401 317277 14132 685368 680244 585701 87983 535882 62626 996989 457845 224487 647203 707599 210731 880975 187069 154428 131308 381290 963500 540978 4660 669601 652059 904811 8943 975380 840644 847743 662832 258349 804181 751513 917263 399872 562563 630866 41554 623959 684869 304312 825230 125488 83117 34715 738506 709872 343127 412946 838491 197978 369531 589521 149481 328769 254839 383548 786342 744168 800910 302549 602995 67800 992224 263533 223643 249551 152844 937321 39212 757463 99301 950484 716245 337648 329459