1 56 719187 254772 75475 519832 379903 601610 741929 613897 127057 932624 125380 304597 39194 539878 704273 21521 557318 95080 556438 764277 206481 716591 333216 846223 2060 35925 11725 922729 239433 742226 258856 422587 715529 996359 933398 316020 15853 569936 352660 875660 990689 828303 967984 764178 574218 568554 912235 4982 493899 272590 684934 907591 998472 982883 41643 64269 39823 695134 251022 763117 704014 442985 866915 587896 326670 575960 597016 769630 262903 818549 133630 977414 215473 402189 573040 9727 804402 952096 184898 108347 115913 668532 562639 825586 963004 540946 347891 610885 585326 54233 460343 934796 267077 562009 108660 788908 463209 256544 131471 902615 244986 412674 562283 994595 469518 536584 372938 559069 207357 807101 38109 212984 346286 739165 268151 653045 851883 357826 462610 64803 802495 439360 827792 182343 94374 896197 121645 836771 357960 35479 404551 787115 945449 793286 202234 856359 128322 280515 647034 764301 737207 752339 897557 167984 730576 576127 477322 603643 327600 208849 854042 485231 178281 167512 91987 173948 448046 265371 761896 69337 824046 117793 943675 348007 82531 813150 967270 810030 500737 913716 624626 761670 220457 761050 235343 79434 596131 176956 777398 624681 429437 833381 15257 913356 395700 12870 841372 774624 109511 49707 349107 382089 612623 424391 893001 667318 369708 18965 991592 383265 812532 24757 362944 871652 272393 512686 349339 872751 939602 415858 446682 95502 953727 738725 551100 556370 581843 817652 783554 695576 761828 898415 844749 992465 105719 693713 984529 375798 455942 747805 797429 505236 449192 736581 433624 693697 806742 317070 104456 231190 95390 611959 223533 254182 99952 920599 810330 2545 413854 437100 419300 807621 129296 806871 627138 579756 71628 415759 711616 60727 998620 590155 45000 191610 668150 538817 872536 759396 685673 586247 579840 471345 274 569330 588895 192416 740618 649465 562150 210662 734481 657550 781977 392571 353035 601713 878187 387271 760309 535629 22270 999747 29313 269356 512818 241703 340413 993549 245422 53952 298655 816618 314562 352488 711767 255261 797478 928181 93766 775861 763275 126226 93809 248912 82697 33282 912759 920313 14882 924655 754319 808639 121830 295326 198589 666830 600449 217406 888706 914895 31021 872682 214623 171418 368145 836331 198455 101022 696855 195266 487509 874015 758789 259384 240906 857439 755401 491035 204352 34555 766367 8629 684147 512619 974282 927275 222919 441082 210781 55358 285655 602503 222084 46750 956293 636810 304912 418302 181746 229474 654692 628525 931855 704564 337873 982054 770278 664680 54651 541702 711928 591039 540204 102756 698984 11618 794873 20375 355865 60744 773083 965646 746073 948967 370310 60148 112661 426245 857968 655429 582974 789477 761974 882108 458971 402211 315043 434045 989440 185183 355111 516817 924974 426909 387435 812339 989661 346115 878390 895309 82401 542105 139391 910604 242255 822408 337296 52480 234512 820386 454832 349192 235434 543143 658971 686401 31349 743410 162565 746416 242046 660223 227810 451556 48987 194638 154167 757138 656579 38307 174885 672499 603104 200453 171579 343254 518122 62046 449008 918821 992857 87921 700999 25709 139916 554401 136803 345189 673956 165472 444302 145537 555899 996724 947129 812759 124819 900764 894049 846355 531569 560243 136000 262282 798837 174417 481321 565378 429192 366341 101378 829935 642415 761273 596655 281488 31460 871569 710563 955807 423884 787489 296504 49608 389984 30114 377200 168826 589727 227891 821625 546087 729301 247570 783596 669474 498120 996334 30804 165608 243953 766964 471668 819121 258886 24927 4641 998805 509712 4508 693354 3065 254444 709929 340600 156454 328219 166097 756191 53948 455633 288598 870130 93664 356589 918814 505974 120649 109616 205722 483327 102999 138737 933336 143086 235864 110763 150874 216104 157363 228957 893115 838151 685448 459423 912137 861901 198153 122128 685308 514214 734660 103634 812059 811721 667759 620458 851359 39114 254101 454493 272250 431473 975187 552057 109051 995264 112638 377444 638908 180579 461045 292352 666418 474860 260628 739432 112759 764431 955748 944362 973481 223434 742919 599774 689294 89439 601542 978415 596161 816474 152894 511415 32143 318599 173898 669739 616461 531146 404015 686902 441890 838150 684993 92409 799574 908088 883650 438695 535784 864420 18068 511839 617713 541902 714221 795691 262516 772637 922953 34456 127863 62705 217178 729632 368178 492870 805761 183261 91961 749949 42133 524048 232675 162904 988750 69369 787695 709363 636457 356778 172588 685222 499180 249826 63875 644904 440809 571622 434482 143711 881780 989130 22956 396210 74684 582050 691489 162904 837537 295588 783513 699103 574067 697721 481458 197217 91945 910186 300183 72641 606679 840686 274416 182933 920508 340006 902255 420943 741668 366183 30653 538413 46059 984272 35388 243568 609255 445004 158799 944668 147766 595283 116536 665426 551880 148395 953708 980649 296684 844174 730126 567210 264808 749993 640519 885581 496746 223028 658652 415334 273354 290875 311571 631333 497670 65303 102394 919477 21529 76742 625802 860155 88188 681063 580239 983329 995292 603546 209363 354147 410885 125011 861139 275383 425966 845754 93599 568194 110117 805277 811075 281561 435189 360982 707127 672673 675412 453374 633400 76545 473663 12916 466030 865243 362328 146365 604352 9900 113735 892112 84543 779523 285147 916243 733833 496615 832020 597072 703156 263406 284356 978525 861365 488518 896595 442828 52645 821657 450717 952352 323644 428524 656724 400775 330096 287045 895906 248712 813148 717504 524532 996748 30121 307834 261673 658990 501421 30493 370731 584167 590714 335252 820873 530962 950097 845102 142180 696465 734792 967207 101680 961441 260254 670748 260054 406429 635548 976830 189325 225483 516455 686767 707379 799611 29340 847573 534487 999154 629227 447542 351710 765745 319456 96629 709077 274129 735671 591226 857708 582518 756988 644715 301188 575038 599337 442060 205479 115846 848164 665733 293161 553778 684434 168708 251794 745725 409157 126224 629469 535494 68778 797611 919887 774663 803933 997303 907354 85523 502854 703113 443728 67233 435354 719430 955734 36143 199283 171255 849952 806625 498437 548388 953579 719435 330268 793805 990904 891164 778663 760908 259128 871537 233088 344692 551323 781683 501870 276981 50965 420260 753674 96128 67025 273939 239749 51470 437222 974962 438808 362713 563875 141262 21633 646857 194377 832154 781980 363094 255042 811009 5731 647174 45570 47233 395163 187596 546458 363120 57474 744337 471632 370116 199598 676559 469081 891906 6943 597110 967145 496074 834364 541600 549275 609576 930598 720454 835905 636677 427218 505849 705004 492234 948278 556865 663465 600861 362020 964714 207229 50783 775006 513970 438448 40425 105275 394343 659076 384587 819068 509612 763025 40648 722749 968000 37404 175697 218406 398493 768825 602623 133239 670707 701521 314259 223509 702066 465302 947437 452167 263370 892367 423398 954201 14202 855538 906464 322328 344459 936317 236655 457079 978271 962576 479838 783357 111182 271122 998709 350696 172776 253597 416882 835179 6919 509819 913825 983588 621712 62216 890091 746253 706033 152383 970523 656266 932300 613973 210710 411471 92513 874017 903633 515016 834741 646646 955359 771461 286778 794290 387677 440679 3005 821850 351961 952499 25957 941885 348565 556322 267273 361367 731040 79235 55861 557515 753723 28003 794237 260255 919818 452653 734169 294761 369531 433612 535249 381399 43340 900832 264325 939330 526331 204770 383798 484432 397949 868631 112350 425484 226298 851133 858331 495829 780354 566280 882598 447796 596354 49688 401293 878711 431906 524062 276126 884888 309463 268899 412752 946848 909302 155175 421064 683036 169352 951146 21629 957511 373134 252654 271087 579478 131501 547259 146206 277077 159081 497188 944787 238568 546041 850847 529643 52956 386680 323047 916320 863435 729315 701996 393941 839039 629511 585651 573440 549248 613655 755146 771655 460136 164592 687216 85946 178093 718584 538295 207385 460896 968287 673636 629816 174299 441090 830710 646581 692140 256711 87909 896081 580169 147110 26787 391020 445520 265098 35160 828267 221225 303495 590047 703141 972260 48056 713424 329858 96259 450759 995378 294525 93664 86143 348134 147253 439694 469876 243656 307769 28853 612124 571481 374147 104394 839593 177995 69449 366112 799589 204977 930251 676499 863488 696735 13920 155876 910254 821706 755848 529142 735286 879532 349111 991690 640041 546326 695298 3434 849381 872997 446386 959606 884675 141207 310051 576616 948422 448524 955710 602600 896891 261341 15140 555428 391735 22598 359549 380571 686170 692039 531287 687516 368271 507705 221822 730297 85531 407155 418278 876085 100245 996645 574861 224332 292888 432091 650695 839376 435566 441192 761514 898042 568702 83218 979480 163382 299072 216977 281011 162913 141470 363952 767965 444305 363485 173469 162643 599185 497140 277066 221250 193633 773133 163920 484963 763878 273686 135602 122285 269381 214458 3550 836930 978446 16942 146044 779252 41443 110463 575045 472092 570000 331159 351308 999652 545332 503551 890390 649404 871661 867176 637188 956055 401955 792036 399542 93280 346796 939446 204972 959878 275368 876835 341141 676910 981177 794689 853877 177534 202040 478135 806707 428641 753051 269676 585177 784767 208020 596711 619011 147745 471745 705249 667836 383883 91590 983098 70726 371577 327848 732180 408602 293234 452787 613097 719399 753915 322035 332395 962004 420514 158268 988749 216125 370345 94727 609068 770796 139147 394733 260255 655736 879856 576953 880306 267165 869558 284952 246375 45285 751399 396894 11813 577839 906940 815661 424372 209705 538871 761687 433274 542317 570221 557884 149666 383196 464915 227387 547450 18573 852037 421871 556894 353240 143469 828472 155074 235900 384906 24555 34409 417526 601211 944192 72263 450237 781352 565585 108065 10464 299169 79992 59422 79420 508124 757462 602920 259841 600141 994376 778535 680001 380912 905406 216510 788768 78622 449451 638509 942352 380887 229049 326586 534270 93388 117012 754066 192502 727099 393964 802584 850945 91776 654728 848457 708467 134151 834240 578878 64945 5229 588576 164082 152623 560109 827566 427576 249024 777546 863637 622716 468344 287841 128441 505804 664195 743981 351535 149133 842333 392354 676836 216800 61558 424832 202963 237346 571509 762862 677860 237337 125779 783497 804789 44436 414338 126080 753380 568597 105212 679103 494680 604311 959009 738482 596132 734218 644749 714977 190203 741714 412827 454846 445065 855111 702397 161121 349456 748041 158209 138238 66743 878315 592175 656546 816897 139522 14925 927766 402529 980263 76606 305656 118509 538671 619615 701969 604623 358282 461962 646986 950727 559265 350998 714409 639059 454451 492645 900880 608285 857061 721438 745178 575898 716607 23787 290484 697822 833438 509280 662295 345981 697493 720928 461438 266190 346306 405352 699652 695907 256059 137304 344776 703122 547856 934698 283598 564552