1000 1000000
16 36 42 23 38 46 34 38 6 5 18 48 32 36 15 13 26 5 47 2 50 28 12 41 37 31 46 29 38 32 15 23 49 9 20 26 26 48 37 2 41 7 33 15 12 10 39 46 21 10 4 34 40 26 16 2 38 23 41 7 50 22 8 23 38 36 36 49 43 9 38 42 34 47 43 37 42 8 22 37 40 23 11 22 26 50 38 2 44 12 34 45 40 3 41 34 47 6 26 13 19 11 5 27 6 19 49 44 10 2 20 40 50 28 14 38 11 25 28 38 18 21 23 4 28 12 46 26 40 6 42 38 10 21 9 19 45 6 19 47 23 22 20 31 22 47 47 22 17 18 32 44 9 37 16 19 35 16 15 37 6 14 46 45 10 48 18 39 28 30 17 3 50 44 31 22 20 18 5 33 31 35 14 49 27 48 32 31 4 46 50 14 34 16 11 39 23 21 24 2 29 13 10 47 38 41 24 17 48 38 45 45 50 43 25 25 15 39 48 14 2 4 20 48 31 4 33 17 42 47 26 32 26 38 10 36 49 14 38 17 19 10 29 22 27 38 32 17 45 3 18 38 17 2 47 27 24 35 32 39 11 21 46 6 24 50 39 35 44 39 29 33 44 15 32 17 4 8 38 15 12 24 9 8 48 35 36 41 11 11 35 39 23 42 12 29 11 50 22 46 5 49 36 42 23 45 39 20 6 46 9 20 8 22 44 2 46 27 31 36 23 38 45 26 15 6 3 12 30 4 28 37 41 4 42 38 33 36 41 25 47 27 36 8 4 32 26 2 17 7 14 19 49 49 12 18 12 50 32 45 17 21 44 10 29 42 6 2 20 27 47 13 15 37 7 40 20 19 9 13 28 18 50 9 27 50 14 29 11 45 16 16 29 21 46 13 25 35 44 19 20 33 14 15 36 37 2 16 39 8 43 14 32 7 16 36 2 13 4 48 26 2 6 50 7 37 50 23 15 8 43 46 49 41 12 29 7 7 4 31 14 4 39 27 32 11 33 20 50 42 23 41 14 47 47 34 21 31 49 14 37 9 4 26 43 15 11 10 22 19 25 28 32 25 34 43 47 26 5 31 50 6 47 40 14 21 14 32 24 32 2 48 44 5 8 36 16 13 47 20 7 14 49 39 2 7 19 28 37 29 6 42 37 28 40 47 37 12 13 11 12 40 23 33 17 20 5 3 3 36 6 33 10 16 41 38 38 47 18 19 50 18 12 50 37 36 50 24 18 42 11 50 33 16 50 34 2 46 34 36 2 16 44 6 39 21 3 39 31 33 13 48 4 15 50 35 28 10 10 47 19 36 34 10 39 21 14 12 20 43 37 16 27 44 35 33 26 49 11 11 10 37 29 41 10 28 22 35 7 6 11 43 12 32 36 28 19 10 16 39 44 36 32 9 9 6 38 6 27 10 25 39 38 50 15 50 43 31 32 32 38 20 22 44 11 10 40 5 46 48 22 17 12 28 18 39 23 28 12 14 24 3 15 4 25 23 10 24 12 35 42 27 4 27 7 32 35 15 3 20 46 26 29 26 28 47 15 42 31 3 5 45 21 35 35 47 7 27 43 6 4 41 4 31 30 4 35 49 5 44 21 44 47 20 24 26 46 43 28 25 17 18 43 30 9 32 19 30 21 39 27 10 35 2 34 40 6 7 12 17 48 48 39 46 5 28 31 33 30 35 25 39 23 14 47 7 12 24 24 30 40 11 31 27 43 8 39 13 33 10 7 8 5 20 18 21 12 26 17 6 17 50 2 39 34 24 24 31 12 31 12 27 43 17 29 31 45 50 46 31 30 30 19 12 47 24 9 24 25 10 19 15 39 46 48 18 35 7 8 40 26 31 42 36 9 8 6 8 41 26 42 36 39 49 40 37 45 7 22 7 9 8 35 7 17 17 43 7 30 33 8 41 36 45 32 11 45 23 48 7 31 6 28 32 9 13 6 35 12 2 19 45 42 24 23 47 28 44 45 27 48 39 11 36 47 6 40 41 12 20 12 42 43 35 34 44 40 8 49 18 24 22 8 30 20 37 42 15 47 10 45 35 31 27 35 26 41 6 41 49 31 30 42 46 38 19 38 17 38 27 30 30 16 12 27 11 34 47 36 16 30 27 42 33 26 21 9 7 9 48 10 16 43 9 25 29 50 33 4 33 11 34 30 35 19 29 40 32 23 5 6 50 26 22 29 49 8 6 18 10 46 15 42 29 7 16 44 17 21 39 2 12 2 23 16 16 5 33 8 11
480477 213509 117744 314815 537264 654208 599275 943944 534775 452664 282985 729051 666160 37873 115893 437432 531256 946165 937638 910649 864050 252804 136040 288424 33606 527973 209538 173803 747618 319987 718166 128227 952001 298034 471357 881318 400812 940169 813182 803941 606473 719053 7626 313914 197389 148425 103926 407856 315579 332320 690581 523078 968365 32421 230902 692009 198262 602342 462141 429013 612841 303428 962801 520026 900307 788386 707635 824090 488655 176021 622662 289128 287223 194869 151930 613927 254765 180129 481203 604277 589858 216319 458566 176636 780656 927417 367333 32360 560880 518951 711975 52266 985771 321387 885685 255029 579084 731258 682768 339159 447198 123545 933649 22219 984251 453989 737913 796315 379901 477430 985108 310116 647343 539737 3690 347806 168006 317219 55380 725163 57760 748361 425365 939656 268177 962278 343307 600110 892014 876111 936028 128857 373180 210386 308042 220960 439007 718407 413638 985712 186222 25594 629951 655632 764296 766608 293757 808321 731834 440694 115239 599921 602500 81369 855318 149916 241620 270553 901524 820153 979111 137769 849421 886669 252387 841208 570683 556878 435559 276056 730328 140965 646215 778784 463317 489646 938748 928829 881162 100636 934684 994375 503750 993219 861933 760124 225781 602872 118984 348793 328374 889690 156094 459374 749886 132666 623842 122570 56494 150038 925811 626438 528565 50012 689610 859233 846124 802619 947867 384338 624516 441912 967944 676127 668117 960555 687226 660512 932960 466108 619608 396833 5867 687337 461788 710740 418643 864854 276183 404449 16735 781955 106934 653672 700079 532485 953036 389753 568258 699336 992137 816408 265112 396514 490905 648202 381811 822286 911722 941048 546807 335046 838021 661015 536831 939598 545839 138040 460032 427557 699196 748240 229504 260689 995012 625892 551026 179443 949518 454034 429896 63898 333836 829441 27950 177135 199247 349315 960477 519952 154743 558038 77998 461282 15206 205132 506074 834572 121037 205644 139217 433714 666530 12770 52408 376300 103994 492520 284821 467613 773436 451947 145501 126493 444147 396142 306309 143070 19074 361946 907397 323393 928208 573622 258380 573196 948076 704139 213134 159121 865204 440019 244379 800339 760418 609227 96773 227653 190758 737888 89526 50114 644841 547512 292623 736034 62731 90620 662707 627550 130754 331621 561016 267812 553669 661727 739574 75358 812332 985693 213521 778578 220232 22329 777740 310253 772101 732450 879853 79458 577974 447685 622148 73543 643136 525866 5451 688878 464533 854346 160506 641302 364820 400876 97923 477051 71950 362810 446187 98538 875607 296189 223045 449311 965579 310771 346321 154703 363607 860388 236322 598717 814379 253392 610689 941616 916506 567470 860264 477696 328680 643522 929369 470434 679770 871111 367723 456961 23289 679741 220629 753997 830704 653236 554398 704619 686957 518725 442301 69981 801686 78207 446563 785361 582547 180240 700458 889393 421368 163258 642533 274363 886915 373461 108389 407756 436056 524337 484998 4974 575894 353423 924267 962518 419324 624918 559339 149956 738457 234573 640937 990116 801434 444173 370044 741155 673776 427843 531964 975224 43441 753008 93339 641074 970195 245837 161984 963908 496369 350498 87151 305756 340741 801156 296607 431506 974811 29253 478302 304704 542776 882191 540587 403726 754097 767247 29573 942662 750295 35557 625125 959570 865076 751868 120506 303189 888331 757094 415339 986667 292913 732549 944432 238012 300400 494259 762249 195680 868682 120783 469645 284493 34018 926288 36892 448213 841392 393866 84663 753246 212650 278359 330188 75026 934400 224814 397558 440552 273405 368905 204346 246956 366498 799261 648070 880441 121158 997025 132011 911239 96716 371336 450378 916565 503241 368359 392844 604309 555801 286461 602922 184828 442226 201719 943327 348146 93409 615742 839764 594827 538831 783275 567379 572684 256886 788765 51265 164804 802115 50919 616158 95226 387523 478375 969971 685562 598139 688949 541573 733964 399888 916981 787191 580459 635945 880296 301918 275397 29582 29467 648510 313716 521081 575004 339625 291250 474681 925294 895457 653282 110366 298856 199833 694202 111446 741134 558380 542749 108455 935450 333043 504868 230288 953566 447423 638144 585316 594656 886733 809560 514693 291703 578528 723884 748965 818576 492491 829270 489910 968637 286501 256894 823004 574410 373631 39182 804242 72114 225458 18657 126743 719363 340482 999928 74960 446117 198420 739541 498698 230405 698663 288604 22199 984849 273756 799038 599366 542575 248616 485111 573062 486370 69809 249076 627046 363190 148098 848708 36306 98139 373319 726311 699819 599774 749369 971011 641462 624693 407392 236098 317263 120397 115669 247530 832621 784231 195015 595450 144621 752495 455357 141954 363446 67736 775983 145760 188368 233897 976964 947462 892340 372021 790139 7044 283054 79469 971128 252633 495703 122145 10561 632376 886101 359055 588692 60652 894234 631431 384903 765242 818271 437957 272081 202429 24658 77330 442834 927018 945000 362557 745670 981884 855515 50874 375363 799440 166762 637663 335752 940197 20535 888877 605767 86011 118417 128874 249017 909179 433369 462530 218074 721181 456607 637521 367416 321350 630533 629353 101760 278 991817 178489 866178 779803 699664 17997 354377 459720 396140 570351 720398 484688 696870 716374 313143 948010 184616 469855 763031 317004 738573 53396 897746 193411 610133 308047 672613 898056 169334 212943 31301 846728 384250 277648 349868 255250 404777 865765 655222 24418 890276 484658 8236 518156 817230 952722 561173 91737 875075 587524 733306 481512 699096 890826 156699 766277 986398 671408 175951 38876 702999 502242 139979 324571 964859 962617 490438 203014 558175 209223 802670 382935 908748 330466 389326 78715 244083 474209 490616 83701 17680 536297 471601 343600 722546 357673 240158 499676 944391 865012 566333 174557 388482 140985 124944 695823 688964 611127 42473 42506 177395 514864 611081 237733 332053 541363 882951 502932 45631 900053 194057 895404 181482 185182 828625 230085 678703 445503 177652 971290 232712 546266 441736 732031 856676 234870 613752 673078 796596 905850 927011 469852 192346 879239 212895 649173 238880 552942 41500 51013 528268 505966 291004 992063 615054 209412 392659 49563 901118 144896 322248 147914 386471 106005 691120 639537 12713 463054 887855 613393 448365 53968 488958 259481 606159 428209 273107 805225 363446 680609 815186 873892 249229 624353 919558 285587 829020 533375 193878 142832 822341 433895 235867 190055 978606 506498 759699 199779 250768 580120 906345 188647 147387 557393 949820 321397 975858 918952 417809 836613 218144 85285 895179 720829 943342 750889 781144 495615 335668 624963 968659 843971 326401 440082 554021 108324 757445 800038 732622 556313 708624 863375 454888 282749 951757 375561 327495 446699 188341 710429 36488 662762 26497 513308 334521 184706 947929 906604 626135 43142