990 1
482972514 306459683 6033569 939778091 795751361 755782687 251400173 633091722 694397973 410125189 506886963 730982883 114649190 569434936 869770992 626850242 246285547 990401962 563108089 672040394 681489393 721398526 701075987 787049869 181156575 844741339 651575532 659209185 70027132 57523287 621302643 367162090 922853886 873288643 923701033 50803726 699155219 217010964 173131365 74003044 189057177 106436445 586926813 138886929 915144880 680026107 773275364 270330181 562467244 978535942 91319238 382524947 386996405 193553435 444264458 207545536 55018583 504472258 648508619 219215244 847082748 287493649 122709996 881958304 570764928 499773499 965355404 308176019 534595304 757868139 188881321 526259081 546590617 169617562 563537346 89758865 716739301 494496212 630194613 6414507 516836238 513878913 300555549 140055347 495108005 911448173 603288322 644199058 241913694 305089504 337642849 257417860 147201780 341378518 292549556 674975588 270246936 999762013 673982247 63547484 247258224 353102355 347612758 61195874 399118076 218898511 60732010 430316146 504222789 719056384 623634814 874759945 589047946 278735370 321012120 221397438 581405098 821292381 804191395 792765023 609143754 48208970 99360832 21890169 346580710 367503721 123207795 94400204 585455825 953706076 198272033 734573087 429748407 22661515 340237742 252618888 270921580 745927271 579627243 695104362 657614909 740271744 435566278 153706776 749447793 375549708 115247115 780171646 311527502 986299680 949508021 723442693 649514396 372420149 417066677 286711912 457933802 68888741 971940615 102204431 881084175 66899435 247651984 143534809 184412396 29867697 870890610 731898142 238455900 247045218 496076998 669169331 283757367 844895883 137990481 23983332 859927625 686329616 26926431 875130680 583295148 878502659 447872842 29808791 714515727 146913872 189548321 32901943 749222865 989640131 930078018 452176256 733571758 818828776 825710582 163626757 549636718 766427430 857524255 697950395 787973143 39034119 954495501 728659180 261213927 889251673 368275177 65019443 40729194 690598962 272107465 738678736 403150511 992688457 909067562 685020732 136753810 951842222 534731421 987484565 175874201 617903578 868785274 651492545 348490266 481859426 934306925 805114571 461927255 604660393 799503064 500156272 686134056 232898955 87514668 543400134 165218336 142636248 664227066 529663027 455366319 467283595 254511101 401705213 553157285 712247976 117647043 50652834 550373198 942011465 384949617 802158898 277483544 630849644 257950739 152676522 344883352 599628901 96709025 188262222 169092459 206815047 351185751 343000258 621373201 748745342 108641576 228699444 194897833 868865015 357949647 513536381 339770284 940982466 894922071 743854866 774771589 313624761 924521499 983251736 475108190 988159504 954079725 161315871 660272204 566754101 263029098 325542576 603325575 323355246 689734551 301483105 604589936 721340959 678830034 315913808 809111559 112648565 684800068 408102175 446763148 98511902 59044988 614756230 691655008 656908515 446644235 525694337 609907700 758053061 980736747 738487878 294028374 61159399 302795675 398312170 975040806 426887899 592482963 528085171 77545048 674718880 456935943 887873112 264063406 792804212 964200166 908457219 62538904 388803264 525814924 337901867 400385683 691849059 905834146 943861943 663994560 330644659 629677137 549783180 201845679 89525165 740078351 648834578 591821531 548352973 420677203 708462725 673016665 736201318 866934057 715650375 69127133 383030171 397933791 57107586 503208995 452002653 292939488 554589134 257113445 888901463 496131818 452748722 205125264 872518742 70383085 988483846 239854626 189432396 901778859 322581003 411111209 817050980 635810930 158546722 235941384 190250625 399876799 401011539 604318144 704974137 980659430 520502877 361866931 661775851 556366953 524470353 736934364 212598855 97437469 459290936 834917741 107928634 491352441 677958552 38800371 35915156 364668492 901696483 656840709 663973042 411628275 500788614 233377058 230810079 128988711 488367594 260473740 195386528 939406412 459131178 380676445 946010239 650649400 57701548 983582035 521225503 88626161 961182134 615306046 648102649 437635419 271500632 833014043 100836666 873011046 891892399 182695319 8863894 576468101 481099442 754291288 63117320 256552590 673111448 933317052 958732993 522087433 397949189 919902249 132878984 253653566 361595751 475871621 905444342 748607947 364730636 928623022 464246744 690444733 60708615 774992333 409885283 48234555 978639552 94432770 148239468 479428883 269872574 288750413 645061441 158472543 582752355 799825349 780716974 347949515 721077231 206085571 755463254 601612544 17334427 33610390 753374955 318040355 805078314 322561065 675865315 280089772 116068563 513154722 962518687 33471459 419318167 362042055 831295960 132688965 301376414 440440058 222631696 498135207 703698645 757510240 111588770 334906624 952213517 758868568 792695132 411556917 800386943 596937768 263103152 876418447 589193849 50586751 558654337 458645158 470951571 292342141 396745524 38559562 686904657 868320859 189907119 858228530 872704842 448638515 309216727 563029331 552501174 178923324 509556252 429869409 863349814 698441936 10042927 217372861 156119521 668200185 526096346 405822617 189764272 191752201 316379793 646736982 160156340 493444208 989802870 262492788 981287124 554415491 170544129 521769325 386747038 540969688 978831558 823282102 793334825 722192876 599873585 933327881 165708470 780898431 507979977 824698793 997127782 369964529 905291760 866205909 912049650 288395944 232642907 15646646 319321696 831954919 541182192 966686171 677786831 47527183 879591265 420397305 359421343 172141033 884095428 668639373 361778818 467217804 925430268 307467819 246591568 347991838 330643985 721033406 100817911 181898878 876718678 548505965 624751722 587396056 426603108 693902715 632896560 293219318 972124044 296494580 799121136 929951223 323653543 986518285 584007148 767232079 645854379 196083424 292385739 730121186 607270714 589245600 881676317 359428563 956574441 692016294 372037889 512904974 622028636 548320992 78134331 310015872 626074457 95971461 854071475 554942079 46503946 383101568 898734434 641089728 323057267 26699503 841430643 493656930 991325290 255626445 274538384 489410474 54795422 798725248 408496990 304704962 311845812 978805630 58687398 443616995 818897824 745696651 742337923 778769512 519351568 145966049 165792902 927844870 134176814 79227181 850595066 41020817 4707150 271286624 416647664 606500701 706280769 299307214 673726394 691194775 837952592 404575991 509063939 519623300 328196444 206840663 940775902 303268524 886840233 222264784 225429552 728091392 846799892 475627325 444012511 306065113 110606573 163435194 78112443 864524310 357454006 556374860 738915529 503304198 827109789 415231378 18602226 285151031 227267667 279650027 356112191 287361837 29428369 269475846 761340624 273652434 405380180 96445068 559622864 156720834 883063258 356048160 749033954 720459862 991732116 713470857 625185126 909685069 856498169 249097108 868712849 500856250 999196027 297240958 88842982 197458523 105987619 202781790 607610518 213333461 530879618 993922064 768215970 797428760 311272606 390510209 348787613 720348240 826716817 844553829 860035631 618691278 936107712 971449514 84553492 790673815 633291570 847475948 854803781 763762301 665117656 682550002 387595970 606627323 325163997 529956757 575096478 528869120 343677992 574117711 812538546 759846593 399648854 353539886 942842212 57381329 351761045 877403680 36572342 298508911 227123445 148145715 507358664 20824198 692631699 528470828 593461119 890775271 321164465 977843599 2629972 603549286 764710832 910511898 319848705 534567516 663593855 702266468 218217232 573931195 621201794 955503399 133189542 211497390 812670884 632946521 354167318 222561405 481404281 249813101 215730270 240335925 567703544 816256635 684257440 859784474 60807301 850769053 289382677 554585862 956862096 82666618 322106196 350449387 485949824 744369895 804324837 262059076 166256192 331215648 430619328 556289777 397090513 529090207 572177664 651555906 91511626 357102156 899572408 54097052 373568243 91147732 7038236 294813084 951385518 671434736 470212179 592299847 125795912 3240410 858496897 763337172 863584040 283648536 262534671 655963283 276956701 58442081 546362357 608769770 70602343 557648231 10618989 317073295 194580778 44396319 889132731 930590783 348713529 319629321 479673977 766120611 652590459 879628251 106075680 880771070 113308282 980284959 306269881 333479087 228396634 187289354 640569082 582859845 84782668 847657862 658618456 585664643 379317060 906061546 136697837 981897767 852543584 895567758 400236930 359021757 431803436 839709948 279394809 6153559 589186165 192326496 7259603 933081430 180476896 748337051 394064653 790155496 369977151 831603110 474169491 702844373 941513269 655392986 452174283 364977257 664142551 313685707 175299397 486050985 745676975 994897672 652824442 342463871 152248198 364488426 262444488 678015239 313450426 517486013 215120940 156080211 438289091 207917034 727019652 184183137 51688795 867150040 606810660 432168968 429443413 562466288 84948358 561306516 764168868 298128166 258033187 437082808 748021161 705222168 482559213 840083914 350040692 849676742 115173079 754204873 885253560 592583027 108465244 387515733 598551807 992177855 94872872 646104576 81488762 183037489 950516348 93150577 477235320 332543691 838151126 429835167 383340192 36556385 395032363 351378430 174339776 167192157 478784417 58138282 394656974 737076729 517316925 131241589 147161001 480672215 946882017 94254076 214706667 295378613 8620254 251849053 388018427 311393328 677873607 231488119 843386612 819034343 600480192 151963194 298646115 261782467 813437140 434370070 942374534 414831056 843440903 479421736 67086699
415497611 15110019 296678200 509350210 6808180 958080837 205884008 244029971 162965577 781794054 942926761 240124579 35441256 816194706 670636418 158915898 4167327 21068065 346509262 560179966 331947870 394680846 886349524 929074379 532693338 29397560 319785479 322311670 544040861 999157854 872562192 204665972 928095374 587980502 65950049 759968673 177929755 211767918 580006049 105819884 183249942 702088944 966413495 417403120 872236017 234258357 986155899 221697895 925078088 945900846 297048854 352374092 759909131 686654849 985001253 891342067 892788420 936315034 940806955 907726785 133858873 187063839 441847358 121842866 201658205 616211242 339979535 923945241 118238100 667633997 997523786 549464282 42118108 663175917 943007186 670377905 635413761 391416505 11631427 967287312 41427860 911949248 783638653 490131051 169106443 24165471 255188553 862282877 167996868 365499622 80498888 87981602 354352321 108498436 785850721 683568684 228559676 854849648 596026030 129367868 171541622 837294059 172098504 524398053 475806858 544868099 870134227 320890934 555733642 174565425 420309016 138776505 956039030 875354988 457985989 839788575 863339377 234233490 389640425 497196439 940475092 775497870 3318404 820014506 417873224 197981209 887423206 537126247 726465244 373319415 360019750 870638666 653814660 429116797 975088666 627055218 778956868 969935515 872699651 868061861 833285493 884972263 598654183 625726791 175297997 755927837 374602699 551015209 792912386 639038656 618885206 467249009 667168363 314675100 848555800 476640361 530639145 207356560 846914550 878388202 554684729 939354673 120026500 850520251 843161121 985553094 471433669 617125888 472151154 710613227 126846762 659404711 901276361 583334220 885429483 206869577 243481340 68589120 293436865 484921148 50779732 746795229 566440663 118077363 480020044 613483069 768621456 320432835 382075841 40347373 383524550 414072943 187700059 918499912 612177204 538616530 42841499 429714923 510200653 887828786 38795693 589244306 520113828 675807834 392767023 237758800 767726208 488294050 703173949 345721329 282128275 455282483 425539458 887539560 346459238 54182884 657729429 62207973 267398916 352197981 554058338 774510721 567164967 848963107 667887816 617338265 561399893 313619705 529647680 158195541 674232601 800078319 313770112 85414712 667958958 40233813 558708681 492132570 169142616 728441821 505408410 157265235 243511773 882891329 545547503 322459910 263796958 854038758 468968793 727059832 592261061 791611225 1265752 525708920 611140242 74547441 725114944 852722866 105440639 65611232 340054366 753956682 171894126 890840143 826488319 288753053 738549340 387123352 960408793 875958306 630240578 2334830 759831406 927096125 994840362 152492718 300354941 667875242 871448853 560367528 161358207 333270943 523878369 116845786 527596402 928067782 254930810 255862484 365682023 955305075 298063621 496567324 435219436 473801552 625109016 876810214 937636828 521673548 719791020 243619308 246846058 44558600 41816896 896005178 309924944 890077204 571602722 823896838 166344732 93214214 237402839 353738438 528004101 732087723 504655928 107435240 645913969 747117266 713063719 162774815 626119314 426092230 211948714 626429469 352475805 236043516 210172691 250027682 95832709 994982401 201434227 859542192 789590246 902610436 775687775 814636081 522124239 553783584 470350762 199103933 641009866 441649621 198791281 474000176 614678664 37343525 446859327 12642027 867299348 978331885 168268607 706867328 593162279 20907704 756114207 17737306 596547432 529942942 589621488 75881546 942143443 272536276 697959398 192893089 548569148 802978920 500729470 713352285 276495796 92868889 371155969 94405626 778842337 550218704 736888289 171345408 413106946 615691840 331842989 27710795 723455917 217501776 188112208 526105689 733502617 310251502 977962755 724994026 260092058 810009748 81976594 974753319 728967576 419237440 458492167 963637394 455113952 164390477 459768017 721774635 285633359 102349157 815513780 808696011 330612925 197015089 649468374 545726044 789374091 412185377 985667265 252922602 468821488 167685474 563949141 625141537 772089479 109446729 230866554 588192743 687397813 6161500 159037347 404328063 631306807 829795153 853444934 419911548 484274074 844127286 773074482 142551627 528502303 945172945 796447233 193748917 502067493 888638413 282894855 666761223 160106950 259834068 88270137 823968201 929112383 64926568 921077500 88981424 564164771 368127121 621642477 361647398 565222505 60317488 400655818 69035795 208642178 537079565 293739345 601338836 234633174 419920645 222928212 169910002 335040332 240945317 180470983 152105581 276068273 613262982 31912007 372387388 38758453 685430555 818661597 436187267 922501294 81281576 839600659 126550559 837493393 485036230 359618935 126742816 728188760 411157564 413050257 306003778 435954504 783978864 536151 417117404 703233709 27429994 876671230 333317304 783840065 688030179 696394632 349307529 992679868 374237186 43126539 846959847 20441176 247046847 454631826 829071782 981866666 402570174 412367497 780170631 262260217 297862054 790297584 711348093 694900892 305237626 752338033 407456394 519271539 147324510 801588905 730285834 446466948 540488668 778065014 893261370 763969021 148776531 96511361 835946308 890056643 377139009 878282627 523416935 799952262 629375587 193098131 798189779 166423304 947418813 755946970 162689276 475334524 157013458 203190698 113927048 435403010 667685690 567425038 719052212 376770776 500127506 892003271 534994772 548803144 86870548 691270124 398478306 636570633 364863437 630921115 558997193 417335293 879049675 287694936 809369447 788338694 434831920 164922375 880275201 725739522 6253263 691035896 352362320 213803821 620396035 374638883 848907120 745022015 894073053 6034687 742264433 950271845 733067275 685027381 784833218 163713910 579604789 9999325 199079425 656296103 383790497 18360519 275819336 194949452 402342373 540551522 298529570 398359202 644092489 67892691 23381059 10929727 358117290 452044630 271534211 284877562 339504023 134243878 660166409 905219561 946737732 596699863 159475830 146104952 24715877 79749915 937928907 837512031 534947655 834584870 656538089 794916396 588482945 441150910 88139333 202214986 784487834 941851757 512610009 245472981 518983722 234111824 457778801 562076 710789506 884537326 103180355 227337053 703620458 550057200 401582307 40630563 121659216 687460734 768768265 690231681 615496181 822379034 141740318 775750727 454163193 817300077 359222490 51070996 872712128 446029981 700569883 822871800 840823261 464507316 784291267 109309808 517579678 89155109 877856219 31428368 249402084 927808984 103282916 509662647 544114073 245658917 85395462 273163458 255899205 169073739 353424172 6603499 730807449 95551819 477532195 441364001 114165773 879480402 210060030 695098212 403518273 333233284 942411904 502993527 737792801 605112854 480548460 473536671 606119112 558759387 14972463 909226452 932067756 214328320 979394080 67692808 837964716 600830938 973501916 584957694 823684455 574105373 156806461 55563455 302112840 66739602 174962090 381116007 680166046 821636315 517911922 872791442 57688675 507541623 216371278 953976226 622689817 141682368 71774833 263392436 361617898 973994569 492361955 194568504 938208188 876197700 195869192 812117732 256832545 925275871 821714777 546142609 123970376 727734850 270191944 633955095 824898182 386277710 131585551 166526477 62901240 857041356 519975077 978725893 804698927 705033462 357578612 696134253 961292573 856239775 917294368 58796835 399509473 277243238 423356240 680029701 78906005 973755436 871727952 124679407 282726434 578970011 446413910 242683085 690687448 427222189 678737540 318213194 822718969 155548227 242050294 614113438 222984550 460363601 17496384 504349143 349201469 327055084 39760485 249763489 120570578 896706849 738812753 374986895 121409621 968906111 687043599 74022721 945589443 758331612 983035536 840328822 260470615 130331755 932650273 823313073 162606920 524385045 268383396 710085183 218688273 11371812 499011865 428267633 456776803 308139272 256914365 180855509 445391254 634135312 145466976 864812289 643847855 858249232 940928904 680233800 89535559 13778737 193902403 299386372 56104417 39773681 8844530 718330878 253057405 626111244 386700157 243728411 507544304 578871845 377561450 717142375 885695434 659901294 144209692 694436070 632471982 971744677 389874394 531190454 652365079 126163194 728517068 675206182 125092511 50065618 717107 557682698 854977275 622872750 794240304 642052022 872073391 678211344 914416459 629353472 210999081 787235458 172492727 252626281 178669844 698277146 763813210 741989777 938251189 517916129 213606024 216561652 81601594 888163166 483885709 826260265 963243985 54758756 505858934 859654568 981861237 751868521 244755871 594386916 439805638 168147068 998200910 404434001 67158071 636995186 148897027 319952064 570686780 250019101 16915009 218128689 908492507 109686540 453626471 995101034 1221600 961705570 625539249 610228973 177560790 893946546 308163215 269360819 31657210 493960156 997283452 684053019 304670282 51056925 707378714 303341054 229676453 277651612 627682552 715160451 946483292 258663396 240499870 512255721 431461849 130760394 464624084 712114042 985419877 282940193 383165951 672696686 228927937 231083105 275550806 906355642 581724077 524858608 540574684 664132946 712774650 765024668 757686635 471286253 69398060 204778765 338678414 446180240 721588043 96389151 384183883 561664563 119447035 904310250 158360223 151445343 930305824 391658077 601763860 132492587 112519344 129406230 709816120 879752702 91420312 533958523 601787179 478625833 189087790 397552443 716869906 749368848 610871016 702113262 722781875 725436784 72442994 202065108 108471162 432997436 780914996 177074441 260273991 207207966 7909850