990 90556243 855617982 789907418 119873522 35099154 927534327 749636543 286414573 189514910 102206725 570427625 66929743 920906527 57768142 113808338 234058190 8390045 322019324 254428766 13060850 8542964 458555291 689438599 708008855 66731696 206090910 722915241 501710180 970628055 329181865 926477168 588150473 456018968 898986034 36986827 173343654 413378100 195746123 26299105 481504391 177760632 595024244 246035843 382469313 942462339 18319538 883164335 424109929 950529211 215368550 829855139 96810720 72546874 238756895 845370095 430315158 97713057 67374961 687032748 827915722 913160984 496099630 29969075 663477753 225857725 130357915 824310666 653556793 769733406 689062048 445414083 494178053 947007188 508373116 665976714 828122318 79085486 175133380 632512848 224875580 254008253 942669306 56728615 780618559 477757272 384016040 447518584 234077226 74116281 144102857 818534484 336003306 111733353 968854527 780796613 536667177 862045109 838772568 867501913 193055859 242258975 9789282 115276155 582099057 541433955 591538163 330276422 483903921 934786186 853726442 715092311 773403984 465735264 142420425 82901363 341948016 560934422 754682989 954143891 500906515 519922458 479300864 625781275 866633970 941707574 471954729 882412354 829600512 669931031 926078625 284559492 276242438 942285437 396490288 725916641 875759937 239339444 448584871 144778246 688907074 561119434 893805225 884357084 219712785 478368845 525508870 941062092 834116694 461575254 232621706 75523758 540504280 362573441 314550954 645230211 389436369 918340639 193206646 744964421 633013657 294019382 683972509 48415945 788535017 380438627 269393195 12860139 607543668 412121291 148299649 309445551 907087947 728479415 428829282 196916788 595212760 701837802 983904588 971586016 825204880 861388640 158368144 160701904 922152917 55566243 796321525 347154365 496746331 659130597 52731283 971413968 654054068 126826164 130912428 508423105 331559153 408144840 975140590 327657242 966311365 833842430 188899015 640750695 913383522 434432910 274046942 470173908 998163161 312278503 329106365 225865177 116675599 563316013 574880373 5561858 843130810 283446357 544413232 823660699 268287152 114649195 920875672 168658783 482681744 211562422 943316608 103868308 804291388 980570582 929715236 543963225 763468741 320426882 930389626 254504987 840993944 37757027 34920548 565408491 120657886 347437106 743470682 931371327 869787722 649457811 299563029 966808979 238174632 437380268 609907659 883898962 448233400 796279638 229615383 310283305 155190092 390336561 420672482 93082099 627695312 179866103 401502395 593858386 942565156 761491789 178279167 148298778 518112573 801302088 215039265 39541285 91541169 469417526 372375505 464354342 589620368 54275546 359516882 888560696 148683967 38851362 906158384 908391265 28705161 442240735 223920092 278271930 603869354 572595655 542118343 920959255 452888766 929852163 354879007 211089961 970640737 898075543 421421215 364930678 291070765 516738525 405061547 389487583 883319657 849247753 824847110 804031273 368601757 48600434 554255776 979519483 826672561 328880457 22424058 284466580 494002450 165324035 849918693 182483679 673422688 323223872 958187063 387973345 168446426 902752743 109406710 575029674 23857987 693770138 36195788 576363245 989920449 922363656 709242984 689319521 169886921 271007808 201583627 7188301 694394835 778258515 277577178 604641545 69046016 930408069 848403849 226754177 863542516 748336344 458720638 428441557 257235730 463369190 825449580 174134226 825568115 152796122 29511356 525589048 233054964 104454845 195862819 220577588 545199409 625253645 155810994 276182780 41445560 292993909 185403959 154424802 720716727 486508956 650083936 668361552 735593128 640623311 918488070 327527241 400830935 946470500 335611533 807268541 863888740 103096920 626461903 196828053 181473870 897568632 979381132 451780161 612361220 259262405 427165132 549352731 411941765 357394885 306698278 374247315 241852720 244524024 806440626 708459299 870126013 230664998 570259494 288024013 37792450 288159735 436635461 719538530 166096 356519614 988275456 27688285 83018931 597678472 597776603 74119490 918382017 162148666 574335619 368842332 57678246 635452461 539011986 521980600 861044725 474231802 564595635 479534329 443616857 617119401 357744130 79107919 210481034 577207862 146294886 562410087 211360811 947848386 329262665 803985533 705706065 830439969 880092516 950489518 544564528 244011999 264131618 939946498 929880844 225036887 418330695 778772043 849873144 224387369 694280123 636543931 319823141 12475528 934868187 76177030 727115386 283011523 484302736 539815199 974099657 206261973 922330711 295749401 110784775 320599478 128520152 78565100 418831321 653692981 374720248 21298923 814924840 308820377 65150999 75061537 304773433 173633745 172113253 333923507 116226141 965646749 98321749 486924374 551344979 640111477 850958219 730179824 660689808 855806637 596207837 733942443 119150068 216549259 317854631 87818441 353070076 282353583 1621990 447040117 62359743 350212704 595150058 328103120 914483043 903097964 143090351 647047731 990286120 601864831 232053319 811399093 965566378 425946372 647038678 110773844 78026111 391615920 594451861 624387864 500380836 962963258 672548431 173112196 291794706 138755373 526216643 788726958 603525688 523175810 443640197 19968485 136096207 614111274 988696913 95312975 545187823 240234989 487777889 438569073 283409307 567059577 477738336 655164934 959764184 508291990 162919832 246721389 668155491 236985241 174180833 632237316 822103798 566846261 564673073 254162035 713243715 862942528 106090547 883327798 788035208 111184004 913731726 759663853 342047834 995525198 882458897 606168013 473453507 185751223 224092525 82759062 643484599 504636157 20162076 448029429 447314728 428457226 16267447 310600276 306705450 466926802 453374034 242722884 530216079 543329675 230047832 343338950 583844632 14755462 566543866 534889345 295940263 512010568 847675234 220981737 157325960 110767385 376156979 917860141 594876473 701075861 257864731 66485275 781686948 573957699 728222633 669481347 230452680 67394030 649363189 44068809 182029960 406045062 416780768 503157182 70631765 694452936 935468959 377496117 58029213 1174414 473059441 892229180 248612965 640521281 742859466 210877867 18904044 412344137 174694423 785339405 644094889 258272840 681384526 593465632 808814310 207512387 453599513 909045074 332835978 701747650 583916051 168950642 598128013 794872028 254251551 92170955 890398851 136993659 431425867 367314566 490112349 426574315 905363779 111650141 21767705 174817338 433867725 981224432 471209580 991000075 347244377 667706682 449217313 636357037 508768392 296114083 458246264 548096924 978635470 551455257 826980421 202168287 706662900 8967870 461857502 126544117 273126504 839601931 746607496 300055108 893664192 248973992 75143322 823109551 892331851 108222852 700207367 132978429 600073274 131225656 359054137 247864104 297754200 163006110 806784733 10317478 31718021 619722134 43569685 452960248 117627501 778334674 82288472 542221386 309008980 231497188 286287711 376615330 155464064 510161902 790829707 261828465 322756688 711522403 773337806 141323119 106064897 374124745 512399361 58495590 569428803 889868520 324032032 332885847 108277016 139899339 974168201 168884475 195687360 692299212 332134066 594705300 877850408 111714219 284000597 131003405 485474909 278038341 18912121 958695760 820569866 750016987 407277503 781996101 34131647 699559601 936367885 935331881 695193693 145418710 998458056 118329724 211586263 9167352 501790627 184780276 958392079 869209003 876446756 424313957 455920264 950402563 702781210 157631383 81712141 951374710 51292972 53717007 589066895 220019313 735983638 75358850 54241349 869381905 607641938 932226558 100689931 213454567 589168322 674696488 115344686 495583000 278600980 655564115 659028301 828857370 446021493 476498178 483581140 26802261 254999329 289053212 276176654 421670733 185992385 479343465 788503802 472123384 19048961 107108485 194909723 723638758 919669532 951931968 59908171 67567289 292585426 721820295 4262902 350925153 892776705 688909125 265660081 748684382 738586753 126773728 196885888 40789207 640257112 751382770 694836159 282101941 824730157 738399962 149411694 322268958 672344107 772808580 828875450 323918492 878217961 882891153 2405892 269485455 682860402 869547217 352329181 959896860 447833772 616682882 222838694 28713885 733413293 779403993 924673022 46026933 463809714 4768714 193122706 570475438 259877862 812374164 73724866 438303638 701820543 198838862 669897008 646941589 425732327 287056741 271953655 447820269 604183424 370537236 119919687 513203419 798684373 260521431 101712940 930482483 580373024 559240076 121323026 774657639 328770250 149328534 659824143 752175041 301926184 341649353 634337919 961961209 694093079 391036833 490666381 554522935 511604444 286530420 802837245 981214841 938450573 272802629 958438423 385877155 857352605 180206269 905912772 784907740 169263086 316678907 421988578 141625124 196742379 739556914 129827086 993529624 343619456 399367239 441521175 803092026 355157090 263057857 373320920 316451650 786789685 466904598 404456123 13569089 897192953 63287 6536397 420299790 912244638 610771229 931281313 169653373 549560166 769516201 812682012 804434907 634861090 683622997 108040406 453351332 116993174 443752559 446836197 16299446 169859810 457891475 613239381 441358608 19346623 819204991 101069190 677422445 245231713 343262936 233725594 780292982 374446862 863595500 370381881 596755791 814824075 503594371 42894862 538034727 355527829 711953533 240216866 2418062 999456088 66820551 573179610 813440852 332696037 154875879 216691857 396803317 386753430 31841106 459240867 246906848 118914203 62469128 378651935 925843312 531413020 530924962 87220799 928944314 368216868 34213543 267381890 106995009 13153438 143289450 352755677 585732032 849048802 292677927 923452322 922356381 40818539 820760622 389450941 195094376 118800635 548008513 78871322 57127248 415144041 434482328 675137106 766977965 445312370 838032270 601900532 652995775 579284068 779494905 336051569 217517918 849979362 854539914 165925142 712263801 489278239 258744842 678757947 22535302 517184924 687650770 708443654 273001918 277891887 967522108 97094833 812194844 459419598 386460502 846745153 254670085 139561396 682349072 690160730 479286195 192054292 300817783 294690260 343090000 4182884 16512483 566196610 853135441 99092558 506218890 416885764 805280716 274093827 426158879 559987424 425159139 711456067 518970065 410713599 154157813 740712995 122569820 412378569 376894317 188243952 487172693 46106628 908209417 538963632 561132907 592663069 366588116 392370839 297139744 794418237 420111559 401950745 743343085 213457157 271261572 105415539 259377496 941045830 682825938 741682188 40241848 160082221 419053961 243001912 32204752 55244949 578874322 163266806 945831335 323323310 203158678 727943634 517283290 503826792 209480683 824259871 407404655 44600899 451922784 619471935 4857438 318250931 189685533 370746007 450208611 350876060 318215587 733613037 684732189 492065253 922214378 441500768 504357220 274593195 541671179 261601041 684409782 364428672 292730040 36135024 816885577 360797194 158138597 351252823 407484798 690364005 505891251 191188524 652468779 748049722 625879833 159730709 581079627 103637813 729612702 160695639 717664767 796629700 266339653 408266295 15873154 364221494 405834511 62088494 220076837 834582500 454993333 285082942 939238987 189416276 170736742 990086852 707096363 893404078 92679535 962822861 53920746 4555289 923853635 506249493 94806364 509113288 671958819 524695471 898438114 516156578 246185124 315822183 894267859 77346033 587384465 130698006 741613693 946904301 216895689 440014765 313763644 185328921 175220904 253260964 530930104 319456711 122583176 500716896 140070136 838714761 972413896 808093711 691796145 811778489 72992086 407996408 320745012 886868324 437359817 961735943 718006951 305372335 467805173 588768334 87707954 444184559 289411388 712929819 290393413 573926713 919851945 430506251 552869490 904501990 876490387 495286695 193610179 949056106 825002778 108763266 298231575 233866719 381362256 827550839 488282244 229600880 294531308 7296699 268807753 545496837 99965220 771215905 977317955 305913025 386451122 932043598 331570070 484642492 221535958 26008666 594501381 672571673 639976993 382173142 156014186 387705009 882570080 191955009 639810791 589572506 537873436 276105501 765486444 361377452 184608966 620319424 240567851 668799252 668837723 995936121 462436694 443785079 537363785 105911660 874008975 972423295 155707414 698394765 984105879 186249402 289518866 380328828 773187770 844972074 868032763 165258717 370496785 209254121 958465429 497094724 329320400 468740386 412467512 219028232 138504918 412300947 608022770 575398663 551453441 831934769 35169717 502857036 689129512 599045430 171846983 912100814 964608119 953044556 148829763 953119710 217010896 739203590 220947942 920234747 770286260 514158488 354293064 81976889 684913875 507696033 177621666 150803408 364517392 397261009 886046406 400103001 23346364 139670177 689964117 640070522 868275629 607931063 756697206 292855095 785285915 779790566 893314669 551242940 50018244 333710026 171718907 566693719 362369937 838801503 188718407 77783005 505047390 165719763 863937608 481060448 90158690 46075253 151234866 599670849 928417543 540550384 857549842 566295652 516331181 696226791 541836405 550537301 729044451 65676529 39150500 462434078 676807204 463760493 849224668 558778781 35881429 577282197 649727000 128352040 480870989 152844484 420703773 678733877 220873424 807454197 6541981 927869659 980511596 488763795 344952641 601905992 618362110 643033051 154078592 19757061 97850634 251618893 653474388 997712135 628501012 852608656 891049175 623635604 890513996 592733024 866331467 884262620 360368866 939393123 48951984 988292171 214839324 969249068 153758456 573767066 238737081 346585376 736467888 556342433 38016311 979020933 294866231 196008354 49081027 440552340 92717336 344827270 731187506 312985200 46787734 55759965 874371191 387419685 703780132 437543223 293726244 391279888 84737980 230331799 559565919 126147896 142507636 371687540 263015199 875304006 319723001 689331403 194673871 376996444 228515553 399259868 321683497 142165620 973453772 417268733 48609447 976314511 360829423 988284579 973994893 221126730 269073157 785424854 827170283 35730111 383325364 875028019 574246928 33436914 45710548 264543803 213329329 29546872 561190240 385090529 845451402 674468875 745271532 297024664 685993712 522831665 594792036 541276259 95579446 217114506 423411499 429455577 916150991 990446913 953337113 943901302 903332101 886447419 840088706 209085401 380818139 305457263 682114410 43497827 100417174 912423382 115264478 42109590 727863206 145584167 966975162 225934781 463828740 499775181 648168623 49661135 366452757 823726313 234617169 112543269 526698997 880633978 38173628 683013225 57820536 479532120 199854954 609841489 768495388 840129926 252249238 479596708 370041759 249171962 158476196 519726618 559133218 20937852 536302148 114837189 281292509 887902794 71543745 911742338 590754807 225457605 820263642 274079832 490018738 478356760 408042298 872394838 645875304 660198011 273504107 477128168 357031574 443862724 831883905 968248551 368053547 147698538 421062529 168325520 462289348 404362504 74045323 947187399 904070409 465332386 788737065 238389875 125474453 69792428 96433458 187087479 289992388 459116237 594310853 751699289 658688222 15311178 814499506 30197764 288309519 367765419 618889118 569216951 507652003 628741880 726962702 582122720 65983601 390347943 326088740 133891997 129273907 561107731 977330895 279679964 8943813 995683724 990149208 345627881 865247856 351278220 410502710 972445074 587562571 48004196 948786514 365091388 174687160 359478752 651743922 555310307 889704618 215125215 270690750 812319391 14461177 12999094 511566458 107138997 727815375 561295262 211557568 135977006 655225993 441820984 881093332 835702519 121372770 878241904 324904913 121285607 220671626 98772212 11679115 641876490 558985476 904593245 505589837 542196184 255384168 873912049 55362266 991923247 196757502 578970851 693988192 144314361 149461112 208416178 741112500 967997591 880114024 888390209 104640637 599266153 579618237 873679081 149038402 739266453 465044992 300839310 703743906 898701815 326416483 354037617 730861663 715639902 204888528 122391860 317971033 441830388 428831944 477488898 774919630 138029723 612404717 778213577 456484568 72218863 702824353 578934735 393959574 23459575 135147086 524442665 244319956 831267560 710319373 236230492 170565029 62855165 265038956 765198759 376188494 20229233 126411176 764725055 362094113 961089034 20404760 579247900 264271716 261206328 378988622 143280400 423650684 616754138 579567696 495920008 908100725 803497888 959169657 391179936 532687512 698227581 32576714 371084642 107349344 737605313 815873999 627656567 232998197 343384167 640949314 790960085 373311727 505810490 470550210 481718145 801194084 15878536 199032124 646375906 141418735 988076390 327359485 871352011 541239734 305537124 334253411 459925393 370635694 196423410 366015799 464497179 52705950 840447130 258081745 183157732 710722866 655386577 830105532 464835030 226670739 460838308 765833257 873684060 942738289 679691306 798017625 758207181 968310684 467837385 133741251 198924205 807419739 755563879 281014231 816759337 512131058 941514940 106856436 308580860 116717849 731736991 981579280 966386971 819437373 221547087 779911925 232218310 1887328 657270124 984215813 209346994 169957159 322591514 847524691 388295109 455555742 415877000 685619759 527227226 585639825 462859674 473719298 764318915 370502203 165538700 703940823 195038990 446264236 955599707 29325701 596145727 405042060 79460932 503394807 166458818 991713299 107819467 92560355 898804204 137523545 412425375 498979586 855145798 462535888 476394297 544233475 984372497 467476582 614603691 162217515 19389599 114927521 276134521 526854753 935142506 432925591 984794533 273607031 309044632 952759418 6033814 269862094 734805056 675602109 47925395 455235306 498367040 847518360 883100732 576057964 578484293 245086076 166149450 565612902 229223251 161575422 628228203 40139915 820842331 959529518 372350398 276913134 440633271 3630849 293420691 5386495 50357555 659377066 63472627 523279494 316929094 138800053 820579044 994911993 247454052 441002057 365087175 16581934 511166386 723709598 433488698 729960808 631075866 242700816 751911791 77430207 302004568 750242415 271883579 472501642 696185724 847055059 585018372 99718319 535086035 352208247 6011256 941076550 448970830 284825120 335827358 978615906 597977307 636489081 706550727 673437440 123223393 71720930 532241208 339370206 750634181 975987829 754182082 210469320 785732057 393293443 523689075 746141053 375308807 268543835 468841976 165848424 399784211 745413660 322827728 782002889 135643739 148125503 805011207 43405321 219082931 290576221 751364037 718194515 704448553 212240218 930834657 958144747 310226645 418304886 120271622 262037980 231366614 528810622 824469706 764372538 834698038 381814961 997986669 665344258 612421467 805153821 228192518 478112747 150796349 102593331 134803821 659816790 494011352 121738212 364908573 298723294 592184824 988482525 231667655 401796313 17278376 557296168 204915288 895206361 420580314 397976384 240411354 167124399 317709896 157953646 6706691 694872227 92467301 683213153 64911216 684557395 501255558 292086684 517612959 282538076 852469866 135227740 335656821 914870594 496696303 946434789 130654186 152246067 218626683 236594727 971530595 142307815 590214366 120277440 256694572 373984209 699435286 381749118 711225839 579719364 820227843 94405826 910529284 68307635 357437627 541154279 657858645 61112824 577517877 563457464 798846427 32872956 637543555 217388331 474803574 523817687 604620051 639625293 887450265 73371754 81601793 36821045 697206608 68568250 676712474 24235517 154464424 393274741 800972510 446930808 819669067 22858908 807554445 138795033 320971452 179351493 370289967 422676483 534178963 281566538 381159441 76667882 553305230 18587541 785550483 583178606 605561026 153152292 441859820 626663093 880562438 418373665 771291995 233470993 797576020 53919430 708562545 415526680 897490694 429949261 815093793 688324917 751363186 683102516 716977253 598864364 603351375 473367092 660909971 113555177 824159253 885401197 979841236 292865229 746638052 79242579 158734342 526942602 550210152 402499807 672041688 130706231 568879475 332285752 645316174 45218891 551288379 52306374 393167100 391457068 601943114 37939707 174404273 264682092 890512876 822431023 885419018 122476242 502814550 83290589 153821471 27882413 898537812 151418772 854606854 482420109 841351063 856300190 977808420 80117836 772865283 449077003 938316853 214179543 682034004 225929138 570244334 147396792 744785919 4869861 673989900 635765588 714999444 39096802 559026305 75776762 105609077 352837726 421038271 44303886 313793596 637070807 859333730 27130282 127328496 273079284 348013219 284864033 778421965 147906028 177957192 179958251 404752246 80510520 169417965 327537040 879936873 56937724 872487780 81022574 989328959 143592151 323952611 419670452 645585606 184545504 998906939 538773330 680808255 236529785 450439757 118575546 185088260 184186575 430729059 568655803 971118958 94335201 406130930 642017776 711962792 122003174 437895309 532361613 844050021 153313781 216939349 671139064 873014610 347739135 845088112 23884160 357307575 87792297 994763135 168934522 749130709 485881815 696446692 334054187 408678462 216747822 340831211 476960661 924953578 18848760 318350579 268869722 358814712 303036067 470506695 688983804 848476059 94779704 426008882 721212948 935251335 73441198 938040211 15679947 128787803 30845632 727303119 611007443 718819090 158346668 594719127 278355404 365999903 525871182 629002988 339457677 853347523 489363371 788759413 16733831 119972310 470482342 487969068 184217672 498447833 191468528 578011754 260186810 665860141 641780846 829797341 265406444 404528643 124640163 280146429 572461503 895871178 365963991 579490469 145629883 751971378 246333314 539639781 299649847 996263106 235679215 723513713 740711053 922386127 444149168 593844414 204255583 605075271 170283640 821259081 413288391 515236670 480307398 625154132 130167276 428272034 529633752 552564319 533424168 775610894 104019258 995444303 425043815 426840339 291124873 613991148 108384903 910933228 100194250 951308438 751754513 902105290 256786505 292568914 376369281 499901118 110986733 441687334 591666 766358424 22753748 287075610 706587529 780520552 708642013 731337286 139580313 525475276 68886224 297746639 122933481 400976381 22086606 763892023 253514689 974479295 921217382 998446368 149716086 797997799 225512455 429465815 184262618 389519030 150578726 281950788 497815653 681933334 170519639 828981973 66923057 358298258 73708977 963907942 49573331 526103731 732218395 758533593 349564831 976362458 219440506 957521419 153479897 441144018 254721325 791957601 185454284 458190984 745895934 933709919 303730007 986975078 263344089 736010819 683390241 863775450 547700034 627895850 963584347 984111782 748918112 899809609 76611141 565428822 391056035 591363975 47160647 240567591 330198882 968613824 254156859 465160985 275691562 397866849 346427340 711180182 526809690 936201278 92233567 148015240 351062243 380336221 290224885 668290295 355527206 402411194 396510583 416340329 97878887 369199221 451437169 699283592 182222663 284409461 150297744 499740846 33659268 387111833 274568680 665155180 163921503 432144855 111543599 309070013 295728655 341017800 322279608 676931295 30740481 838619808 8171614 283540560 410267460 960657348 553992312 705909032 632483436 944149683 375658336 930498259 47601092 930381572 401831489 923436910 38334611 657686797 64954577 730331740 185355526 742063090 268527277 916083364 350607527 454822806 398003812 786279454 742253 828877051 511452654 574176893 620110092 623038295 494454092 585957615 203450104 650582666 307111087 786514658 359154381 596017264 130443233 854750903 89651460 746631492 707871193 785257984 129880020 601730224 96026138 452372197 183459733 330620831 353456502 825735688 369138410 494484840 253571549 575222029 1848886 223286552 520924883 780087252 287091142 642221040 176327544 929246573 135328226 832783553 83703040 368988008 56455097 483882046 362125348 532395101 208009856 547808940 390512798 464330852 26694193 464016486 681490530 692927898 224190456 515964789 451661863 779211535 181931536 949024588 361245207 564234855 44585998 594385400 316824563 330975155 340011946 833565450 574212350 712935241 7375705 233329041 743025562 931604130 590827067 912201753 185551992 846679264 87780540 633611409 587572820 974583373 17196333 111410181 240867063 409759152 798702315 931441445 169705061 993058696 10857 817438290 305182969 709790179 87349076 352958049 353263225 907285769 292791391 391689965 687742261 805034871 41995535 925056887 929123816 969299214 112588452 784651300 67174258 559040611 511743076 894761000 144689640 930443730 175230324 570704123 349480061 785240967 529218009 989110166 253927556 934734647 147824051 292414900 707559737 835804898 728783637 745718474 568641751 688233014 48692709 165708626 306682546 651705123 203222231 740119434 76376334 86112709 180859707 549202575 551853165 734520931 284686817 579643066 405320739 558457443 111368824 194149064 14389902 923697037 60137118 422008985 42526453 503990409 285063216 461761779 316449860 982484822 712871995 956670829 766526735 980333888 49816753 474759195 606297614 825176119 59670421 120378119 773866438 845259851 146743029 525988046 220705518 630020916 10964364 404259309 319871300 762592848 78914385 428028895 79195890 187342931 192830179 356817888 160052047 627078350 60141104 285817322 249800749 762762300 115259005 475476549 379320903 431970767 47259918 549266445 182190169 741044892 628582906 751513696 470275798 952305301 175263551 219987357 212573479 308532510 577908524 597729911 169719763 984575214 349437666 484499935 239171363 540884887 287044490 916991342 781485013 979554024 506732767 602827177 272362266 942878550 485778034 844360822 163939612 758275907 533784365 850152473 262030751 285375445 272159580 814819365 442376727 619310363 599544412 806506242 457160100 459638304 430038745 531204425 125193219 452701942 473332324 770224975 160217003 876880933 301456685 563751553 212530377 304011161 130234056 934537765 151706841 601657021 414069609 884184343 86902717 796194835 398786975 761172273 628772940 664996728 409933874 796744020 481580051 814420200 380553639 437214201 537114950 996518812 292757163 954488540 279844342 581322894 4255667 372116282 209150379 974052411 330093945 700447221 187958315 253546935 382037374 665899174 43930544 561535156 744343927 936682889 765742351 991982203 351485239 720406092 616971137 883730744 357884225 821891448 212538664 625977270 292147214 938564397 214194354 261317930 120867624 951345675 663924932 954369166 5222249 941747906 686612875 833275834 532970562 829964782 38962363 374698798 5231147 88543973 281095335 486945794 302826175 636194150 469672631 583202777 274600432 751973415 209179048 394099972 610306503 621233694 772095234 986506698 110465012 897448546 337237448 488765611 569712260 718249474 268674441 374134234 184780559 275581730 641515386 653542071 33119443 800714317 239751054 449631383 195722319 842751054 41881175 794102198 174632961 440083741 54945871 696736916 696312708 702706431 728866733 826410246 175846674 960352715 53820582 364856540 90720325 597106647 564068843 577025091 349873396 816588937 572938928 844078853 175554585 236424084 28873701 890583193 38222313 74113536 459510552 979454530 536576555 832871467 366038147 373936509 152723855 644807425 699303075 887109390 475908138 846178774 545822290 958706389 199878964 919120616 349772857 418212527 452023549 796906043 54548483 819252298 469774444 969704449 726624728 962776464 216481745 553580145 4894639 894770661 501144802 807404193 690580088 781104016 412347582 773322942 236215311 345690604 379111635 909306993 234489735 702652603 629397429 924778584 259735511 869300191 374440843 557987801 181216238 393008253 150358139 966993210 28823510 641954081 589839907 821245127 528057589 793673134 767800970 989330712 622384894 687762234 667278296 896830441 7186782 45358328 269593041 938843222 410715770 683047695 137341519 749336296 534107503 836910114 328811884 798161869 24211354 251741561 32351339 905824971 185394406 243731114 476746216 514881020 370410361 810627794 614309144 982785625 597733187 611923598 74614308 449149221 286448000 906239947 55725919 177667345 57040088 231230291 191371351 248954390 112844770 157532574 532824539 857146497 293659527 506949635 247360317 307417639 39767707 954584057 240463904 351503775 547056929 608131804 256867900 704135408 177046719 395299392 361226705 898077000 482597246 570857645 165164306 586854329 586215026 969078546 162463615 605993517 131034424 663094162 224147634 512507039 272620226 359283585 8378896 683381073 74586265 521217099 291540231 702520856 662785770 938250061 42034413 750389397 350106980 938607019 561934971 634638860 134126715 148254604 14740654 127029202 695465529 896662169 109693013 405067882 159658818 240864033 296590016 781957352 31451056 393020558 471968706 937977690 137082580 717680320 317892297 396030619 663699566 770612476 415036888 629460684 552460962 600105875 72445570 165082017 298129014 511356854 110778503 887093368 521546594 668517621 151089915 793922903 399413424 526731670 127952832 689760654 732955604 993367313 481337774 616719825 271238424 495719426 814285773 823247399 121878504 165083105 70080530 75636852 186380144 821606306 603441136 912931297 299922895 790239786 654923646 751137853 183169309 618101177 261304501 686293818 364841327 393754847 189569086 416927788 127461346 222210727 58055460 709211925 445425122 963995982 615242919 658234234 165105408 323381231 738917364 828289668 317276373 673195451 505993786 736046601 261484772 337920199 150029812 352721409 506606095 942018283 31885615 782624850 548918172 712610744 425964775 833701164 82225200 712921135 480351892 780167094 18726413 352101688 385874387 899946895 142224649 693162977 393804245 862504306 101367057 478824303 310533598 700081402 436796033 633155291 123599590 683455674 678756992 752318597 182253779 702197376 90172441 604381452 234280151 283210427 722764261 986986519 159381403 530157159 278879842 368249323 182445856 714721131 407494402 741236888 275670035 317860126 295505385 327402862 51313748 223626087 71641503 476318378 80621776 341514432 158715608 237000636 378804835 846084200 545122301 962799879 21543806 22291414 397799993 930480716 262435167 726297166 321147198 346657138 62397100 934861566 205578244 316697523 28263872 769415916 12501001 109473060 648775723 836574120 147641107 206985040 33924966 680846329 358099444 575951662 545974207 729173209 22307231 783622968 413868079 507717506 280996834 515384211 91005853 662636454 183795214 616862659 62709184 391907106 391049068 675984402 242592267 513653873 279218234 296016237 338428679 863230208 693573227 905990863 173106207 941458935 132166464 295854073 742876432 873640522 22384985 468458005 423930697 465036614 673665372 906696564 190669544 198116704 439262003 686171719 324867924 493774265 103820670 213375323 22726240 829824453 86945292 309041592 159534631 513132338 272837764 532761879 881135048 908697827 50343738 951952586 243926860 958583752 42137419 211765107 391417908 609854400 222259781 255943217 68169879 653714441 137196 150631946 533295499 691797069 487806751 582548692 71059835 250082918 406061929 779762318 687079419 810483724 142850593 505578688 204388497 329478696 209484379 359380009 444557005 991148723 552754775 965901844 447982148 842714777 147715112 710818944 423135218 452531628 33544114 233404662 318059099 720787995 848810083 899971851 205549125 649344039 31264278 176748667 635007793 863625904 357911740 924992393 88574327 305660474 424309432 623112035 700390688 747123193 282558409 698703800 29967462 785957802 120621014 520470007 439822256 850449576 152878796 330136702 21900800 56897249 623244655 695679473 130306493 859594587 302880835 949894833 12598547 153921806 535664373 800509840 358349846 965672947 144504164 646352957 320816574 820757856 611118579 631906338 607429956 890866582 143538857 356473872 514933853 602703560 78289962 205070926 425028999 732818139 9816680 894222106 588702753 926563050 882519300 896472135 657103385 752599306 201876522 623026000 166676641 840697911 342053987 781382143 67669346 664657596 385293783 461403914 33767732 501270125 19512184 778379979 491978304 861714075 540069660 917178670 720152933 980168867 374540979 891248814 398297690 983033425 469567353 894454926 156580427 270220984 378284151 935606710 225117970 538933255 40344424 666366319 336970439 410752554 397716719 622483980 788532732 914071466 162108324 840792848 470746086 749615190 380463788 802449752 253535724 436969153 231691098 428117907 815850460 830873289 146541013 432400884 23459111 592407845 314744119 409919178 246552519 265966891 226836828 692028458 154332463 172455593 180936521 595505837 101556654 534941330 180514909 307176292 562009360 880721383 38824451 950205814 180321197 899317917 11107182 866421296 237251135 780230288 86839476 316049054 882366695 902380838 196804679 661837271 151235392 678452516 297168818 956096656 61649345 878844824 229750003 423609954 119437540 441967001 375945529 619969802 64694991 894531960 39789016 972263223 122542686 638115319 61414841 610244036 408309400 710455286 857293065 902873141 62809202 182590604 254737846 683513035 269630693 917640077 221681943 290488464 285513926 505738583 562232994 961613876 367838154 886009085 229175395 400835525 513616324 923796359 345474683 355425613 300090793 385987001 855376741 983194630 12971615 508284855 344671775 753695102 795413468 928943904 430809774 728189319 574013688 594744041 289434698 506430716 229531928 445600175 375152755 909322995 138613458 981103302 542642687 673437840 659839091 787875236 285012388 915499769 482846162 912802891 12014104 42185962 60235212 769852660 48937773 490086051 314549402 816591007 425070373 978050092 417633635 986958171 168813616 869782703 323216552 577787240 385890936 794043275 92934711 312322760 75526754 980079193 436353578 440685394 123452306 441419023 614571189 631577706 25097698 628323079 265495009 448631840 604891544 904757953 427341195 712090877 270826903 562241929 108215443 899209591 474647162 958659249 55559142 257538982 101159773 161830925 391410436 910596835 835837386 899231130 34775488 651449301 659555963 981715625 322908096 413967940 83970002 957063724 399856633 876941281 408471649 577059325 299065860 891536663 554595350 991291384 177381087 642564418 795885617 799546399 74160640 579966466 278031692 284973299 214391026 249289478 484249869 936168403 698236924 783024633 290516939 636537083 294910238 835783779 171680126 473573817 109728897 422883857 168603916 731536279 624263970 819605282 37884840 272317618 232603906 818914118 708603957 836202651 75581369 875079940 74274710 364843004 89026387 900061923 574514505 920753749 197615604 423576785 293977641 895796097 783762039 856230528 772408479 843065016 518686930 831356841 135903122 487934020 265803689 316126605 21725171 629497094 955555715 993813588 91757878 623985947 39919833 79124609 156520413 196670038 541627464 893441133 369909518 513228657 24284182 197014325 287476210 381574710 389349743 751458975 125728296 840901986 180631747 560502233 102914963 872820186 486742857 859884134 613864295 854097792 3941487 705832835 78552209 254643335 391613593 662008086 507765717 535916850 563355149 670028864 301177921 969743001 182582006 960812876 309638169 918819341 32242 194586261 556694338 971573088 293362331 674830512 496188628 831431224 531747071 531840427 3543803 3610115 548980538 899697893 541292658 654746570 173683665 204339924 327056017 706648530 377042081 483788793 115073580 738687097 990756404 999009680 138758189 823931204 144552815 462978324 436806725 812053062 481726524 712223893 379572699 755233857 97617344 921992139 25072488 29492083 542799795 567111825 674133026 718977240 594084629 690994412 369381823 465507049 117666641 906020273 9997666 463513798 146722071 611430229 101686649 674025431 175923718 465911177 795739137 896634580 71158062 147213081 415591129 706633969 351455765 447766566 618325263 651094103 592506187 910272564 547906167 568814379 487991621 939970511 285053763 529097494 79591594 175546602 89126125 488663985 122569283 256298213 50635794 794591467 485982501 698882369 488441409 822774176 399943995 966616264 268822505 877741616 202564235 278664329 730970169 999032994 256924892 913366122 227299144 356882871 261709794 278110809 103259844 925189743 143451611 426883587 357270839 704742765 51205931 511552584 810885654 858634683 66591446 276538041 108160435 625150027 310838756 415744358 9439414 144940928 118475072 242230041 121187963 335505356 581632599 778958949 201232310 512724331 732226615 903653804 62047878 405117013 413766894 670586076 746845219 868052375 192138629 831329913 173593227 946343605 69927901 320200671 55625529 84744249 203852959 949260796 112560166 605656277 432359489 954929114 507909894 961279017 66881407 429778151 190328264 261897840 572472475 882158434 18421218 432344922 291709090 790869073 51247850 828956780 305805957 898424510 211048549 674740906 9090868 823388369 545608041 894412400 181974988 771491086 298655530 893424192 229160711 549363536 354748905 801635817 384385347 415174012 509359870 630409164 190210942 689963556 677534998 709336515 235138413 876116808 627795568 989769201 283053986 874615657 268008684 645720910 301910002 548032316 474344000 978930502 162067610 260723341 179676047 183840926 871184156 943937896 47017372 646931268 289935714 717963809 150045838 345633778 385574171 980031735 173133700 776492208 77671728 428923971 229370428 745120573 199969327 266021887 26166867 339852840 747228268 808503653 96459060 842518268 215418539 756862549 715981362 976293627 78802798 719491308 358886624 681167436 302240907 468940263 110990813 798039997 291650194 869297451 371906131 982761006 157492010 521309647 700595961 931160553 358190166 560218395 412585290 465535050 129305324 936139974 259521891 814886753 55912452 820269086 183787031 339007746 231015049 559710665 705083205 799689857 312392913 677608984 292302239 448154393 54856357 453443621 183660755 543072404 231268442 958854783 29695363 464149606 209242858 706289328 86583094 597879275 51631796 797199909 385762888 929511793 639254828 970698630 290140922 291331845 164883051 238765340 337182240 599905479 680365911 988272190 92363623 198102745 462004525 862247845 207942075 801506170 165054651 391355339 192223046 882420288 16624934 55953554 652168281 879089850 722473281 748485707 576439441 982966545 269282605 948393628 329868404 524544238 63513775 307770077 609668897 800774358 276442220 504711040 265125157 874828952 267085493 910211949 344995899 947905088 666526092 682761794 196593036 706162153 591831240 849376983 2333123 567024165 195013922 688023793 25422163 857180115 702108419 921913487 397775927 641322289 656569608 906011194 132369767 578425672 45547738 978002341 403360131 996383345 59076771 943151809 72429467 810835985 789390321 941166050 277042803 999825751 862680773 963362230 155999650 291285259 29115427 924230133 528688254 540014308 309159875 508050931 177489195 636071198 726990979 797190700 13008563 326343123 150550279 390391462 741854484 963891822 335046697 840154293 390853062 971103395 270416822 808738441 496174508 940555826 551832308 880505432 108393807 650354979 543858604 739744746 233050096 237801982 168812464 300720358 266279143 873895183 9403281 938068854 476445456 943537045 76089442 446256345 879410451 951379345 391162857 820547271 161162424 464273601 328433268 438910491 162219910 165494216 244623950 460920909 89763705 676265622 110986755 936231272 55695075 333458117 117150855 827300440 165043549 267223819 357362343 892119255 851090526 924263898 710726113 942480853 176933851 510371119 48823488 847726210 476021140 668969187 591099377 977081377 116383200 235305477 225306246 954895740 561510888 656853778 230873232 356296716 501128582 903528988 131267562 709646329 252739422 930966905 17677697 168794988 191717000 722399236 243982217 423642764 95633031 161448362 219334768 255996459 370088493 443361581 636425322 902996659 267932735 601987927 92455480 221261696 41492436 784941804 66355035 890443902 430198263 910746804 44076237 947950556 20638614 146947836 286665893 816958871 61754043 714307918 822899990 912123287 165983292 859811390 306223066 480547954 105010649 626560042 210903347 885252228 337136063 460944087 106527619 809232592 213939883 728030701 95286042 457276492 199208118 346470708 4236985 297163111 279105500 383145041 336746500 816421537 934329526 941582007 927220325 993668231 133972450 610179242 613623401 866601639 428828619 683084022 347745443 474265768 91756886 603226270 46121203 289767621 465651379 742613926 119525904 284376088 94328004 466687918 241987694 516069570 430243734 623583569 493393893 910927993 191483332 956216017 386975284 553283053 769088198 996079335 188326652 614425130 132145519 486961521 96125265 438180797 300488001 740742728 134502737 253138687 159407597 893772978 215618931 912175373 149403675 824148799 298259521 898362052 305217048 438695616 834098345 884723931 30304148 370206746 215458187 291501311 713677778 721308629 203524117 765522342 171618971 925048347 233563396 752519795 273511451 496792391 151919493 755193151 1448072 435203180 602420530 880164763 485132572 986689254 482736297 959758279 452610334 828307092 164778994 275745382 127996367 831040227 2748485 464831057 603731081 834981657 292305042 656628024 180270507 582169414 39398108 509973694 79145576 840299095 217243244 432443822 66005854 123507764 49983583 161697280 467617019 922306608 720602754 806966450 36657725 514864867 564329378 709270537 534937236 990905741 134177795 139834578 685891728 856090357 290845567 790356566 261735170 372969169 411264647 704035477 407338466 469394315 636284227 673827214 161300323 945866749 808860259 829261002 317678963 638942561 425276286 494487004 477745707 770594616 14674212 232158284 151429496 704690815 221928737 796182460 76985000 740994716 208127954 299018898 724670452 874713720 850880051 939653041 523523328 775272995 368374655 960131207 30316815 639831296 22431768 609372037 131539511 772455456 66104884 943368530 564601155 585784195 386744240 412049620 80956618 540999980 194621034 338124526 503123034 859789736 202198792 790113920 328237964 507581697 566407041 941432069 102329561 997505410 661205185 759796456 139125881 664696811 593352596 894837841 514497479 828210979 131770604 442253838 173339535 315221258 300484237 529167853 314234084 895797778 330477663 496144015 349434940 578372611 36213995 171231106 446628014 893297304 16314956 92920549 239838998 997565819 161768149 573731048 550505536 586280194 54113054 647257557 108556778 707294086 39459644 564216037 19143157 253862531 544279421 569269219 316793157 712701823 40729227 287187647 15537157 303236272 151294980 217502124 17330570 107550736 333220374 981300165 414831483 813001486 45333987 801399550 257566669 300871399 740043567 954070569 440992157 871258596 514216722 975996816 669709676 947142360 598012249 826753423 44322679 680353408 124326284 502426031 288881138 733048134 619782367 746808671 613739448 726199111 713702985 974408751 713845903 927994531 236640239 426395913 537581518 750405358 4538616 767318909 492891724 496134574 70275526 584642221 20278268 258757315 167572243 190952291 367042405 606073341 197290862 328951887 289920946 940303329 180417947 912288641 411823575 595426735 301176299 443550686 215370255 645495614 400282855 900731461 90983588 635300185 14579932 338592882 206703163 240247076 284793421 313182453 1392537 152930326 897029442 936430605 199947492 589161182 185133222 391730429 255715817 321962507 323517792 497433016 87251481 158962486 360718105 874194820 563394509 652663348 224944461 964740523 131054097 806226402 606315337 905992516 370348229 799700310 136573019 924152565 401018860 557455696 346169741 881468221 215757894 353278399 42876670 595692182 100622195 705943675 620905676 876098316 689530009 734711886 146326075 200562110 117156375 147168766 137799694 461664556 341339435 808172200 132071884 622838206 415205552 711228648 200608187 605655542 588779931 851582167 112906262 744258494 215270402 947458368 69886616 989638311 58521635 252080052 159468469 396962176 597773231 993335788 709119172 981652946 187366738 196550320 282554543 847781767 241027964 351341668 111883529 590354426 136329793 881857201 218558458 928241344 223562460 768335187 844737936 871053419 158308222 957550610 56379978 610261881 137634904 189661833 63623076 444950343 83548090 494173618 7238364 223310434 17964406 127705613 564809486 939117328 51406951 765552140 126940064 361322993 296219660 980447725 294252786 846268646 72364325 435796834 608017415 671795524 145508916 742120995 607967810 974663296 22635880 823338330 212331337 738350892 342134466 960587115 338124755 723546863 290408791 796453200 314633549 396822483 276130286 668557263 131973605 803733527 379205734 457053664 37501335 395216693 92465289 157604888 346741157 506322841 512224692 855872093 145875139 844993643 492730116 992380683 267566270 626977676 203919214 549651976 54967990 456964830 148372862 951393126 784363441 909508355 109852529 470350209 291056167 721507819 626256359 901852217 206424280 638707851 329260296 420019439 256853872 453502013 198165263 874103891 324117262 403496701 202662558 408680653 314781140 742874223 252953023 620827404 576901808 732980829 69910001 176826191 426240006 994290661 258825884 306165222 72478090 393186345 169603913 543720373 229427391 270007093 193577725 288003598 813654697 978604766 370072627 715933548 105327990 262859573 52664335 386097317 48251867 571418438 344905354 386349197 54997912 853038594 401303249 933566389 762406637 886251075 595145282 934352638 279674590 517162787 162698674 322611830 382553611 633829032 308210876 841235545 482991165 495680021 167873404 868942161 169489075 826785172 404092641 495803582 48307179 211387219 26421260 681429531 444146130 918193362 33819698 40484325 100841871 662332611 165287931 292202665 423052191 556364861 109898495 911949099 200574814 222616599 326904301 711082188 229488114 321727200 299563083 547718797 73511855 751940898 101052758 976665798 47180781 285900107 50553434 975444269 645303396 981604485 16616956 327150051 576623993 971021689 809072022 851560235 556141801 808066760 626752650 966910641 164396927 589950727 205785905 667255645 38460025 193016361 746699544 875250824 481672314 754995662 426404667 689561278 82833681 918447438 180913161 894380083 356104026 631565056 8941964 647907451 388979485 913873821 154866037 559412730 514063993 646797951 267182198 441901652 447201916 947970662 54998410 955179926 592219757 659190241 105107626 710161395 226397007 261572688 676737458 997044293 162793229 168653846 510262161 659749724 508802620 754568497 191736726 435607391 29557626 130632502 332560835 834976816 670852398 757862729 289453788 811456437 241574349 602020451 203208232 958632789 131372702 331526280 683417408 939752847 129297808 482915213 525988102 797340629 859265767 942499187 480016841 739023459 57234248 376035159 154238183 314246195 419772884 766441878 222477504 469365524 108494902 940861328 520660755 916007000 359875006 634426673 116254721 534513221 90867719 703583815 363721125 557363370 866704653 986106143 333950298 697305691 722422272 893055688 562565427 761224956 279181755 429507687 666554519 920010925 189689120 809152884 42930789 386936199 482082110 887975733 137406503 310396674 294693890 568985287 17278313 623804728 61763644 471930100 472319780 681733203 13177396 139184635 99219081 560274483 13237343 579381721 23563036 825024056 48338574 506621854 12928721 108342910 60136210 395726924 386946935 791268178 66979401 542293195 187166563 843430852 287100469 798416339 264612942 367983023 611697234 647581809 450818652 877109818 739897354 836835208 282353207 714640945 180816560 579999882 139235659 868272930 576138740 850716894 60166191 113880744 500785721 873076355 152893320 707891209 428479513 800170753 325917143 445136440 250342986 429493164 389418381 714916192 57864620 67183453 364022543 660646825 71242932 91180041 53865485 926878433 515758540 903397241 55998358 306966551 472409350 790660176 1719371 106505770 364238692 404715536 5195393 972889770 84777900 711844368 161416509 904541092 161049036 924986851 443618603 710104057 60585302 342400394 73478146 757721619 444857442 815953309 283255530 882559860 191073082 472584097 34930276 793068936 370218152 458958686 174952841 863175952 156756927 804670607 638951410 824873260 574755377 585308278 833222417 894422568 631259916 722021861 414291659 958947974 16259432 784389852 44616661 433343112 373106013 961135796 602056766 791081836 685856422 987817965 478077770 971432234 149865510 807609917 255416321 271796548 735513822 877466057 207330792 970915398 263683189 484534972 210043731 279279009 97075425 523181253 518149070 572015997 170043782 213546094 483468273 727660723 442689520 732170895 338248617 378130623 236647450 268500691 395203760 541912139 1961507 87036945 126787009 932491093 654639438 828399299 188238937 630505349 574071675 951161648 53936662 534838017 515744720 577758696 67466142 368397984 778214050 813145171 294530432 625885252 221713751 664094329 307847608 699206860 208386104 401918073 729775824 745926465 218868377 648123174 248384968 448829806 280299124 424074945 10250207 788772006 376760737 693039801 306045215 670894794 552015883 861725390 798057434 860712403 119023581 381896942 552088267 839782456 247632624 754787011 168171553 817716899 620836554 987521223 350576660 894366987 28142999 519562195 162198961 281319356 114536788 159100109 300311200 670733268 13541708 605428232 765001251 772063123 331794078 502477429 15722681 265303872 220788084 420575397 323094394 482441651 478975248 649352724 156723616 687730973 289778442 850928622 635213839 760037924 165648957 189759990 226048528 735994894 131835183 383343510 138003862 642881860 148135193 261471754 149617295 415763197 132098835 428184354 15623236 622955451 511087162 619267741 69027018 263315391 169333098 622980484 224792943 276828973 388083478 653585890 273958503 673546096 711122423 734567907 403989164 429989607 110392927 762944462 892323795 938265586 85369161 324392507 86890404 394150627 288310974 847398438 44451230 284386846 352137074 890876093 116132438 922785477 289875888 415039966 179531097 587632189 451752059 530078087 338776434 655027290 873308861 916486949 89128620 144152389 230270531 780987331 45542097 116366925 64472017 919490794 301908036 420686895 193495289 977176135 171910029 780137954 147011983 284027194 542306904 546216460 170321678 600889020 588746572 591951761 148529255 208401242 861893 99375598 185312211 690037566 690617727 835653303 583133517 912183089 694105385 874956656 390598379 936060236 197754426 670855613 46240728 936994308 507725033 515826812 842558158 906611550 313318927 563842570 100625858 349327581 139650512 242793568 816563285 917634336 26475273 258535599 275987125 814400942 37115681 137288289 219804622 438141703 692980955 850560880 110854470 618252295 78040848 736276098 198390315 916023900 229994509 761743018 808737585 984828065 390616180 814472344 89039859 588203881 280730666 965152685 177750 124923423 244851608 347443665 180630881 772310227 136007987 729404157 183688174 271319183 749724124 862438665 765372051 850687954 128802896 267368484 82398655 575103395 18633582 989559326 26527632 477403302 104646277 322491793 618037976 997298749 149661844 510559372 111775199 933163112 277404833 933883543 283938146 920038043 245951976 560778467 126924844 234187386 132569882 186867142 223724948 858351255 510129953 643799492 641773428 659390128 4004916 257029761 81100521 271849983 660698074 896203723 842776792 966445873 13089371 608743309 21258929 439932114 142046755 762106342 255034585 427648687 74363473 430128879 176343394 918705936 254153970 794960080 177469451 994288065 300123360 787672275 3020759 216618479 220059175 452228166 435086507 612322191 370213084 762433162 561454348 567002736 58455098 263384265 757992106 971459762 248861396 342555505 306741713 561706659 40245414 422722021 248810597 479362689 107092628 962537984 309546323 770388614 276585511 473086055 994069 43610459 176340100 294565743 615961710 647455323 13146394 646449133 99685329 470084466 387310629 790959700 250649922 709523551 575990697 697703598 202542570 377593214 172344660 745296507 221307919 326824656 138303402 805698908 251356894 870572510 92022871 116603426 134489350 168905890 595557545 828563436 587905803 645430499 620227458 926373273 41008240 240171333 73126303 246558768 716868464 756521212 15298401 315655300 258255974 278650379 810093725 969189821 46170072 152370431 609718869 821575322 222798191 561096797 87275046 731211752 273744271 781615393 551494118 943697160 260854901 612768576 171642018 646784072 159872397 914710240 398707139 911121239 733684726 774743319 81308890 827030474 424091689 953064564 480993399 743783970 496940413 525879800 625513460 869679929 370298314 451108598 415166016 682043980 472921618 590562420 40676879 170794124 90985305 958482910 157326065 793873497 545183268 704361809 224894388 501481383 207568585 809669025 744603376 783354444 348448664 962475925 219881180 498743132 603491920 964207885 133470878 217555915 795415031 921859815 10150016 922808232 793858583 974799562 429035121 872915758 147846655 717471718 328293218 843103435 190003175 983180421 86930292 663106572 109594352 842221481 12357889 648765320 90697890 196328565 377006010 404243978 649777854 778224410 101813849 799355496 515178342 727130017 30491101 104948593 302013482 381756056 137840576 839982086 646753740 953299017 178602519 698295298 160665061 708571031 359129942 736085298 621477241 716939493 145468857 578010197 175171990 522276370 30168432 327056192 352458978 925908304 942527164 989548827 830895291 866196386 481829280 796715851 181675548 243965138 267759118 871407390 657032729 750219501 88620926 422578844 293637698 929262018 215527224 520942109 287359069 945588846 91480884 207049055 150486147 323605149 259959146 551907317 471773452 681081241 492348828 711878954 427371756 946790193 352361343 553421253 120968772 166127044 413207992 536558291 163081009 325678890 215625759 876800617 605769645 853245881 536492668 920107435 108563477 127837600 40867200 513823753 283792463 518600825 65679570 659223684 209055529 906800924 241624440 528164135 89439475 691724570 18448502 80808506 550725910 668239122 419167292 553781619 14378302 985860185 8020233 726751687 437554290 652864584 26221565 572210650 194030134 423160200 803456681 838954717 91227811 410785957 350616112 678460241 129974474 754608486 298439429 819772816 524629529 555509445 562101613 640176011 603900240 792954982 736730723 800237626 142583487 589070998 4045324 58332567 235690636 967871283 127905827 569305677 451843266 586514186 361164502 604477078 512989128 590396809 575602431 808186716 116781050 515968574 243035464 428781882 20121747 63229325 226538937 918061231 622661944 750239082 219092849 828284043 281006093 480848404 632257689 913048066 28967462 92127546 14586373 252921966 684652146 865879505 511319819 960893407 218505887 438349889 36354518 376879432 762210512 818976252 77957418 553979483 383825355 745081713 221510150 310423008 208884492 665441198 59280666 435542890 338130811 495691882 48709326 253174343 95577201 239397982 439920912 843633537 594125986 607225723 111051377 281529738 86640462 385819112 745957985 983336525 301547516 814233327 289954416 577085609 59311851 586693331 98474740 136633837 241316875 724433160 77314778 765114131 70919131 415996059 602147966 660471877 85699296 387174093 326966677 633066782 407259617 551119396 496518425 565992089 283338559 716835763 298339856 359690692 422559963 946574784 347567574 434335804 328803867 734254288 55951767 561898322 142770267 706711611 523189310 868988106 56557918 614104307 84306659 378774716 720925919 764469949 782610654 857862576 268798756 670733420 109151708 333922357 234606429 610923908 808382110 962325275 451537568 852809438 809645300 834899205 298858770 549279974 385481497 618080881 31373546 821220015 924520598 952947501 468214063 594729282 786291694 897532557 202442291 841609666 6366565 333732454 574695168 848844215 26491447 509115691 452135438 814290549 113696650 519224358 349809117 670938357 35728154 744122193 178745060 755809059 323035029 334507829 467608499 817119908 22808776 560323541 432675143 808714375 29798759 343024776 178929740 330098093 118141546 537954746 263867669 421201873 546114190 803397725 480670370 555181591 415135263 835567795 526337505 963446272 213126459 692132641 471227497 707091913 549107538 960660407 107847372 847024965 405083159 830404906 339286255 569319188 357213371 374270028 11373211 250541820 141511713 957012858 83604293 151322580 270130733 941473874 418979047 672400262 35319919 82517443 91323130 532989625 56539204 933068709 90354194 244191364 116040540 136745795 19496073 609325873 162169608 837552038 141799205 910682564 245861760 325731449 215916511 237262221 66555476 231108201 219800019 492326051 668827168 820599621 215434396 835371252 135577587 175657426 774542317 795247650 378117138 481217873 129017483 206718160 470637058 877904537 92114140 594267491 99298021 403838883 247479118 648794666 347533396 829189744 384337280 935426183 120733878 279524010 234670753 358651855 487195425 511144223 476311528 821931712 9894657 735869104 270650931 576772118 501614212 661931467 952696849 985042105 673593705 943837002 474046070 497429184 213663040 781722192 481728874 918772196 593351020 673650828 255748613 734067768 74935755 878583973 368503348 880207676 45103286 153086028 266582111 286171382 44875213 414150495 216178110 636193015 48427565 471099746 436456426 892103071 474034094 500169257 190977568 440645860 729126171 740312927 561329766 712660887 26930701 777801738 587722657 996432898 14458697 70647811 491678837 760109518 858906681 976730938 373665447 433132397 89960219 114348265 523682290 836259751 257429568 828946005 302446782 340009411 155364052 555138460 70560739 297007126 250412531 901243078 201405325 760346743 140751212 238762841 130543861 316780834 32352134 41273629 616350597 741071061 39333002 329209479 397256157 580420425 150711799 622566513 179038579 942448658 6108823 574076597 618603546 840629013 64450378 140849406 68759219 684247391 214934783 434290660 87449302 100828944 647574950 650672644 270627999 608371077 353316401 764737039 928742701 976551857 302972618 661439237 52417413 144948999 152999375 962781343 483945771 903516004 46661896 839299322 98483134 296567769 364728254 973427107 385038563 664687557 88633916 277573630