1 76 801974 293937 71903 471 986235 170119 189505 106200 284678 680376 72817 363263 178922 70288 406317 834570 706513 592514 876089 178590 962672 133039 812331 974367 364164 135512 857547 541389 847485 867516 131393 244253 842648 299118 785004 255128 533440 167188 147554 99951 797294 479338 51017 286700 59020 8474 934934 629701 852614 80919 382101 19272 745812 134224 284495 536165 540889 387486 673043 897359 318664 344371 356503 434961 574199 509765 765632 382612 121630 249453 222491 661554 369846 585931 128183 556586 255990 711753 321713 928546 756825 191380 115562 258181 562141 435341 416608 682933 984000 212489 498039 161299 457666 281070 928372 229151 378790 148300 822326 372297 461998 606261 33738 752323 170211 243954 244089 887920 657228 938367 460691 127836 673683 712778 493832 17287 33978 393660 190641 338065 503959 967385 527818 535847 689259 363081 556221 25329 456569 827189 862833 724572 8753 999528 589388 227365 749665 585522 546204 675342 994250 741116 882907 523122 677329 124255 232734 436260 642679 124559 526882 55310 768214 267052 751439 954475 138708 857072 3269 944963 106047 242606 452562 118001 682702 288924 976957 735296 142711 146686 910285 560083 153259 445202 588507 821891 228875 971626 599735 747194 742396 48508 707113 287299 559519 475895 160174 714551 12444 491723 442327 518037 114996 20729 793512 985551 456065 946216 219590 301986 298782 438342 815303 962634 903940 49764 41304 539277 916421 90339 670038 468741 417697 574734 563616 759690 873778 29646 599315 295595 50850 342773 249762 189809 303362 276494 169431 62203 677299 711500 73359 114794 929001 983436 969094 122221 524326 591520 424227 418663 42248 584514 915097 398285 225465 757389 310237 234699 600700 774534 379871 113711 294232 295133 201673 951802 504144 778646 487207 776959 949367 793274 421438 625379 339690 653199 325720 295844 382105 46912 896042 263254 345392 392692 833060 735259 511097 219749 765197 997487 515067 707864 133622 654797 697990 798088 305758 5774 273271 715918 448770 422312 745301 469253 440920 149050 723985 275342 785955 990050 227836 728669 467772 846990 956004 981163 239068 507688 768241 275664 226931 245735 749243 857138 218818 984802 932688 173575 408646 442135 661549 416547 276199 2346 426499 911175 920616 968004 603182 241692 838276 651701 719504 925131 182702 649802 115390 537541 976190 41207 92502 296998 920495 715861 385553 847347 348627 396405 843354 83920 276851 746389 928677 872840 638612 677950 395196 187166 556062 998078 679576 804 741953 154113 877051 4515 667594 810740 920322 131015 145668 960551 81413 309197 403210 722879 240170 777121 113034 523283 108232 711815 87647 865695 878621 361168 787009 133593 650228 594184 341740 568425 190491 483871 90645 866560 151553 259275 232854 735353 434115 56353 322658 648252 425109 335448 632564 152593 901946 246730 998131 388723 310106 124442 205671 826104 930591 154252 724056 655579 793420 600167 326159 820698 665557 277297 244325 55332 734589 579139 391660 823959 256585 619473 891324 798803 211592 455352 784835 279629 404680 401312 301923 990543 363882 990016 320265 432202 640864 703448 390527 961780 985257 437148 33359 368599 600130 971340 855460 878015 371205 469741 718976 331150 204509 322979 531203 910554 94844 210413 220065 112750 498187 286372 329192 957727 357003 932995 606804 437762 790156 132883 763268 92633 555613 444458 879125 149533 727407 320222 318027 361216 851681 886139 970240 222771 608908 420039 416697 347288 162339 592951 415596 890715 935956 170397 233256 879806 470851 570107 598322 444661 286480 644319 736135 18966 920184 498363 795437 400252 663315 932881 516447 415812 433976 696918 182738 99232 162784 225059 936189 741298 889442 592418 421137 452191 283896 748725 51628 836201 456320 975391 48725 77394 892285 999616 381088 878761 912563 808510 473250 709223 931848 539776 406410 141141 739809 206086 265389 329989 782214 776590 311889 326754 16877 850125 328945 374184 721354 987973 329549 391376 726753 271924 344447 237853 519495 332826 51005 651563 46 963886 66009 59239 676893 425133 948313 36912 741781 987383 2900 657549 751776 242870 730791 50918 138594 631791 918735 158843 340267 1594 693431 435235 710759 74862 759048 784389 569167 741423 417032 653377 822395 286991 671991 380484 914717 455398 206734 336233 692367 449646 457688 52284 818932 633635 801095 939837 136094 48529 965419 285089 505939 32523 710965 633944 454292 608422 439530 699643 856344 111509 845626 497215 426404 72686 348681 294442 538875 495346 152671 936884 237215 151387 527424 778838 285627 22658 95797 644867 135937 58368 314786 470705 770408 275701 189892 516327 717258 310926 649741 135354 29562 437209 188908 15765 862176 891251 827633 3486 952568 79511 910347 811154 808600 884911 732904 481322 374028 78627 457422 106620 120673 619649 314638 84892 418576 727788 245915 977329 282337 449821 354614 342359 781289 331794 764141 318507 785641 218658 723853 775585 862634 687365 296377 995726 363865 366605 808484 338807 732176 492901 173808 805225 959692 198098 257335 46786 750188 118204 4649 611116 594692 705261 507818 703353 927864 667546 835347 672459 890930 589695 181187 948588 313131 866428 882208 381503 761620 708968 652182 492004 945684 884459 552628 810383 93238 109472 135541 588728 117812 458999 369501 814866 906930 18949 131393 327835 453042 760642 863145 314323 892562 323096 926030 67224 569137 822737 803435 782905 125013 129986 827779 491758 884797 265064 287231 801358 337116 260673 688701 382182 152926 340073 15889 878403 916172 329855 882014 39347 575599 827983 434506 362388 102555 178825 388901 925324 624725 771387 917510 201700 103986 489500 758006 364366 782026 917386 499592 281943 296634 650377 290343 147727 156164 237863 862332 95434 322034 590861 602085 295481 108863 878539 37177 302715 598930 246333 756288 543175 509385 837250 132371 583456 201194 746681 916575 634556 151289 223005 912301 3210 490046 315817 451349 35448 260218 268780 855887 400966 221281 656787 839988 480033 268093 121670 797134 576452 111215 651753 804212 868841 691070 145165 645527 29995 664790 720933 761467 369195 236956 887092 82967 267361 402722 946809 392987 120791 965613 573756 325898 408834 839735 174042 923459 961790 570822 8345 554080 792041 424520 825554 444720 632871 245923 649149 350810 121491 355724 655300 966128 524262 995766 152900 255198 67654 5912 569460 619521 95465 477777 619350 958691 894586 559442 491345 78218 330442 10197 163629 340004 261265 815305 21983 452433 994157 127037 317750 204947 596157 124775 951214 235088 634012 183970 640655 963801 380630 959554 447032 446133 189542 309121 675173 911059 31599 888521 323866 903624 943139 285572 885590 27091 844426 389497 10245 936792 115934 658755 319674 283117 664096 277155 679188 345718 860977 545219 693524 174319 574039 393146 500254 201201 938757 84129 129862 277240 932766 761561 963834 232184 10926 18172 187077 867067 351208 283177 45952 211676 67921 355972 303982 608143 479804 636616 55836 784647 648125 492331 873535 760980 897685 119497 676346 935152 786134 850516 437579 475429 19515 508181 415034 118743 777333 918054 271328 232980 239303 243359 416482 767124 906147 7695 590468 874446 801309 675703 253621 221833 693508 625668 551670 354266 123695 279700 249763 962911 386379 205955 873600 121248 514445 844186 887833 584631 834547 699076 783062 633860 656201 686802 878488 627463 161733 389043 24287 902941 402010 583741 987864 327254 86255 948983 570791 414704 387387 67506 517074 76590 466560 973238 116279 165342 219264 373442 317651 610893 733797 100668 145611 91458 301422 177517 343091 129060 277647 402821 62125 95099 71556 306090 747538 75448 589529 773425 853831 505207 527720 783838 125050 88519 451862 817919 313971 274682 863078 752371 439236 651130 85720 839445 840157 294983 193865 422154 201725 129104 208096 249113 541673 205574 524408 284852 488609 104658 903832 533356 398819 344466 908102 887832 211010 248575 436077 402772 439009 977822 670292 383861 149422 534328 541605 924284 253873 451827 311987 434765 528963 25702 157698 329478 294473 533189 311647 454600 176709 545349 515235 851855 653272 892648 704020 902456 660355 132101 499693 537256 241769 932679 722981 74558 116065 388884 526881 246287 396662 782481 605247 396417 713998 875918 896048 453287 5196 319323 630354 78586 745331 165195 844160 253476 698012 317754 812336 640229 927280 740110 1164 610294 692008 879530 59555 294145 127147 125272 234062 612438 749447 854646 735523 18112 962893 159168 248733 229961 706833 398872 11094 410678 632082 279099 259991 80102 167562 535144 19717 550215 331374 874895 932350 221719 177328 295515 353804 792360 581055 589501 815608 741286 394357 235798 817076 304913 869071 755833 849086 463417 765925 85139 38749 361496 346365 325825 537839 191587 856484 246328 388898 255541 628076 676713 410770 828387 331009 727487 292029 560294 779396 195233 110451 12507 361495 748224 250354 863049 599835 163417 282939 759645 333068 532632 399397 516603 146640 8408 724216 379754 718242 369840 476823 799514 424044 333870 645397 936033 142665 3600 224798 689069 661227 480622 669384 763877 646932 444193 628008 417188 307419 621886 951100 61201 83927 140303 796706 354611 980376 591808 688419 624315 382482 864440 974974 544029 966851 626202 99083 395049 910615 413473 391314 39862 325769 165833 32336 900969 877385 177680 883763 433329 767550 309187 837378 980050 971991 564584 323338 403011 613901 914765 961216 119909 424680 857800 434807 412843 414721 124193 191877 433307 121805 824196 165904 294890 404533 971519 244206 679461 232071 292769 237789 486667 841048 967863 994311 48755 359449 424228 755641 173663 111002 274686 725677 547185 326499 492720 63532 199663 874359 84107 729863 217758 708569 496645 736428 584438 989363 914258 915709 625326 207728 496093 941024 992662 835172 445659 418436 209434 240403 805595 902579 214396 194122 551030 645529 481774 477808 149463 836483 121546 607079 816942 980121 473056 547791 504989 488567 596223 621683 908197 298969 733604 10962 223585 906582 444822 892661 620554 63103 214042 991499 231570 874079 45456 337933 602035 761800 557044 729999 615055 529572 110325 912529 496659 43202 778925 717039 70868 635035 33658 57388 251957 263824 746271 590663 635319 367730 467609 396827 342863 601515 93436 817208 915625 669400 618661 681079 78410 173315 562165 523612 989352 236108 55209 415160 999278 382957 452499 35285 103108 611600 157912 950021 584827 269354 56099 379844 556681 299098 860895 912828 107027 409360 43878 832351 97767 626531 411667 671513 667211 311767 394626 208752 429301 820545 958186 745910 320696 78292 800775 269030 641507 40263 810075 221883 288139 735770 734588 540816 85837 506452 369411 514122 893219 48205 137849 636872 892025 121498 308265 930204 560909 503051 170991 480642 71955 443992 702204 875833 354405 626035 496054 224103 441974 816828 605008 406817 992918 133297 389139 383028 419297 587025 42313 844645 662966 283100 482632 948516 518343 700004 922055 863505 734474 307295 398414 499550 436165 272172 178495 310245 712142 802769 549937 787839 808540 622052 245238 620980 116999 611240 573525 167491 506715 928237 187843 133961 723764 817239 303894 281040 319027 635270 291929 878505 879560 858859 851252 671215 223910 364191 267473 20885 879322 108408 126553 249617 727427 526595 624147 715645 660115 356060 249231 15895 991064 223440 111671 535001 26907 845360 155432 398134 976485 721027 431419 485562 720863 751455 662795 709706 583064 148738 907671 369223 218741 451750 436885 960758 46832 973784 349227 660549 45991 594848 114313 98801 963368 791325 148688 194725 409103 104863 12304 666730 937861 301721 160311 303329 633374 182794 787586 618292 943549 184535 727734 7873 640013 373780 454108 556221 542865 236585 382475 155968 763833 804029 813101 730701 929909 37625 335524 47778 210903 166934 820440 147231 620746 910164 761369 726405 741794 703916 628004 752553 777203 520660 751738 777729 590673 810690 14947 292052 491146 884679 455242 394260 106085 969192 494935 190293 894978 596352 481388 452643 97076 272260 424885 608935 696456 252189 166539 753107 853092 311650 965582 704882 623566 169686 842706 161407 278983 65019 486273 694317 210561 987466 308307 999290 941600 858597 900796 389487 49948 442393 569718 492414 18490 99995 633666 651619 905372 156244 606096 67374 687669 492135 499755 880250 721004 881890 222198 763405 242570 74650 421946 715571 146614 325662 375567 130516 540110 828951 533296 234937 591162 40843 232447 557128 482592 851096 109565 804034 157519 448803 791148 515986 953590 702660 128082 728434 197891 338247 49812 89637 149889 380810 259440 503141 234906 478146 179200 273584 149398 820262 804709 593962 448438 426349 695484 8763 848756 804085 38620 555564 690822 804900 678137 510257 523096 429671 656979 447548 409275 24599 697321 192017 549654 763439 728766 482106 874780 212565 800050 648612 416643 160874 294209 651602 302420 229236 304458 858848 856896 169544 492418 144043 262499 833462 348616 308927 139469 843331 777947 554870 249255 271357 592672 232897 796802 367118 731149 842129 562121 31197 730523 661600 225458 996389 806633 792048 886958 245691 211022 152691 621613 369223 247694 485031 894689 786314 369927 842956 809379 654392 460757 802663 736119 586012 812579 333434 343276 446573 962772 441271 481526 650465 717933 378135 558870 793191 951473 501796 450881 393469 283172 116651 479880 491275 706881 957795 94883 408497 341294 382601 560044 848357 357832 373919 241865 661475 316814 149578 739035 29755 850973 88799 665116 31678 868010 207164 478559 747800 12100 349590 826590 69066 231691 616399 605389 792915 463151 906836 315292 540248 517389 632573 286314 846490 916466 695427 710097 820009 937789 397602 920408 245725 38583 526865 384852 150234 906793 17354 590142 926136 105963 405029 631375 28221 639331 722267 971794 120893 644569 51998 526034 893072 441196 174864 470306 745254 523701 544203 93768 372099 179703 309038 476661 672612 6851 613687 698144 106557 488789 44873 752688 839034 563699 151348 222055 722203 788825 229633 627296 505941 339510 227438 545602 187903 97017 958359 681585 803897 984012 178897 687845 926499 71300 504141 273182 769374 585422 242726 476220 999202 609390 682158 751765 285733 353257 136439 159696 948575 34304 860867 928851 211732 912034 178168 78416 85779 960325 719731 954885 861618 621675 329817 436011 645971 24468 443214 337918 531775 358243 591415 317175 658888 448035 209377 587488 124946 526888 135295 880676 397034 836015 281863 377821 195173 11131 687275 828442 537124 882621 720459 582977 684591 272281 403365 446555 82792 803697 778196 15875 348454 189491 981920 699551 283061 402697 5270 348137 128265 626063 28763 536650 123286 416198 358960 871085 151857 656606 225437 941978 354451 545232 838410 52287 850935 426431 600390 38904 554126 223172 432324 252248 418070 806086 96808 483979 187819 785015 617867 244029 38670 521217 188146 404063 696972 114379 888109 909203 851539 343781 342725 905881 805796 74948 32637 702595 127487 198042 80530 378543 451721 452027 866872 600106 362595 142193 133170 248171 141666 462735 261676 540701 481897 499006 160327 570462 835199 642649 392005 66661 829417 391311 912154 276458 126409 741351 229298 954828 971607 587880 941327 310365 635011 489686 854951 90629 625670 607705 19182 945401 793228 998595 839157 116588 977044 496009 224140 685487 153372 724238 999087 494585 722760 816319 991842 431699 328788 418577 484153 215718 659529 600325 464631 737614 613028 713763 572715 293103 94001 700195 997190 72258 861544 670134 214197 905683 695601 750598 488325 595119 656998 990061 378896 873717 926290 740927 40603 595475 584146 734523 942929 688649 643603 890715 101257 10125 89909 936886 831577 588017 764106 766930 444322 684584 958667 477567 213138 51956 79131 154898 896998 767174 33330 656965 2456 608621 263506 756982 15418 761550 465257 724098 225139 459223 387292 780548 428781 293834 212882 881339 457492 106842 600313 174419 416359 484713 470231 437389 178723 203569 672028 914740 745676 274725 622234 630513 549562 560558 975366 706079 686301 911608 45940 927729 125392 237608 257870 99578 984187 502942 296245 185567 209725 465235 63888 759974 947268 225329 875197 189497 886144 824536 53155 245131 178311 650930 619549 19980 191950 111029 276172 534941 899737 598085 700773 209375 134185 608422 117885 348963 693153 422317 582825 365581 167696 771252 505041 159047 756890 78697 164875 483399 280091 967660 941893 870134 846839 616770 589252 820093 599536 54650 338836 12514 779188 486673 431855 115040 711592 63930 876526 454389 145360 692462 784174 983542 645211 124641 202092 421376 628305 736300 170431 832085 301786 446653 445624 814032 718337 238359 92933 407837 486252 24789 941530 528609 739183 736471 694496 978799 130031 75543 650597 296699 133372 754104 833223 780012 148424 595027 425361 910655 61200 516016 477787 655181 502879 801564 114775 92465 609613 859766 276958 322410 699165 181073 571967 284022 149512 235715 387270 478986 277865 874384 287977 71358 589580 148158 273070 275481 827909 403124 295025 521544 321627 465214 33337 448766 395959 642628 53846 926323 434884 749563 465790 623942 301945 606123 285581 11687 948098 737322 965034 558684 380458 158513 265124 361819 4270 925720 360578 283128 525025 248844 601811 188393 45585 526100 664428 119574 332446 975925 857812 418937 971409 573653 959388 486923 462389 399436 123441 775637 832909 658386 760121 433187 3802 380703 313687 998809 640743 350304 423813 899585 995759 348721 2150 792158 904054 802707 551835 933728 235060 690545 850959 736774 902315 333877 895272 614300 943909 501150 886722 603057 689271 757873 905846 950089 498302 765343 728723 866862 215528 323005 581478 132803 69048 403939 137471 853601 702753 51783 517645 256059 177775 392224 837784 477304 992764 307029 262636 577243 535898 966492 232586 137938 259701 148393 725999 131889 935285 627113 75494 454818 874684 429128 703558 172332 330596 675259 484418 802264 119250 613520 87813 180113 658933 246131 285124 381989 521561 233453 104562 763407 773707 714208 143052 851690 706136 342800 112376 157686 861957 457432 667817 649967 395232 465122 214217 261557 109866 868436 835302 113153 314353 944154 670314 26497 200056 497170 204718 218685 115901 963928 618316 252576 352272 749267 312175 665547 50748 975787 692641 903272 803672 571393 656386 161154 997251 379066 690612 46752 217753 488684 400006 31345 441003 907052 413658 505968 428304 432222 576037 674506 24818 994902 658323 448529 724338 616901 703791 212436 893956 643143 486701 230859 692440 319454 605468 277904 550053 25342 506959 367287 689292 238617 490360 277449 278358 185788 243831 628171 91808 197119 320190 113127 117675 375613 810885 288610 669468 995196 904796 593067 30334 274101 827058 31951 70773 556757 734620 325762 523947 124555 39631 460379 634470 549714 735254 545588 968644 99399 636832 339534 839783 692564 525673 667921 341946 955714 454289 468786 876665 860174 205093 929310 141770 512066 719271 968220 848423 24967 785313 998999 119620 713939 941425 422424 760083 883807 3319 963519 676832 179572 351942 492947 136605 364780 136647 465443 825042 97952 220997 348708 314014 12556 827018 321180 954181 774338 51442 610736 523114 976593 877358 463657 654095 892354 154495 195467 135810 207249 425118 433827 447381 546503 645594 515535 552712 904634 117545 693264 964959 765838 826129 585461 957117 225932 304604 162649 38915 386534 472813 363372 679367 430321 664382 353471 637601 978832 214035 867905 848059 680822 49175 534894 95395 345149 777970 909538 370181 67821 474753 955328 56119 328464 954488 958696 897890 732392 414332 349351 229414 920796 966499 747292 108539 33081 127931 925375 383725 430773 938654 863729 728913 115918 132598 292372 836055 63216 442104 594793 825957 525093 771663 54998 101445 422094 611648 875090 656874 133816 309826 440319 477079 291049 350234 502671 483386 642350 285293 24944 764781 609185 756091 960054 697412 873625 799819 133627 931456 77337 916983 2690 464129 330168 330348 650981 837703 686162 589623 754032 808825 628283 42450 953037 787167 433346 589377 959844 393585 645922 980485 998325 142991 930681 378156 934129 162618 667679 879790 970021 468873 540960 221046 262469 222898 113242 66779 620933 769029 717276 230413 506305 841192 805352 947133 712910 524796 958323 781186 263900 600701