1000 963778 917277 540361 100415 753549387 521104 167957 80054 28189 294016651 377309 337889 98322 6443 265989900 93973 64415 272564 229111 592838723 381931 38758 105917 105414 657772508 297362 143592 133459 108717 692586345 873962 462282 177454 86497 802030302 605115 381784 975578 198450 458501821 207562 153556 108426 61059 758320346 604166 379057 184110 127319 887633056 669675 403020 501913 422343 854480070 468995 172000 649498 308082 504529650 433753 47951 439040 418139 361156648 166529 93534 907353 485894 657185089 94451 35958 732940 12603 67416678 243085 222435 321857 153150 248071296 51420 18903 958759 518812 480709410 535432 203818 65561 48463 24170937 747160 105792 366134 201675 206948231 144487 49079 654333 270710 740788720 846395 508740 349705 83256 940383715 998773 171563 415892 23845 261851244 744671 470714 636760 439117 322942247 646301 214258 382298 63424 313934674 544887 43303 812350 177046 150875211 885724 650164 23042 14799 462396681 198218 89261 530885 357511 856351422 858307 210417 150035 124654 296804826 575950 295888 212937 194808 240034650 371089 277620 214334 37945 846667660 606108 50947 35114 13509 282358833 429184 94813 448904 195 112740031 299135 100931 496719 51859 217597810 712620 377174 165377 124372 925099634 960463 352721 148337 121182 753487749 963306 921949 947289 503837 850958374 612602 170372 314887 79666 525044064 239926 162751 673302 5532 996436329 491552 265221 158550 124924 618054801 780141 735613 55414 53239 384887204 743613 16276 388949 203575 389018071 108278 87802 569015 190883 544586499 33421 24441 760040 86416 9785909 851996 794241 860201 536237 395923381 200281 141596 853128 643683 633955428 524508 429994 78421 46480 864371866 123207 15508 799251 171347 783585334 278338 6877 42681 11579 493336625 651511 148509 132411 130401 721526868 586586 566798 301161 219039 405539488 145460 18098 470619 356059 785747643 451085 448635 786339 478839 282776548 640337 46377 551876 100093 201198463 867155 744877 812161 740459 135050037 273093 28397 521668 499385 289037907 319771 200189 238872 75083 431589805 82934 10113 540785 144340 766321526 500817 394994 233729 194487 625827638 984435 727851 701881 409829 958408162 611202 209504 317379 208101 648814693 350899 264272 488540 481307 635595917 752423 154739 303597 253294 205111985 366842 8636 782448 277100 480062269 743555 447799 704576 613411 432489090 621883 137692 698826 193372 642459602 594566 307110 886385 1197 603497858 309278 110025 702695 44096 6875166 267122 11304 176371 75414 808084596 429995 403804 3205 1858 660590375 911360 907677 676987 315772 206464247 277803 276789 714778 59834 757347696 903638 103089 129664 96138 562155836 148133 32894 563759 199356 466821325 360210 13078 608372 303366 121396089 204485 190304 740369 505774 305365598 103757 96941 869882 334992 622383172 145005 27634 847648 595746 917263614 327834 230182 715553 185951 756882401 780546 751052 303110 167969 352274261 216583 91697 154674 14037 527937705 847919 516523 287508 222518 192163606 789250 350630 102444 1405 417649276 328230 209840 683715 471436 788882743 508151 434002 239483 191039 815085748 9116 8434 497196 227846 589922890 66370 41086 830240 50830 742262369 27850 13965 513110 463603 564260764 291462 177332 607314 155080 249243958 358598 302201 206084 89 970966969 88312 13718 379689 5838 461379882 1381 443 477893 193769 322805678 122177 19243 94418 3865 942277440 603796 361801 62605 40363 474065728 468031 335764 115219 63967 549956549 379452 221930 807234 701582 942411048 936920 533544 455982 246980 441437394 615213 163808 118501 11311 628835581 681402 407010 963908 6830 40005827 598575 253541 718751 713663 192536425 877380 685911 719148 623218 327203706 879553 800992 500759 211640 754671737 710404 521117 586540 442566 216438239 363445 188607 931836 866204 459237678 148160 7354 893060 270732 987985179 596363 200857 234353 214997 293614765 403368 397955 507240 377506 983189863 484569 186562 408644 231758 510388258 187344 38982 270587 163755 338828125 656446 651285 348667 21753 839057269 213772 184066 116443 65175 619615895 850724 620083 780486 764213 335437702 399482 353030 789283 757139 918226565 338330 260645 62069 24932 865649246 190332 180387 701018 512061 73476313 197391 166201 885178 553100 138414600 893188 293348 394085 346264 789739115 474572 179066 568731 415963 212480037 129581 57637 809266 156923 998043144 534963 492984 91868 1965 332410094 290509 25983 179274 132430 204209347 881773 137055 751121 555278 958542705 757143 480786 548761 304406 986952366 687976 441106 943372 765801 605464626 38966 35786 523980 287635 501886240 232020 62419 71286 29689 897216171 752463 569605 345001 292120 977700802 353089 228567 186991 60152 509918638 805435 623752 573732 181271 300810125 601551 500833 457557 304868 182655661 302477 174647 710756 534385 326423316 827960 451612 734074 548293 355320152 566517 389169 386917 342684 433646400 585884 498195 469143 95800 258204487 670202 300646 806992 319612 164917859 73624 49811 155242 151586 224184440 670373 482045 128697 13584 295484139 790485 208300 959989 589771 862253583 244362 207379 313056 303241 243075380 894314 757037 905102 268289 639969848 51893 16692 896129 532536 161163213 495353 181002 343379 136275 649558168 622992 399347 163567 155617 89699799 808830 36413 490287 96542 662289864 782253 348402 281805 86106 898451206 824540 488762 374717 99026 254099121 412405 161377 588253 49661 268524361 112402 89868 521762 350176 405365251 91261 61085 244179 156274 754120334 609049 35354 658791 321395 171503012 573713 537010 659956 50931 214623389 367492 346108 438557 407322 810759650 108986 52794 765039 708750 589501858 717742 197770 437937 195254 316019228 751687 47330 93262 79926 194039315 975192 148204 587395 74333 428808227 95939 85677 762733 197412 680989603 702017 614578 599562 184947 774929503 489303 283764 969385 635868 507657676 655512 592471 637803 636233 330933944 769341 103601 366309 112293 210467046 497941 230415 832840 711504 729602715 833664 421608 43108 344 791987545 919746 435835 593724 593100 15611443 480165 37692 286097 36122 113907126 605782 336789 176755 71094 43637191 408726 162082 742276 670092 90551836 30092 3461 24829 6303 656893322 368362 266407 943932 131567 699822777 273259 33353 853166 822961 206388909 202388 31477 816512 12366 277972151 467356 282740 47098 1256 16554822 190884 23638 947521 637283 520559992 685311 314081 949936 361194 170364916 237650 173914 908655 234087 768046291 139678 66999 349127 304600 746459064 14835 7534 49991 9113 346758484 898860 486216 26990 7911 242761923 103498 47892 791117 238773 394219563 778580 616850 386364 145100 353894103 263309 12683 50918 44550 190059785 209576 19937 384229 80257 847705016 94122 50820 653414 640647 923704489 206074 43539 600224 264897 691978017 63365 58702 568239 256871 560267058 381494 235829 44739 7423 660449483 520119 459846 642025 271723 732407060 606080 50270 212536 167820 128643042 471123 314689 531558 518996 836581332 101496 59782 415189 182288 740177554 606417 143322 78690 13205 142451075 565583 461914 287570 228790 724528921 906829 687805 114551 30963 985141887 935115 240065 438970 227690 353886785 127031 96884 969169 448659 43690046 16157 7329 446072 267038 907126371 784823 250159 347920 172288 678546195 720753 399998 812843 378191 979888201 3321 539 919680 300890 758946305 139979 70437 495161 448630 525831568 656307 61081 132061 94833 750600549 728061 445774 670191 404814 784903183 538076 418082 116039 95779 306768408 270670 183533 444348 355012 618638630 618318 171901 831741 216239 315335836 437497 416084 604827 451712 399560843 330096 150189 896593 812856 186600443 187069 1660 16413 12901 475904930 780073 304930 960799 301948 674661530 312945 82821 301369 108460 494288792 321664 6726 32996 8735 762721180 26949 3559 289797 282530 825773971 536238 496801 810268 114898 917245304 411132 250651 328101 228896 400565350 759387 48025 991727 807051 901322826 333045 112861 34907 5232 257228987 602353 387278 958602 469251 275281659 75216 44997 412770 307696 488562337 578021 37865 676718 203821 830491749 505693 273478 934910 22623 691696338 935233 454268 636793 252649 926274955 551347 260768 983999 784392 74456362 454967 424154 931404 514784 667078581 510211 441371 115047 84692 881507135 244934 108151 696450 48529 600226141 678640 231708 244990 85432 45577235 657645 358645 369993 21956 43889056 193368 133216 863891 172193 350827581 806628 750584 263384 51151 874147737 1730 1345 901339 86013 225652934 316913 243147 735598 583890 385932034 104956 19123 148575 17093 354401430 378541 135712 132410 102831 254767407 573656 521430 811916 264393 186274439 323228 174540 394916 385053 254673107 374578 210372 33779 11689 29357421 25113 5604 195860 72533 465412987 555686 509693 407881 190962 873600129 808281 342944 890662 310226 975501017 119009 48388 883476 730134 893623202 572788 460117 912592 867031 102135398 625125 595542 558090 300693 129898240 847922 172877 972595 14685 645606248 512655 186521 592079 490650 949384270 990122 411831 894748 189359 79761247 500267 259796 55069 14064 930485566 991464 84753 237916 8676 981420889 767817 177318 112455 90186 244177577 142354 108950 747699 655047 848476319 179415 26072 530254 36780 134823742 752344 746611 606753 188053 363929034 710112 474845 707855 686918 67878568 8312 2910 808931 331786 540915813 636371 503548 917598 362473 375485989 687096 120735 115060 49271 77603266 539775 436587 759927 409118 295239567 664420 168644 341816 249331 956497462 92079 28418 206828 151629 526979871 602456 47371 750527 711196 301113595 793931 10825 100719 32692 655747614 273345 33270 771106 178724 978127746 828498 330120 112425 78713 907514848 348284 287711 180054 41910 64544240 498561 198099 830296 415265 909662521 210716 177034 7386 212 686852415 792659 292243 251463 6703 245054555 217413 161902 591135 454193 808054381 589829 465618 898785 754100 410650731 632294 309516 495953 480529 808719321 92870 90467 329929 147125 947411857 928134 484976 630771 531465 941636410 994333 560454 896097 316634 547341617 154089 57434 724096 114966 404196079 7743 282 929775 32785 726418992 778673 703142 718124 109752 854764593 497925 217247 47876 4191 46249999 10923 4491 390632 75355 786126274 518012 18366 636728 627876 350848766 64378 15725 986757 141147 779558550 498427 69414 911104 556795 52395103 189886 165438 922184 618559 828392389 298035 200026 507178 277260 325842233 103231 79686 842387 742044 90831042 745243 206873 118528 112800 698998605 971265 281699 385461 74225 934998533 423327 331195 165982 123553 998945500 90802 2142 749098 31653 532423685 490841 231207 143822 16116 205184291 993648 592768 77517 6735 423593213 912290 41996 369253 175844 830038370 668488 664318 137121 83248 648225115 956972 778248 756358 656264 298826311 986707 942660 533746 245807 630608751 848380 387181 610874 54930 714556071 799072 785706 558037 279646 534085853 396618 348676 504005 103842 285394232 82863 23515 929048 241491 901960340 93097 42343 169983 6395 491386482 855978 812906 493476 117507 674310664 845098 795086 211542 124953 836404884 686661 570680 727672 608686 629085261 140426 52103 68533 44438 661534678 578529 131238 547580 207181 204048089 870727 192871 620558 55819 66016354 364479 177832 65474 27714 407118691 56431 33833 379394 178243 427775298 218070 23194 317810 90635 880752478 661050 193060 389877 68893 784321928 232627 35582 762091 195729 569303543 416715 260788 669190 427594 141725968 286216 201944 486157 236794 442985030 885869 46417 685831 553398 349624926 513370 508763 748377 409065 364025208 167910 122863 979841 284396 475615072 719047 511891 235109 188073 19026460 716641 185070 121749 18351 309824563 822160 496134 481847 164957 796317761 402347 154498 567509 184638 38457909 955603 298565 69817 34510 238165081 669468 637952 52763 18367 188897670 121286 92924 854462 801941 950008516 555206 530985 276246 197144 664328856 423556 160087 485681 212897 595680789 926930 862787 180570 113232 164769528 176263 32527 770030 72219 215303777 545499 131461 420743 294812 702208359 27276 5824 203489 120683 952935095 300059 252483 526537 62522 344704546 418570 32196 417470 163536 464082915 875040 273676 422427 405612 860262126 818718 713347 519346 287983 129465098 743968 277619 764732 347607 316429255 70279 54865 649677 99494 828965990 766318 386835 224559 116932 981630488 210211 125256 627808 535042 77246226 809678 743481 273577 256522 614219068 577497 445685 341170 21670 745534399 27392 7716 920986 240677 474904314 759969 35057 374204 169506 594645927 25145 21766 60768 1308 388943441 228426 197269 934650 746446 701861673 57429 23598 61610 30597 330140760 431627 199021 598618 56188 190276332 142643 140912 147518 140310 794355631 664197 287681 248788 146004 87142135 626129 585140 598131 39664 521757004 430964 144586 960083 38148 5453776 34059 23040 62776 45315 414829068 429664 122029 566287 124994 677621307 383446 176006 535586 286823 952018981 973162 386983 816437 536146 790881863 443127 206634 754201 205781 910600674 613466 335778 130331 98985 439663490 700234 324357 139772 55305 557104345 70879 20534 309552 301206 384848450 802615 224889 308820 61679 388884763 616576 381769 69978 38337 33534249 670899 231926 431996 124836 709081897 705773 685314 58058 49757 155365115 574251 364321 241733 94755 965021449 252405 150647 597965 12891 584699015 463817 132667 715262 369048 948667057 331990 62817 14315 9016 735307483 52099 44694 549466 128396 668245888 307354 210682 933536 228935 405321957 261269 122063 526802 134894 165996619 605516 463368 457798 103018 338732650 8870 7714 580757 256135 679433420 102705 38679 239562 125807 377922233 88388 67499 59905 54072 997170125 426567 263453 847400 333978 297488005 631653 455090 273513 207333 260191251 979735 57102 927412 785408 938276437 271426 215114 102526 86839 213359499 146114 56469 150993 64835 347383344 400303 74232 896799 742001 762544151 901615 114130 517853 1391 830956503 810129 35141 830193 137097 126314565 170175 6064 378586 136986 782859757 914877 38983 916820 609864 484885958 782455 287383 442234 157655 378451359 506398 320231 489764 161581 217185971 785740 67172 582147 236771 321920007 264713 138166 734468 351889 996402614 456766 348370 530100 199780 163421221 907606 819256 328628 25496 225906280 618734 203326 549206 169122 22402362 597897 235422 887467 60930 566274151 175813 137050 447138 100793 493312211 359475 246892 86617 57738 506734782 238834 178494 664076 198696 331687190 455947 271336 958139 151443 10821135 446503 87147 965564 751473 255969868 971307 286250 3684 699 805944551 838012 837259 191712 14649 521674152 895087 542791 772099 565862 116802220 960563 887631 511213 224101 342778050 173983 140824 855219 564363 382953949 457420 42039 657166 173507 31010548 79497 5119 597184 10053 919297690 689252 386709 238644 155246 804539364 635974 628018 314885 20285 169338296 464558 316239 282788 59266 616641732 964308 712024 674853 20450 259442182 333909 45072 515807 240180 581243366 911522 177556 630376 176468 862701260 962851 543500 658415 115967 35039157 486261 253756 828435 418062 832230216 923221 87469 480205 424881 800337366 103136 20483 127819 49487 957280097 898983 742627 733434 53162 348506188 253320 15821 143453 125697 88011625 787794 428991 991217 415755 80734348 805351 87635 135376 73645 910485417 397572 257709 948449 138637 897545981 262500 210979 200100 97960 690633129 926861 272589 105319 54299 536874775 716040 623751 833535 169768 523311340 493696 160692 530241 436943 795747432 181419 126681 601793 370403 225490805 381718 70796 575217 290197 591947080 845767 155570 846840 764248 271229261 728066 422613 949314 244314 653931740 228398 19167 486046 264006 657638542 889130 844608 543081 317641 383231911 529690 215931 889230 687977 136615466 137398 25324 621097 564727 43774313 960956 535383 204319 61341 747879269 305800 40661 200864 180763 446935431 355679 259598 270560 198757 130133959 496438 266542 860339 797995 716448960 231929 31265 797981 83525 419223310 500698 261639 603570 151054 502010305 485023 318658 892693 288905 999768962 574826 42058 221631 2453 845526421 543742 230217 551315 276961 56705627 441300 61662 45588 419 703249594 298313 200096 418450 381240 971063633 102550 22060 53685 48441 566989426 817972 60252 841381 30430 97023546 719898 594171 472553 134483 412992099 930415 478805 412854 20242 122398758 719535 344610 794996 669384 480297775 868889 646776 401501 208017 195941028 918820 208152 232455 26549 941531170 672971 572440 429381 135989 834465147 48619 13961 202996 187537 752826789 689646 26782 158150 97328 536640230 343043 4606 391738 241155 649674671 313587 51023 929548 836114 129327305 177707 88128 974957 908513 737678023 684476 10725 542034 223659 21715130 531160 28617 232254 162282 14283766 763528 9048 851069 360538 348212727 872446 368911 41922 29032 665731391 175468 101255 425687 51788 969255828 408366 204104 427360 139745 958455720 273720 29702 923869 166087 539889314 502793 3474 863489 277380 708031061 730656 18301 703603 82863 579408979 777141 372001 557262 100996 460720229 770264 158885 671774 252054 578169246 56077 47119 917949 406928 366495477 660518 526991 350958 63395 681121331 241630 171033 812430 532947 488225640 247506 196937 648024 80418 784538110 261326 46238 102160 33089 970627014 522893 149774 915408 580838 354778096 168867 91785 53409 21016 686226069 796945 686045 66971 36655 951086729 292962 83924 696060 306670 842683632 13421 4714 502192 341816 905541722 655430 404968 256220 66046 460737731 945455 737161 195711 74275 789313988 350283 294658 560135 500600 163445590 23818 19179 537953 418090 444049026 464928 448489 765677 470554 796000975 532373 303841 375122 50762 15398643 474348 170140 846574 386275 842617754 285996 245739 415319 229176 651201797 589899 479022 233350 217764 740454450 54939 45653 263569 245427 453598625 908502 626545 814290 101156 573475601 406386 331159 705692 301139 410695822 460351 448206 669570 196813 306574880 763392 544404 380509 203065 963461580 712947 263723 646426 380153 33230273 148910 114329 410750 142695 147821324 940316 509197 741323 63613 381808766 113941 85562 403543 269667 764401598 705138 430937 725445 708423 786522128 670884 278248 509376 269038 462939802 275477 35572 535152 435562 286333776 756834 320805 9924 6367 727613587 435396 394339 298655 152119 250603319 279472 207186 978059 893657 206055955 926090 652706 566648 442079 418188379 787939 625684 744855 8345 418496097 886887 265348 389655 234062 850372877 204798 128262 330415 19963 701532837 223711 60848 301278 203183 29477886 857253 198109 622427 364772 646428495 998326 281019 230880 62295 676742361 196429 33562 17097 174 464652509 358227 183221 487956 224476 346307821 801731 213410 455393 369393 241337600 728617 706843 926518 564537 58414745 343025 270257 692146 410005 143823 68414 56073 745280 568345 98745375 3855 3598 225952 124580 616398544 461335 258400 164077 160093 590151696 995114 275852 37784 22397 934996171 263562 130699 617685 442222 168050678 977285 73933 452435 178199 934859439 655602 219768 752295 688518 53603789 395151 36086 884062 546412 533797414 674410 624886 111564 46924 406534140 298501 265752 143641 76404 752005337 509565 508815 357172 316170 508992556 939200 253626 667610 468135 925046079 200868 84729 556394 125179 14525649 162302 148527 846843 264196 581585181 606634 6587 42622 30149 868327057 880112 344220 364553 340888 760189579 923288 385341 624314 20099 398117141 883752 373984 265588 170069 218847980 397007 274437 606968 25096 476194997 649049 445449 481463 177400 450511132 542741 356449 72102 52917 251933647 488122 256571 416811 88810 297201466 316470 150905 951521 290397 538932500 544188 179203 623926 194397 128367831 801906 798789 355848 22971 127032069 439137 262370 10382 3580 398906733 912140 480241 591568 232188 952263425 50865 8999 959077 481563 347412224 641979 521061 310303 7181 461151487 682478 600515 313517 98903 946871362 722439 694924 755018 96266 830064086 384631 27688 599679 289162 590508101 728998 201375 679643 218752 286433063 93949 34161 130700 43248 542314954 831728 640222 998065 626568 752304480 80647 18078 355651 138766 844580323 513762 506994 230319 200551 77879730 381710 144391 722212 144597 584116384 612531 293345 903725 553408 450119780 291380 213438 94960 65984 162965131 561354 7419 957519 142899 280975420 160042 3426 861961 24944 876619529 288677 116458 638669 368408 887954566 711460 401356 132632 70105 887552683 155045 83042 431276 153877 628379345 678285 315010 910642 871884 16124215 223556 219213 498777 394321 596928196 547564 176138 986163 820875 994331718 335380 283548 612257 351103 929866334 762964 686601 74788 35819 798644296 984387 161671 650612 614642 752581838 418553 333325 489505 164499 937670705 723811 639275 897200 228330 704136387 704589 447828 183025 76335 935169944 743234 785 934183 470697 561892552 490244 225953 244536 212406 471542281 462569 113531 214158 37040 44886899 988081 282463 409634 88572 227509042 945495 272150 360223 49643 642967597 22581 18847 823575 568177 226610201 893762 4341 574073 337559 926089646 664192 279863 892630 286733 897342102 586429 362129 112567 17195 940599344 568884 130662 522733 171719 867174078 366266 21233 937132 539185 240191809 349207 132852 633416 211519 643088098 116123 91420 663613 83118 340775120 73109 989 701732 473281 421155626 689078 541048 527850 1456 281012623 517963 280614 445184 335076 352093374 209295 16386 157406 43238 462040469 573412 506014 964207 241245 483388248 581952 117971 991602 141445 57226889 352839 99538 34383 15989 882612792 491073 232342 207062 39223 459320672 625571 449931 2626 2459 77292362 840893 429475 462073 232264 590256543 970867 501591 851043 415791 492297600 734644 712004 187684 168676 477233936 383997 158932 136685 28056 67573965 164535 101030 909080 772391 786982242 960569 58229 369270 239544 340544524 263550 36309 155882 74212 169149767 661298 551430 730566 318544 88500116 221579 98719 284042 18538 616954963 577774 122983 846657 42223 566126721 844855 49866 497393 86279 696660334 56751 28249 67393 39235 794506838 36454 1419 799057 347679 826231623 640177 179798 992912 58848 427498278 739407 17495 675655 578726 141427284 787779 477927 200731 152309 731357887 103839 21403 418455 174390 236026468 91758 11746 850277 209367 349483769 5993 853 405255 96353 669110703 934363 758907 298014 52957 934190931 679188 399116 602678 452502 515235536 89180 64218 753930 278913 842016238 425613 94469 942222 31499 26598916 848589 684858 964814 173997 457102425 787803 484922 489963 218280 820701776 386149 329224 155658 79790 312787013 86607 80482 903237 709560 800112573 482549 130850 986348 617008 381811197 678121 466094 841957 664038 102068205 88552 16579 783123 673706 250934199 501504 377473 136903 118106 108432139 112152 89402 608439 233801 899404176 577703 425611 195021 158537 355027369 660311 458789 374640 76494 718683850 323422 62153 890236 29265 708744516 831909 300913 181907 97399 152388827 573745 310557 633886 434477 536131978 860613 825529 358277 204338 305574047 483152 123425 308037 274703 206958753 459836 268715 58979 10779 997051952 540664 9369 560708 357484 547567409 420514 300749 20543 5648 140942263 850628 786500 972478 125710 569580525 698097 285234 147947 141759 322600418 311987 169901 765706 306648 823400232 803575 344940 868909 660233 958439820 544839 357553 762710 48801 330077821 508487 146243 346893 7518 634768160 643253 460046 994619 138231 610053326 715680 437124 197387 83968 832698589 712726 306888 194920 2022 994932023 202387 133018 677911 457094 396888223 166810 58008 466049 405423 119367674 650739 394440 862668 660697 817654691 430233 152911 632970 220311 161141401 824510 167749 349642 24160 126874779 217215 89398 464037 345454 608238331 637614 118546 256094 173016 504188671 366533 933 536730 487599 871640231 217305 77482 382712 335685 646131113 872933 344384 283438 221494 116485205 81054 29754 151150 8397 317504995 461506 39098 39343 21274 817031050 424121 44450 791739 181311 384230616 268305 158159 308386 292571 124738197 812569 699289 657085 513330 263143184 551877 15922 832121 519528 816935756 195918 105351 447192 228148 583758643 45146 15342 141707 62450 592306877 174083 106622 102383 69430 235969935 428545 335011 146633 9560 776138021 506261 438243 710314 235150 907306031 962985 57101 289496 96293 171210984 801875 410133 480184 153224 535547935 742402 446267 20029 9179 963843996 740094 333098 202001 14306 920163373 527604 266265 550812 514876 780552953 844717 415151 404745 185014 102249412 74598 48606 824600 685202 842433502 752104 258813 563208 111335 477894243 74726 65384 296156 22399 590080499 209175 139621 152155 20748 77453427 977757 180445 641560 91053 482453965 983394 55552 955522 496856 483213737 913759 837894 165295 62096 878761615 958978 162253 139116 133563 16413303 800614 398606 120291 82696 457376697 102884 15256 379685 1327 965399487 693945 414279 378335 98672 866099010 70604 67263 692368 461317 959684456 870021 307020 882165 58256 348798686 348137 29886 746706 509661 635674820 122702 26905 840608 289286 963805449 516311 466282 72990 16702 234187824 35417 1875 423907 223064 793218469 780608 397479 471481 162748 117782039 415335 401298 326739 204668 222420609 236743 94694 974180 203425 273593119 124776 53757 137082 127064 442387352 852219 263593 727792 336276 336982 51257 39537 516263 228439 569639135 113040 74288 426572 113823 162164949 7962 3867 579205 51616 549652592 246195 64625 779610 458689 347274806 424894 269751 924279 291811 464364074 866669 859267 352221 261866 766268353 967057 86790 12822 805 736261254 766314 594554 175106 7566 395374549 654045 9621 36375 28095 88444262 855643 620744 993588 28560 147175363 521299 176270 238789 336 275281908 73333 41216 155984 80958 768816674 502677 408580 585444 415017 432283328 227414 62252 75288 70056 295986341 759842 200515 733373 678630 602900365 211603 147277 674229 277091 151117351 750217 436021 305947 66694 358568949 861668 30933 195500 179958 588027259 79938 12749 853255 246613 961199407 793180 675608 684244 31769 942003702 831543 445997 452130 286870 136892614 810270 344036 576559 109353 697570045 24113 6574 698665 260900 462951760 51072 34985 64754 24330 349307481 835388 236603 188526 162535 167532139 944090 896899 71284 47729 813133995 119457 95977 133880 126012 317040447 158175 55025 448783 235856 220992831 625492 532968 391585 147444 366166148 60117 21359 315377 260233 905024974 967757 608523 953251 646920 915541355 156630 32322 306666 154808 855823970 610300 564700 303855 277258 168538970 239786 151036 963680 563295 887495173 592778 387952 333368 241122 695154096 184050 31960 173040 33305 620644283 741361 84211 494576 57004 530363864 346571 311671 680306 581528 589095262 966040 814537 70400 57386 716752932 589434 305690 515414 475999 249367239 768777 144977 565383 305153 635241448 172040 88858 527289 196672 507686467 282475 232435 465200 317828 328253 486081 255102 676855 146400 924800581 552007 248778 892366 258036 235081293 870387 415381 510216 194072 196781474 13008 5406 873474 802758 127724856 590543 382155 957711 107637 409945524 998678 994908 25871 11630 706046254 896818 9740 176054 33874 890160586 258748 13425 657156 573557 315342239 962554 192887 351104 271659 457396860 402620 94270 511059 379535 948656656 320547 293259 375954 81976 20860138 687614 28407 3726 2072 655832055 745717 286812 724450 600421 851596615 764208 187087 688281 303808 174829536 657461 362998 466816 78285 966680764 952566 345029 415990 1878 304247951 460883 216433 122882 32469 625361841 297350 138156 86901 78495 511820966 111082 20224 283807 106391 234026338 924835 644526 459038 75464 899051910 534944 86735 413811 149338 37199155 559813 417962 400992 118756 361756334 797121 23236 295364 29052 829199714 92880 73873 539499 94591 306746411 729917 490156 951672 829053 779676882 426162 152890 485723 422996 226100868 10739 1785 185404 40315 867325009 863722 77875 593894 567877 719834712 601655 466568 745344 408000 347588144 656215 296556 177623 102249 513879727 161095 89485 324241 16959 433428826 417121 150866 792395 275535 874313349 716270 69051 962662 805999 860091239 811208 744399 707362 170391 712549836 555063 236480 179030 117824 427549419 554177 220822 720513 45738 665782624 932770 465936 237469 21142 670584693 915942 192978 402471 111422 362913148 981483 948372 588855 266215 715782772 906689 817375 289439 213295 787525919 811230 77565 271166 1449 54528398 149632 9542 254683 236933 462470686 890509 432509 131928 99403 50623038 401361 146504 317577 38840 997347021 257945 185797 679651 392501 402151921 590007 113611 226809 127363 18402824 280465 18049 517843 144884 47204707 901866 5815 304296 8636 485823947 284948 173095 48087 47938 528379391 724681 454653 396673 3504 325012884 424095 244037 894944 351090 927102282 873469 99796 778982 178818 404743075 973811 20214 57943 50756 187192910 154063 135411 163305 1617 583604553 113182 79587 339819 69812 377251396 342777 254329 76463 57350 530281344 266151 51089 118909 40613 552926914 302506 96773 941160 417823 69329898 702368 656146 446843 202999 125394599 910006 16957 254111 230765 49241120 10963 8743 863922 468957 108077753 122107 105508 16573 15865 439642558 878824 607967 715319 489729 575968402 226353 48361 404293 335471 126539556 599840 379927 289650 186969 241172813 875916 579310 340959 104027 428530388 580392 122790 847262 604645 739920831 894998 628211 790936 175430 349900791 263782 145877 79442 62551 328513230 25120 21158 119253 9921 885977707 490641 224624 622129 57927 972200160 876291 324305 814966 404641 356631010 288526 287675 541429 524614 958078964 219931 19226 32673 25694 608479889 561603 54019 4672 1980 569550754 55168 25411 641954 467366 372488881 615201 264826 435306 289775 926394868 782531 386813 534126 380895 468585461 705249 547517 188313 92318 830241079 87946 26397 482507 456158 376744412 151736 89366 629685 508919 932319554 32781 14780 343992 273945 638120249 54742 36324 22924 2639 26895918 693427 478844 343459 108672 951923829 275304 158427 752633 434315 870788629 639642 427203 209522 196109 511355268 479864 364782 773045 304458 99380499 879159 789306 611060 379849 726672170 716475 457335 831348 574506 873116413 231539 195342 923002 220797 685907279 797171 469534 498625 117692 171838284 445015 13050 374753 286510 686866598 987262 509528 338096 335669 953367595 697502 696502 326139 215190 503029738 316122 59320 948925 697396 685885646 846763 367650 657169 155944 282322984 38337 30304 275955 34239 864757234 723962 586089 779516 31688 729651241 836570 626567 144539 65022 476529136 643774 161958 167721 57483 423765021 702696 413929 330458 2853 707190769 936271 572075 550618 48881 282807100 566528 171657 875687 463107 511429614 526729 276661 667335 501372 930557084 235735 8119 653058 541556 646196309 941383 275758 989673 801398 839817449 133694 37864 873059 289511 429502729 681624 202471 808668 156840 826080253 282230 42194 203603 21961 727885152 383096 209321 40009 3846 339152412 76817 2222 849577 211844 937176056 895328 283520 914830 117966 51293834 107785 24627 695980 462674 146539628 910053 278743 14512 5683 104553468 868012 257676 485211 224421 650743361 636133 513929 389247 100985 309331010 678851 614830 592361 430263 45817437 796803 612604 788144 612264 614319651 190848 16532 38948 7095 239066560 371905 134017 836057 539085 57445146 154765 77823 4689 4049 942139957 534378 10171 561089 107286 137813466 774886 82853 75154 51834 134315867 804894 52247 698237 352856 216015040 182938 36942 696894 537942 101760063 544676 339389 427413 166879 152370017 734578 514655 717777 66180 217027963 654675 10516 304714 4198 698942218 203976 64916 213386 38455 336039564 7202 5764 25497 8145 223139177 457991 56175 203755 143259 338602423 646104 431400 566646 227393 464389075 504718 38612 323301 19606 825437916 904522 614125 781915 90583 665437540 349085 330776 639024 230718 435487773 729603 86585 129863 30882 375378821 209161 141105 449504 161148 618272584 798309 15172 381411 239148 559964908 702584 109905 889094 575040 582114257 483750 310442 341502 326643 475299780 910300 554612 756229 36738 155431857 774940 334638 308252 182487 843449458 949358 363250 923075 93958 119038279 441157 340362 841352 205 949168231 964940 571761 120103 113527 429000618 458716 28474 311654 309690 912745885 164906 20141 976382 896086 898475804 55215 54272 863586 440353 453635552 989149 578185 281986 118881 54321677 490957 273133 596074 472930 783894770 569516 521938 982396 112578 232360688 562266 151230 626314 30035 943313112 751071 105567 846635 373399 711409891 719021 45262 807488 534505 419601899 265225 41672 467298 83339 591415169 456004 65595 395398 369739 529781781 373732 56063 876316 535362 272825132 698391 621211 903771 121419 257416145 875886 306962 351030 158820 536562939 442468 291723 898059 98163 210030836 735371 183943 197999 122660 234572293 699937 389064 981947 66079 944366125 106427 79221 252139 247757 446471914 815035 369936 620433 499673 250480749 413373 61229 981319 230821 298157233 839170 561373 779034 625067 66737820 622809 45591 470291 24994 703173222 696671 114989 143528 113166 848337186 372753 245925 885922 204475 432486132 237533 123856 86987 14902 768026409 809677 49760 625308 40763 277732080 458923 165967 54929 38708 93414988 933458 453465 118251 58435 710380407 81185 76631 732652 213036 217899458 664487 155448 205076 203399 25072083 770156 210399 15475 9672 832956012 55918 20407 8548 2851 549931988 391490 196130 51220 16558 259249769 332591 46115 352414 237107 17596457 107638 15291 351798 274241 340890716 187654 177727 805562 346129 540487916 347105 119884 436622 239005 263626359 573758 56993 292656 207116 159311539 172148 7356 691781 681933 192461713 362066 106632 48154 43175 896874831 565765 243265 421291 202926 220976546 525311 207952 882148 268564 266148821 204904 196883 936427 529835 116562493 538038 27546 861249 449158 779449733 549776 231555 854060 505418 175602595 272328 50920 704927 298010 979860402 234898 3308 481592 356854 249360420 827174 60883 65984 52400 640606878 730419 285426 261409 94683 482933728 372916 318280 398184 223872 316346323 290471 287218 873246 755791 7721272 949561 590100 588318 406498 885293420 910627 234172 797288 264900 438330826 975414 90922 161381 124401 793287996 399726 359863 574948 478340 132793499 114564 8958 256074 95575 451159747 601380 533848 455308 78121 344638794 703603 527675 348962 54353 674405966 577525 80514 98609 87035 298333654 944559 907179 523677 7942 60810941 103718 100032 290270 30692 123593306 426826 176557 255372 217781 653581258 662342 84452 412885 228025 429024866 221034 60387 721827 317350 977766537 246660 186203 46151 29948 88528210 835729 27910 509997 417115 503249236 543596 250531 112471 106282 589415244 366032 156977 548132 419187 681814487 897552 266765 188195 182771 253674598 226317 79700 860857 512683 510278085 704443 702287 610169 381995 529883052 487744 110910 650429 409342 61783968 850540 102489 246441 42654 453755519 22854 18921 860579 74794 82347273 175988 18142 351493 280765 213271186 88478 86089 843779 691999 606091012 698799 340613 579818 296663 388225199 537930 305099 114679 93121 665834739 302324 219528 365506 97540 706897692 579095 206949 287089 47270 896630451 829082 393985 421208 337457 799974305 602980 230384 724351 143328 211945669 854162 579278 97638 24315 778191272 927280 814822 889999 398048 834156054 640459 137469 551870 548886 439358200 870394 250111 293544 51909 644993597 604758 94763 909166 309619 417315711 827865 534558 993275 956497 362186798 573617 442782 218277 182105 229241800 320913 162807 552513 109409 155349574 862962 281498 150180 36098 756916077 146138 59266 818492 123514 104421349 887661 290460 296867 137018 233771152 660839 249537 390197 155649 977157948 181918 134351 302073 241078 433534319 784113 735015 735106 342349 459961885 932617 593952 585117 7191 434497595 118673 105373 652575 228249 203933003 744410 587143 626397 413466 769116636 284586 144983 321205 310992 433234081 708758 620619 90646 5688 499183556 382808 305059 577632 307732 420287785 199208 16457 923086 279523 274985217 274602 46066 443097 226597 335930565 615659 241174 983542 106868 365506067 921060 312391 255747 136314 412121049 679210 335892 957536 163001 137100918 713629 130771 367378 194842 279887205 437906 396819 633392 311132 631891362 299918 63936 109038 4246 805540051 801586 251398 439617 12679 342858161 571456 161181 453370 57136 48679173 79762 22868 572017 423681 849876112 463604 191466 530767 196068 791979855 759453 376434 681350 348774 224513737 502728 372096 979498 196776 335161742 29314 12184 504722 202201 978770838 267645 62434 479668 255908 102477187 273390 158450 414531 195736 208025921 684192 280338 92629 65534 960341029 462993 115370 967345 728374 629916778 526850 367634 779306 347605 53898320 216314 103081 853865 426527 837918152 786141 498849 148202 66989 225408324 310530 34787 583636 203141 433724519 326398 159816 27696 24169 351309421 419711 391534 628793 536543 51029992 386496 161556 729593 83810 760984967 958735 858117 288151 233975 838092964