24603
459768883 246084052 439771799 891122149 743564050 598361280 492831758 955063940 484724984 540104841 162927858 724475895 442395246 611805838 436549488 296693621 85978515 120883805 515014773 559395127 237852333 345691194 75081493 928856247 972468483 507242247 77263378 554804511 384187154 768828302 170358975 459812343 785107031 277176147 386203730 724216043 992503785 723081162 708513032 935088549 419991016 808170070 505851046 577062476 836002653 469700985 806442211 840932927 964792794 61008313 224947781 211708001 866848411 235077706 16156596 112833666 808103809 57993918 578549307 318306395 62770095 902904964 193644945 755060567 985154623 73574074 635870919 408025427 834692957 631891707 817299518 945934721 998118887 461148044 454268751 717354070 255356360 634774118 862921014 29407219 51500647 806054707 834590597 749408568 196156850 929342717 210162665 239801055 978217295 429061631 620889018 959184909 441759696 773134961 328165350 515632463 495974283 244559597 941545698 624027334 578853877 820717142 29214155 425521057 966517197 441201486 708074090 903597107 673224450 348969640 87877615 666182257 146301487 941267551 309488456 581738075 650742305 211316072 430793547 661113504 817534483 702462923 299156923 537519151 352321407 329234003 908189504 721462056 34200683 686353518 688171936 433920653 73076078 80765058 824605978 503869597 18812832 904810037 619331596 661648380 154571812 334654972 578560166 553223845 970818039 400625552 982078801 135686196 303038287 479537019 480707619 690295419 864353698 840793269 49751014 648871062 744875223 818837398 62140500 269449929 283363291 417082920 210842915 563659335 94523914 96508132 378500619 172302509 245624595 393472164 660781899 843519650 808725066 391391539 462617267 195288430 101370457 355651362 39744155 995460586 393474516 249984434 942802248 940341775 722896710 234967219 930285975 312035786 633038225 482626528 235432713 351911541 204391316 768903933 652734381 442025462 6390531 348930899 349909645 994900548 849615490 122854602 167823262 376701182 612025496 315999617 69165865 912200061 42902409 925165423 312807683 233626428 852353876 337708478 382885583 85700132 469675759 203789138 47499936 688710441 368605246 924315451 792036860 583986041 432621171 582604914 44298241 826362734 977284830 709416975 949144586 411458399 768959639 17595164 398111400 942369617 100523706 747027336 849445418 26727609 301339209 691676956 316369991 434322777 363090789 26956754 674296874 35216914 759803369 580838606 254241267 781167341 646384731 299149014 555249686 919509323 176704788 435858826 980001443 88733160 124533195 688547161 851036759 877221359 449676487 479435017 616734705 421779715 413360659 628720496 401961059 683279479 277570113 396503379 773877684 811871250 918717141 932028574 927542837 158412704 672793147 332037975 733526109 630136997 883674813 172505783 721765703 721083905 785612329 305617079 943510150 273710292 65661822 59375292 690285479 869944801 497441556 32541607 60122628 88838884 544492137 173870169 807477454 503332532 172019672 264913965 613330511 669063180 258891011 680122775 554349218 303302152 589145076 8972118 230673364 986230921 75593629 348540574 223266834 603233611 66013062 141533440 561919577 905761472 826011004 497028242 7893020 893426951 804873151 604105184 102888357 319316689 149288036 185946866 656196186 191839805 433272657 914190863 848909604 291223738 460584256 710477055 871772288 482457688 346932296 777461120 306749841 282341000 81394664 197838790 621638142 159436026 716895614 867504780 352665211 595167246 685645228 184667340 20510721 191306657 248337842 351355994 28158632 375395123 584781025 339662044 519335523 648597993 858430857 158706870 843528632 527644350 205286705 378082652 207874868 86526737 672425491 547864865 203965415 292592432 341785938 894143138 794473546 146658364 747635945 261088238 359543203 108215077 711709823 101854352 789173430 869609242 552526025 141734983 285639201 421736378 692558605 98773879 748573712 534861143 182718437 347904661 105500598 31132908 343080615 594016213 988504526 70412174 258284577 936069702 336752665 25940772 189840861 464191056 515457640 479707639 915433115 961767810 767939012 776180476 184800762 388916208 712950823 580399197 149820477 817799868 857474899 701163396 930216536 331062676 35313191 687202238 639830686 188736879 997623769 189626669 439339895 393695097 70202824 636157550 254667865 487005616 80583510 335897915 580509763 318098958 642175540 608329023 183532132 929928373 256425100 69992911 846974778 955511771 826778332 540832653 126709486 757239545 531107233 194848384 985584239 877814630 722193754 667050267 44625660 387491297 748647960 937236889 394827034 609832281 128792171 774463260 424020995 659325524 384238357 218609414 921523012 678763678 572132913 652320447 610196199 425986894 726713075 725688002 332821116 819568790 855463697 599510157 410675221 100828801 552645072 381831598 147597089 679332466 58118127 296768526 227211707 867250602 742957721 113668052 52314644 890297821 734852560 734820238 294907801 858659000 148836293 660928801 857189353 32708662 475149371 600236402 92607666 669542125 448178092 516982106 31424406 525774634 240731233 544862402 959335205 494905642 697750279 37924570 557124916 625873515 263131140 983816657 207834137 522536861 23764526 936475902 73332359 87587034 511471490 699176326 218568491 192842924 583355842 381203984 22164484 464026076 687329815 806142106 772929381 737333166 611787864 331019290 408646497 156122160 530078225 320717427 173716382 55867293 331699801 595335108 558278657 744525203 654913569 624972252 55346531 260244791 321760215 918673166 803531271 541680234 670537279 317167009 298565301 383679794 975672064 962221384 497411401 380145217 176220769 621140561 586097836 412160699 864480403 714624684 260070173 98691665 529196988 699151311 930125872 190862626 410186557 317102947 976822888 161496192 957746590 418674476 562457759 517806801 473794799 7270337 6728420 934122221 527620529 807050554 44437315 438119486 621887743 30822353 863746952 989622844 766075958 235481934 800376055 879368129 366466757 78517216 891198989 582307686 216443060 919345386 256488573 932364227 664470559 62310707 81499863 2623352 448458132 369588234 567494203 829781826 181955322 962661160 547386011 949320517 660937263 240160808 245198397 854875459 146861130 294529147 850569363 209893516 203493790 851174545 362313262 344124677 660031170 149258007 966688107 620678567 218906680 935700481 726027481 307173684 461652156 625543268 759638011 904084041 798234748 668947043 431687315 692696492 523672741 82897209 897672333 198107895 533081030 61802307 53626438 134472007 290806765 821282650 848197267 57483569 379239558 83496904 636020391 901877017 148537539 94865159 242627651 636917789 791917389 643516631 96098701 979937249 112307899 317817714 396023077 184514945 173103997 189829947 829728140 183217110 946713291 712594425 72257934 450787762 824554835 689898037 109436390 893262598 341880249 920783621 502830177 201461800 679692606 188514150 514002798 612398789 147130037 307481942 321848250 291433181 701526752 604146505 300194978 230173310 427381714 830137197 241486231 247108434 449328245 644960457 521363528 251654911 709281606 927378210 696337941 558854918 552438974 89781411 315050407 915794526 958259461 56635515 962623622 524069191 621895293 674386043 763333963 594244962 47775663 759774515 979198261 289031321 298230303 729566872 742967252 253658594 530062285 999682173 724385197 282244049 884068218 955671034 664384805 719376091 173402893 654388561 11569226 789749591 734664909 555132732 637878945 699185829 960136524 785696817 269650690 469846775 337923965 284812479 374256786 365641537 367827661 670179282 360553283 877050311 577611982 234269198 565197281 809855050 503285852 77053397 273005085 324177973 648604640 731690086 249998507 357277934 611585141 410356319 913738574 120655298 172833134 411588951 924499483 36890685 2711232 428378602 110988623 853509536 109184383 382408795 990696473 528597991 847229887 378539753 49640870 311160999 328385337 80961434 408322363 895446555 963256237 857813004 766416746 705238563 531979769 47950556 225317749 784652941 257040657 23758987 195976360 398287977 629843031 947243109 763644235 174269706 390527764 445985185 561485590 419121551 890019029 241291400 770540553 163664388 27139630 767140889 397594549 366722634 56993375 868418520 888217476 909339521 637596984 692358654 158466347 836654116 363548179 397385137 82259778 632006826 681389193 522476352 883924855 809088163 790489460 503194535 695465578 530657737 943730023 684482320 414473577 439706602 537246940 669647482 238844830 369305800 647579297 379083649 968504744 488131818 734261102 77958034 691545141 764272726 591964913 858449327 62950649 709929040 242734291 965546021 177617117 378238605 156935853 445791943 728017353 983256994 129353682 697785137 672775341 648600658 846568008 373458222 749345723 939100038 649681273 958084210 188085458 995624092 186318226 603192581 771108320 284234347 214312896 378209469 219077756 521630206 235300611 847533584 537003707 744479715 957144125 48006798 649137371 755074381 719840860 521957226 379721764 288433366 444908167 899800683 741763621 179620233 662737670 960510629 434215143 926095349 120155303 557800895 355302322 750079936 282451635 927122581 302780776 471349094 245884869 241176455 519815161 651721986 111416384 666785298 651377 250447114 538281443 873655386 842198504 220921381 558420750 644102310 617112987 154751518 366482085 441623738 418760128 329569258 633557336 650215924 319364182 704689912 68545077 442299962 959981741 929215453 124249523 634400225 474957234 72616554 199626481 562367164 340780051 150601173 355210752 346702610 303870653 471827687 267941096 555567686 191064439 124063160 827576998 421046700 595747252 495950360 21867734 8980136 706665585 829167800 54410587 662606383 598858621 595544999 117620000 135685905 765537418 581025135 233958193 861072282 784847552 143528366 44400886 371137928 839573794 734927494 156287602 191885298 148541327 310882227 583472274 419535037 909485276 252664989 14056995 915532209 896751275 279698034 941524208 93962969 131071172 642939592 659311023 696924705 324876533 745387774 949287198 550443264 536568787 193718374 396311190 817912712 116608961 736096248 876912614 667027461 993324882 742370559 429556732 637683616 683891598 976596927 796630165 463591980 939634780 437927160 332962579 662664948 164970451 958096324 279788113 945502585 644324686 271589556 197215216 280733413 616630733 673890864 141326954 27020653 876297993 516761200 890125650 586310329 387213924 978048849 414298706 553506802 418535905 190923945 491534876 636249816 583792721 418459948 7011817 560175302 147733806 439484997 133377045 981078701 337404069 566077922 60208153 829779658 16761240 819027916 989256487 585286952 779947636 261183230 408090565 556737849 767035437 925181335 94036606 733257484 594998932 573900547 718588209 224904678 498028304 774635355 320568459 417321712 214323583 434758561 842683343 139102094 919828306 261803991 628433630 485239431 27138543 861838558 264866853 134585527 338430640 236137155 627619376 425487198 349790030 830613274 397291083 559055449 172731794 45604500 645309381 635924114 596608790 473408231 353855876 236399130 951296597 933836300 747161998 293476586 865066777 730974138 302584425 23247178 895517056 262566149 10036858 93417638 610994359 241696694 317502874 893636686 70856616 8641575 664374905 281217230 188023044 970894477 835643619 611200587 108437315 376841214 683176370 322184009 345203059 797168738 1803850 137237459 560810168 996172613 960750397 446159296 847037404 262580255 306035554 660156966 331288803 74728585 295562012 733294398 471514906 684190746 354954946 966388801 491100508 492158457 725277854 921737866 875621056 951422738 14948304 630973593 420728861 124325076 881774028 865682149 617951378 56706480 888128516 588564670 989626091 285487410 822124133 289437796 644307758 901060882 384685272 338390043 585997916 477849078 803129148 213231974 776125322 342058922 619166315 647528645 329271898 113514105 405645140 666129016 479531279 346280843 683437926 180594951 812914586 819848346 438165329 436366498 502820267 933015113 852043223 50361152 347610872 273472305 732808792 488331748 967364287 44477718 68362411 391888504 913696079 568979960 493325566 758543239 581609427 648119356 702607617 788436654 114764202 133895271 270495939 93679774 199211770 254906034 195971915 789145534 761564363 368724896 377759991 583748646 16087957 358483561 403844416 414354811 565945494 472156419 579782182 664304174 349897191 6178965 833903324 515473936 389030024 434558845 375735991 631399757 41540913 625619690 148041031 561035595 647386565 634468710 8692875 599048651 465616430 778989366 402121148 38552970 244042930 632553987 261986923 388372064 128832199 442105879 245699280 50036448 408958010 617936062 752956639 303909196 724911098 72361869 695641632 34382681 426625602 264149179 130367284 89172628 912802889 304489704 331242206 802907220 803202919 559977515 2834903 676361720 32464299 589016876 675837442 263142480 790444422 69902442 613934242 625645709 71652462 38648166 774985497 767033600 206892574 968750058 825385598 589464948 543889545 701035104 799200516 675334493 757602304 708265461 932722848 689353468 917384977 323955818 891328044 41043154 594913153 922585784 798957645 469462625 109968147 621596588 224901723 348094349 737599180 943518126 92259653 436988315 761608638 209732845 40292034 569938124 178403448 890405651 275383374 570118306 943678570 134375716 871036662 485720223 271053841 591092584 722546268 33830087 54847899 892080454 260882009 535366657 86700904 228467017 650944883 359139681 399812295 735431599 583279992 195903419 88095940 463739753 60175381 82543201 939808373 631189213 815532711 495394730 395007112 988337600 35190471 153633764 586377419 471614143 785542246 772876211 366042103 896132214 885720074 251912437 69723990 470967607 443374941 386051220 143679811 668855399 120133209 509987403 890021516 615373505 291477369 723250161 930734212 589230008 659832597 994541745 214031108 547223532 585861754 312844008 59143858 999250375 887412644 970279792 734691998 244740932 159078265 57288356 665432741 845850754 299018040 631590248 169706278 340355837 34079517 814176214 609207253 118889022 883996469 624431944 263933838 922984289 335294240 800121332 518720127 237702363 254888152 60396743 788924031 88643055 64520641 687298729 714086382 830138115 311620473 957165759 333066966 265871495 852416223 641285022 342869501 115818725 392095761 60517348 181350205 790654736 896973316 626831978 820455229 191598467 509149154 208502685 899613233 974403316 534561977 667025443 185749780 663004565 245881356 859233270 300232530 858954622 231909567 943568061 377292722 101931589 245052192 818515796 49880764 394363772 242633754 277110346 919538427 617648217 764847344 50961823 674263680 630009617 786104874 510585847 852537339 934590244 104304329 11708886 575297427 153975390 89944157 24343075 977532949 11967086 578375305 121672924 170751753 65765532 114633520 306603608 739400879 496858821 718771676 947969256 585044745 151311432 994898698 568908658 79503907 576038347 830634853 588872460 541057120 427648451 987301239 294765184 692942258 206762764 964147378 755147448 952253352 692870548 559361111 175704370 518689211 410983290 412087708 204719501 426287985 567017462 451415107 758983911 971796726 979064424 804618465 173816282 869295086 400866757 59272106 822630417 761215304 787046513 882779683 562478237 904513853 110407465 150110264 224591936 832951556 938614437 189310937 936739099 572173167 190460842 553435953 458250466 402449986 896305027 297183456 444863065 655181087 564020231 638708714 944373824 896940808 427243577 307388905 837388097 518057004 288350005 512348425 749606517 232199863 190370472 827285525 449847180 292112885 301593960 141934773 925042757 205498964 637586041 967781947 126490601 512333127 20030571 997719788 833144972 213205611 525466821 200822465 430642800 771334936 236063761 532365052 459131284 794394957 299376752 76305083 980090423 545648702 518695891 727054521 114912381 288855584 449851115 16397186 939993270 364766270 806845911 863398098 283636595 255680103 114899878 880123043 799547275 662616394 88644681 136011523 41938792 136854609 221627024 921705182 222228899 411859777 424874375 119702484 168303867 297798894 665591448 814942923 255716358 283181332 82733761 277380545 25604817 5832867 916286317 482365410 956169781 351876277 600777726 625222236 217691747 435469853 480732400 22164216 384606865 911269740 653816693 306600546 670304886 302051857 788379052 398229424 219441742 268975366 83417631 727972231 658321889 406793282 661977237 379423608 752885185 746668565 321291621 551537281 517225659 722847400 930248201 479959033 451924800 844234150 742699930 708085330 610057077 187284799 737710805 481670953 593992398 159212372 26482910 315296910 681627054 222829891 928472179 302579112 919886607 546013475 220041479 180561602 765792470 728557409 457280207 157214391 838296801 897345482 663418886 532053948 39714733 524604974 520908723 195492909 809403187 488648087 977498232 321073795 599783204 886730453 956166470 572417006 741223353 849213166 371675568 795877082 344824519 355276547 560003254 723470011 817780119 801314586 664656489 681671109 374582024 612895913 781741790 721476338 708888992 163261870 151115912 395661611 285423247 918510040 672518050 359432519 354294977 55288590 821472551 416666502 52767536 680933744 62989721 332933605 452014156 976409167 254646312 412442541 353601362 347711875 381406304 180289392 777660990 556898311 484367924 955765363 28169097 435025840 813487882 244389716 589560198 428390149 459832502 872249952 685147657 997790405 652523535 136933479 56519033 254848164 622160723 886114017 474246619 517757504 417600651 973950994 202694321 99001264 453426896 379190202 41340492 57716871 833966335 492853038 175571947 362804333 82943646 506992691 833269359 114309744 564612660 574410306 179515977 463785631 783135618 41393834 159272599 393537591 40803647 139505385 376206150 830561922 467017517 584147254 213454566 435083202 155634259 661436157 363057678 867074306 163817827 651241120 255642396 402216619 187168450 993033714 755596529 637449594 100871543 933670769 870554113 361242347 644924795 53776042 151131579 867035180 690118565 829958945 937287931 609896196 943655507 628839320 23113554 222400924 546519719 529900820 83548722 944825571 62053727 296051590 163565483 322441881 172801303 40078693 317382633 975171913 314977386 461413240 49170495 398613587 591211767 548160794 464676249 695975728 511832859 879559963 757148727 613834805 323284610 583057827 625697528 598279804 209828338 849265983 995124400 116352924 8981634 49166893 617235356 73970747 980011481 127569070 236815996 96371545 828603456 229787116 847286452 22277125 931898514 71007592 812415504 614063460 17183312 726874934 63341784 779762158 481399397 985806411 722407730 656128497 10639278 873117169 319131524 305229775 377309302 460711363 783177154 17907725 620180527 713294881 31202043 513380208 50991782 14801512 788511618 684015952 866942917 955344820 642942309 431185516 986434761 399737346 433433170 177639752 959749674 747565879 6133784 100413251 901133316 683438101 11432487 738616428 60065599 416664616 979841899 317764982 624451134 980588266 316239763 902026010 285218445 694937612 292639417 609474048 790597449 40316268 958486517 4549290 962791997 185874390 90586498 499386076 247962502 853166447 531597148 311569541 966215578 77999319 350520342 962862138 524421094 464566181 534079243 979313350 429951357 6608980 333398812 117800107 400777140 749915397 405931740 816544451 948190196 343381567 371044589 865115451 868325491 477568647 445482798 96300085 676175599 536468734 873688724 566234809 506481490 939695913 312624022 955518296 790359899 869798493 734886510 393061720 520811256 139133688 989980234 398115737 634405788 474990994 171573136 578099317 692710932 299608118 746293667 540502013 106068256 988120000 282077181 12834435 978871410 508904217 745101136 324698912 68514743 512164881 665600430 973652295 855505817 945879693 433892453 982482376 971615374 446229462 661992046 59908031 213546718 573098142 436201787 240415831 324692017 706536616 467819640 144612951 517938567 835856852 711781853 825043966 334026808 368776513 305939153 846686741 63868342 719550638 530402567 631369156 66031493 896423173 104663237 650027209 243869591 305136993 707635475 660279872 463262599 698442373 339447501 341297395 146366587 994508449 129144448 676815155 252796901 951052379 9512717 473625852 433970517 86881417 255611048 356829027 611443366 817390715 303448094 366061256 693963028 442239342 880065560 300330129 358203147 342843484 131917960 572933384 719122818 218841907 260266522 554054136 426945517 30179236 789860984 517630343 832916244 31265939 624526174 227097029 735386990 194391062 988093177 252122670 491477425 790284340 969447972 91815047 423901847 286256707 808694636 748726528 43917548 797036532 550303384 448165404 577631951 916699289 238420511 956970069 116227239 913834866 276698858 564908895 577463310 15448781 244847698 783860933 802316077 418683592 285257349 576821569 84506289 382669580 884059978 278199940 142414111 929082655 452392228 645978425 604614593 745546147 570025829 879468949 419087899 245002068 741417432 992823758 661308822 600689376 475823865 105664372 747627807 178399773 282658810 90655137 307405900 812028223 499703499 247560881 717928490 465302924 814804200 410493723 557728491 944537492 763587764 84973562 128642514 823224870 359344153 580815119 330602316 200692571 755829193 498037324 103882021 959421477 608240404 211387500 889906953 939700256 639692842 224628079 771833688 855771455 442282416 339786412 181711373 514727350 10344393 740733869 880856628 571393729 942610455 120058281 965271196 108327161 130036721 330260267 297189070 180555695 597067704 435245243 711454059 850383138 928068268 96102439 989596185 213552327 922949414 198557480 276335334 767368017 365996571 376950104 729520939 853872682 339969033 896313670 710922081 819075679 470324718 802445827 859616804 880119318 575141577 776429404 320488025 899626200 790645957 80045438 211102806 992751320 375044715 620470077 771919677 622334241 543811980 820216332 282167510 624222634 57789403 299379278 471527958 280668516 588315951 82974752 928278851 507172210 279809694 855436999 881966492 160388351 109903064 417505612 377916658 456954809 216943035 333968075 7745225 670543719 788643141 347637827 492634311 329713239 929627084 487995026 572405253 401332687 614849680 930719154 183338730 833600920 128121452 828825127 803269711 486400819 584847763 152918785 873113692 178214616 614426510 647224313 677763139 819726260 70799985 110714826 584219778 969043181 192272108 685310897 162541316 961572660 885914215 249384821 536687319 124548505 32668135 884732646 158382885 250422389 641601613 978277909 606735325 485039332 818246010 545642742 334337847 61863236 618675598 784036672 317566539 528090273 710739714 406590399 622112187 118224903 889410364 489697610 597335303 507542484 636166016 25829580 757751527 950836057 366694694 557006716 829773860 751864344 494925820 742536050 482947954 572517819 409670051 947228827 136536097 268216277 874183722 590704260 863164577 567062139 272570933 497941370 593134329 413365649 526699544 797325699 895956111 134193613 519322604 899626322 277682281 370298541 189283750 683160080 196150884 455577674 733556665 177655338 687115066 36619675 796084718 787000610 86388799 175882000 647603702 629702343 327965937 922501718 755544754 62004302 117791641 167351136 226902964 567780376 438558245 189573374 887094478 537172921 414981271 35841267 640664874 736419438 921631135 169756948 537039403 119029361 513900430 295331039 403088678 236071617 689817377 830629757 914186872 347796238 569298740 133446425 276479132 385438429 330930851 473154578 512003601 382531134 839049109 408619702 337878927 847494759 431906474 756047750 101698637 136197442 936465850 904036386 627486263 62255511 542949870 675199105 564639016 98930692 211185294 876401487 972699428 225128536 904921676 916094871 293555924 654637220 387380995 886478157 267788011 998598098 988415450 968621657 338723184 379977142 939266301 589270500 159139867 334434765 509297367 208694524 250825199 480310968 439588943 813152439 948448789 687400647 463888801 649546145 252559121 429214743 104912876 162859799 995750473 483414522 73946004 223919486 359748716 282600963 510329015 555344820 287661007 659939434 961766179 362176744 516899337 557957983 973453740 903794848 940846398 639789468 936871908 251248149 8511850 385985501 188366850 812387494 3588946 669409566 628045335 231951109 900592087 714545649 600628907 660287724 670414110 48974408 940491321 575399136 614463812 662851255 622203064 321738345 113066610 796960978 81622988 597582479 647458450 338032056 549386051 73720094 822137052 850696239 300897666 906263394 63387670 363803663 986740752 148912606 141312269 489302527 787355211 305460653 444681138 981805359 895683039 843954944 929597345 700876352 844576060 262944503 597224650 768051697 255082274 934500290 205995664 244340742 547511746 373855522 744112416 390495283 179071154 432605508 45072948 642451397 491299446 993620213 786203355 855089714 604231215 361194630 301224081 591750537 183249341 448926803 762525363 36636814 50952966 406037376 386108673 550591207 581315033 232689217 846857964 461930647 759825010 860940766 864348252 402371185 93218862 109967183 786672306 742153528 188710847 816959012 413840573 382495644 605593143 795740243 176912497 284954060 702707991 976245176 606084329 675317623 204534171 914861196 649062576 886818487 58971214 714201873 262853979 652183472 564553407 196710776 501522944 501672303 153831114 905527947 787576909 837935350 195607742 795415595 681956697 783652176 754204666 990737487 837199138 868182257 271288106 207303554 351482795 560969894 843337231 644627495 681533341 259350060 303765282 51425994 156694561 841565169 933885939 609543301 811085596 153559874 803617315 3969935 59058302 216835578 243399277 962739068 261087323 281759749 114493273 831655730 286915157 107950062 890515318 768511784 415748219 967026833 211108840 55130656 652877444 869378914 473305179 313862782 912023171 745284545 38277178 92852629 18577467 859219852 48998301 88090299 445825788 53721847 877395699 205174020 728693876 298813613 403521651 499826084 576166966 112532001 159333002 828621754 429076294 57665521 277560148 407046305 363239673 953066141 662030714 321811980 243815214 344511839 753200798 813948000 708200921 914861790 639252468 428444751 764628421 204400181 31860100 269281191 746895885 581437848 76924993 394189730 325751380 135148839 236101854 758629233 604641084 432057157 808921154 88401574 946360990 341547031 601457802 768564936 328283467 798831183 130943419 686223161 381449632 933221206 441561445 390235925 463476172 444347483 624997806 773774571 61858008 489258157 10477491 567097019 627281072 999826645 560286885 692129644 987113504 129771766 82604699 349920045 300746205 986204515 850532327 306900813 305100621 884594853 730286517 745940105 73902155 830323774 608680688 696922297 786340396 576233056 694694106 511072417 882174074 37531482 880704304 820527045 196233289 895264496 903812393 865708974 310042704 47213860 163151574 426188504 968721825 868848790 857017400 39081380 930463532 466917979 278223049 382960394 478495741 910264407 377459953 544864157 244032684 226188753 221343914 309884398 182817356 649191680 958458606 327443059 641596815 413524842 738116091 134538887 716078671 920487578 158587980 330323438 116158362 469124395 23437445 463689051 979413523 102388564 351004372 761143615 608947728 72069627 204875074 491284070 178861721 251273193 729124316 699954693 601843805 137370150 908911462 12910141 250266798 970231847 722250352 431996273 520607342 647897420 876512645 263894202 100406180 8154035 64984400 257419083 116968052 558438073 142132244 623764878 427013724 571270791 12718588 525764903 503130490 794962943 229334289 166715843 681851965 413383136 422548340 211355944 716183721 784731426 833171523 985314879 223685410 62628071 225488024 128975486 671427407 459931404 832281694 417460771 440118843 344809258 523754232 92767733 260129753 182160417 465854717 215199289 159364977 12262663 850702701 989079485 834412890 844887744 104078384 563253434 674564216 850783619 484935966 778182438 861956669 504799351 823843179 230381906 127777994 563496065 304601630 185289195 860134785 702204731 836104028 27573811 64436822 107562067 927665782 77647995 163245073 375506113 634752463 130015434 193174502 619248725 117345262 117890974 895475136 814595070 329463093 62409273 970108602 744119816 173885050 31236185 212135305 407903004 327257568 260083090 5572683 134521657 996498294 800403340 241975711 553386941 340148029 941242668 895762933 471218141 782203514 205262957 52517287 716195118 183935549 515942141 245804884 144929515 319458069 298162766 241390705 773569760 539382272 513030813 621655465 226600285 225065327 539998407 61578184 272969293 794021325 277029676 781335407 610711515 218247464 261846253 192466665 647302921 826036300 450302243 128576512 49595246 236143392 296147205 598223243 111840443 72083596 757825941 204452040 860268186 262218418 643711838 802745706 959235378 345478837 562717451 490185058 149889623 906106567 3635810 389321924 292539052 726296841 946915625 891115808 153354245 417861019 608394767 178134116 470603748 502730535 92738120 918827354 157571070 457872431 127702399 790008112 612835315 373869663 266026385 165201593 532559372 30055544 683163712 353028153 975953327 538479371 547384988 574963631 298924423 743125192 916805342 451393084 623093036 161886727 560082940 529504961 575246017 871860714 662436617 331908759 661710180 692562548 891877244 752620046 647657387 6418564 337242972 485615962 849186067 577281616 75467822 720070205 207219563 686377389 5073219 343171352 63504553 372790875 785245883 97253916 868447834 305509404 997432463 883980087 533679540 478212126 610517185 193593807 23805410 671546563 510751465 463516720 61916152 157944208 956282965 170044029 460431252 506741485 422781259 353036944 23271889 365166668 319751136 27164704 32585576 859453760 907809422 408649997 880418617 641064692 562182906 930523523 604168472 512200662 335940270 286990414 321708909 246608785 349181174 523748914 286567324 923332723 887558750 855460412 787820177 339827149 193836545 622407613 863550754 960641544 982469965 555520263 774137493 808275504 605828231 768273683 303004714 740542390 244506926 187264745 207026307 128513243 140075120 237837136 400635087 715766711 848717968 4915053 166855357 304599987 100125048 608291617 592303022 448547293 94975146 684749595 185114814 403150151 216984280 379864150 540576539 202351522 318346558 218016555 445121558 1443809 254615769 886108916 876762631 497822928 443911586 119676294 176610629 618990003 784090461 25617097 856899546 537082460 110353934 775463577 512465885 458395762 903390580 612261017 462670533 722079924 141498492 610528229 634589968 125591721 665605049 535435688 743037057 403112792 200756947 39100913 407174032 678968692 634566328 841562469 576129642 662351227 238031349 717164782 21066867 482692972 63250335 472034841 614890685 899731060 826622722 246795840 687991175 135975034 14971001 979750178 70406938 238501456 286995373 147816056 169123356 908987820 862873912 25821766 626942107 156910284 790200984 359843062 104048266 138349958 324658745 916075951 583934874 832024368 224652143 529662921 982287311 634432972 371902986 565432256 593152859 921923587 377369903 660098955 380675241 815479485 291872194 372436420 72111437 412758710 840973120 20566529 983099994 947686482 677989565 733163951 171929501 246466004 294836199 349402720 805928789 165756425 36378723 784884495 382355170 961932813 333990688 690086909 457756012 576420718 996618380 232976145 967453093 24661947 701344420 311222120 599991446 705817178 848377364 456290019 233209295 840362494 918369828 752407104 714998862 722590661 73981509 215301106 94966164 247268687 290791896 408176778 865759871 459030209 721976791 379359780 489210086 619408947 939756661 317632979 793764410 20292263 351710830 932763617 119089961 963515917 997689837 114267506 639605364 938224612 91760087 167756277 550226835 662554847 850000838 79532550 261508562 892776757 569984490 69719701 961389674 998149892 508804069 433434597 399649739 900082024 771169330 830335498 61364321 350946095 935603634 987048646 695976684 550370364 169555094 295134767 595801096 332487914 115818287 972051701 564019679 124399556 82404103 187096956 978120519 128491488 228872143 19908917 762301536 648953279 358037824 961280513 213079073 462688964 683706272 124104146 458092676 488849933 68231474 183632567 354412488 877394415 156981198 511921624 175523235 327361287 960670423 959339909 68547654 897212315 904767022 710420878 503419658 407094818 948404088 228272844 920330442 730697200 330383511 496885549 113479817 321853172 882820220 777110014 849051807 486496927 755188266 706896022 726657861 994901864 982296177 428520453 448111576 664743427 937457577 878212718 319865220 171799782 588163782 347191333 649597918 124377637 901064379 332539471 264234886 658990252 825925611 941904742 445292006 941913797 212719402 168790457 506592647 148767419 824048856 510573648 607725211 593382301 408031204 878188462 795375023 212826788 235911800 456880419 501127059 257953610 815107180 223720544 198428049 310267278 91894912 12522663 272445786 644539265 401137789 582165300 712435471 527064611 321507510 720791716 361026171 366689622 752267366 751541701 312613452 947423852 336574233 803261198 751485685 774522606 552146601 84133752 6128280 697822013 53837204 421325730 484375054 76805438 529934712 380615634 291432563 753539117 705691071 911057503 571008486 731064000 874073988 430931804 934714632 468705568 759747622 454249384 842282801 476689509 947012878 165479073 42711297 106930213 897926091 704941674 772470612 686868165 881891250 311007290 890100293 809533385 39018200 312111146 539539219 277423834 947242265 234080186 47056660 264825017 919935083 529872235 875277372 278398089 397817436 822633318 438075724 420343172 724372035 945232910 800920566 77717799 811964133 433845077 947771203 316416035 779521284 283493216 64907168 662984998 955386055 455176710 937257104 104508332 663803104 905494134 620453500 681581057 213068220 641414455 650836195 28264171 620501587 175605685 276389500 550937639 373221834 456764224 512276693 742069569 240452118 798362766 7736340 93810945 798375606 840568854 10165958 372560930 909139642 439869369 164856745 745048587 618219869 5853600 555967992 240656840 207260552 128355711 395854089 995950349 299814592 589486974 50570319 336715310 956813714 683137981 774032121 940871218 553432816 623665953 88774967 189330524 531787915 869699342 166835140 337648843 201112349 394401957 661570754 617829243 81937524 369485375 723814481 611923879 855211853 746022069 138562089 940234383 556729911 769156915 385445692 987347608 744607725 526491496 270255224 362723164 123614600 489594215 258529075 828730325 978628031 461157829 138675276 739492143 170589398 404209539 778826985 648521904 295354803 570053163 402993983 129075241 587031498 373693407 7207363 812680414 405147939 793518047 207055906 242635156 444890255 32044377 601567144 415371445 594182555 577854220 498500890 993246951 839285390 324341347 88359874 509492192 488639168 681166100 866237147 154501912 475587060 164973219 490681026 293884943 957412725 142067685 577568176 334794738 950650800 896802378 309894781 171490149 994761904 357407120 730788141 661160348 904316077 455319938 178354980 107606893 605992998 155413416 844161959 981829692 431747769 847901980 733669009 336152996 8149555 564939300 485433502 114725123 448158843 495156242 56948466 254520396 366073185 244832107 399151912 698239074 580995659 234388104 89413496 428402588 517179538 958327918 974587372 564657373 762961466 711890975 817737720 211458394 406965649 273415068 568498031 982463495 886887862 295434774 688267695 385817477 778203311 975778485 868399841 198800308 273106859 755103988 135673298 9447685 172258132 945179633 585458986 516018816 333175556 885736828 293736558 754070823 150125618 546339685 782909868 176798826 98472944 920390396 675102408 185163556 848841159 663001140 286489395 492861973 687869207 719331349 181978781 387554057 346888947 745362718 576304712 937964727 280096426 872305940 472578616 464551783 158572493 213016602 157551899 604904684 895959081 231863617 539442676 587767299 937804112 128846813 279727418 413896398 606009582 684373430 605619309 958976141 824725643 599872535 557627798 59035371 635598711 438405357 388304580 606909509 114059777 494306479 644183158 111066867 294981564 2858057 142924955 828198541 869092727 32978749 510598199 403821023 558029832 882380197 237911711 326639177 846510802 176918665 725925483 305081139 242833636 542904641 156545511 908523801 726442574 681035359 227410956 319529655 176049720 867200076 171629662 329004977 853886917 188284234 419814912 993252430 371051129 569445947 635076588 157022596 903585512 142260856 939624822 946615283 320532676 914871566 76230298 397630650 611905904 658648974 110714251 189091225 419965364 928102926 620219117 770962199 428620254 431424280 824077582 25038244 194294296 794372683 913578823 380329041 971744252 113076803 712495310 288559782 186228388 880659896 582600489 326433470 205205532 957017837 573702241 513079519 305513790 939957578 73252447 469718660 394314203 769532328 660609256 557369380 168605942 87692702 485266315 546507075 151950993 478736711 168181931 488150387 998899080 123454028 893971903 123531041 213116625 293873811 910445995 364912288 647771904 23186482 50319244 427893363 623286472 993665774 824126721 603569774 687322333 868185016 656337282 514708397 721789014 55690417 61450094 163554234 932830040 928253220 880869635 440619215 960701652 21254003 9512601 277945681 758551959 311565047 489564202 239302115 704688250 561397304 105923127 220124469 30830772 385509858 667914677 877717970 151371806 973793368 561364934 225659343 536927331 879259323 853524827 406149324 398494039 63967913 941206195 854248563 645205091 935106119 314898128 902244810 85315967 968180685 536474702 800633347 737376165 525241878 564457384 433452515 724888900 459291220 594743951 489903051 354983770 709933737 978660958 329605835 644946303 660040123 984642794 867747552 927078395 470740903 221867860 881829260 774959788 400086976 825768227 124084138 250139541 466696470 603038126 869219841 689513223 129040839 617526289 915343152 652878676 246783719 856121346 741809053 921083924 702411520 549770411 978563915 393398839 436902622 582278445 207978167 768264964 663780606 168689946 932634830 714789021 766414326 922246879 65162153 570712150 810355904 542168589 771394522 565839694 417770405 700852651 167969498 734402351 955133942 354539605 251631085 941290357 999369528 639557639 847852064 682348186 764991976 279914462 837364497 268613449 528465446 706055319 279563582 395035854 606820118 793426630 364298075 820506330 896755164 396042991 778241400 977381958 673643274 599816120 975364711 150499292 536271231 443560872 103494550 987908238 353194363 563097692 329260917 729635358 895769110 399638421 783285613 440845239 989090330 187914400 783635664 204907134 762319721 78706757 636171967 605320855 82071311 597830696 340999150 370860816 329453320 265615159 466897011 67691119 599369086 439676512 818168686 672951166 711415111 895724765 757491257 58965105 626353512 985460768 847230251 385416171 198328558 962048951 608823935 116071476 256763006 201174422 322125889 538719204 58286347 170528537 607950985 157800145 482432350 262953179 538376793 131742002 594933968 679357408 939361896 806723196 173729016 263828615 573351060 138812307 728693066 116885255 639974682 552847307 667133749 953326643 614115533 194318179 392710735 944142937 113209436 620914749 842135196 127781747 140585739 798094983 693097923 192289544 247207384 174595677 794303458 579127456 646876481 647095209 896788640 803144881 217892685 70481628 3323115 514458587 941851148 462261031 340159419 974802553 377397088 784042179 416925920 873484438 636238646 100787735 244579980 121274301 966572858 178655841 422038132 437439268 508714399 940203817 169100059 716658875 910008669 322499014 692456647 888287046 7334444 332460723 816143973 243555026 533535173 929518340 340657232 500019522 125817934 238459880 985913928 285295283 950255387 176603799 94945275 52576497 137069927 798196028 7436014 947998693 123858929 107485949 667146597 634912840 189482378 375677104 720828930 686726583 894865479 338402545 911310551 240816188 41715923 228712813 800837878 286540948 472023612 614396272 662699191 769911046 473046356 663114278 948214317 997431255 305908995 331426209 841154874 448402677 517509833 741576183 131881500 49946613 603920359 81357073 544153601 257654065 875796711 438470029 462747305 501897439 643114957 406641649 940378977 129755909 735091114 789997769 671271077 72087819 479950268 318572866 839796089 102195862 914081669 714658683 73085496 385365724 538057714 856326794 509625976 293669952 227033306 305324147 66720124 842325683 287707602 455161991 874515492 290481751 202895272 51255703 477276735 253012494 321741873 847357387 447999325 364937371 2502761 98787838 310542033 893981894 618259323 629159257 248273997 158707975 528006496 459477655 23910962 793002156 185723041 802533921 323795454 261543444 723197402 379487339 471510651 655517259 550849850 801133102 963156769 617796733 345348132 816189516 980832819 965755144 784785331 806258334 989361999 830763220 281916092 473548333 824870338 698970333 246678858 891844640 305128782 41793444 516689020 392281218 502111681 72312284 14899990 264658760 947857447 862643086 401554029 965005767 695765075 270558297 816364675 103511957 512541097 126940408 896083291 413131057 594926988 946351829 149743381 247936189 19720106 465436702 135582523 508751772 805841205 238187235 934154156 369492089 544034030 493258510 923217137 873845550 498708670 775306689 259341933 850571084 347676572 68000361 532707141 514217130 732471078 720741916 638667529 888339369 979718913 796487723 843598788 711351773 223702074 86728614 547438943 670806446 982607983 236994442 443471971 527022426 712457820 792936636 832084370 218698399 81490731 26239566 540367011 968308122 920884369 760617087 7341919 138673523 332864530 538419997 268438819 666426131 638392875 936603196 139525568 87347960 458623534 155484811 261447367 733072340 697139294 90227375 895509279 155903990 881321662 296400780 92804857 314526932 466390312 384199818 367286605 705243409 883096858 658363272 186506923 459069176 202815055 629644491 292710812 315158674 795131866 492336028 577336973 386356250 651248995 596127676 353102270 251438050 766355530 784699872 582151109 157110026 120423085 688001425 250365749 902159455 362606719 186541873 466502340 360119790 928417204 199940921 913987291 172597024 228348336 295289624 187450787 352059113 173690662 510733252 644359838 706667074 869898814 248830076 745192694 658332517 838142360 6369998 953279293 490022878 679782039 402496411 43835118 632139831 491646488 908111994 282938173 101023020 681648812 538753814 665787934 50002860 997140882 929041006 997982251 37435877 133440782 525736266 20850635 919932114 126504780 294849934 157347188 206516725 207964184 389077097 734701605 621211138 13458202 60238760 49378178 698434730 390792045 556077160 616766597 170428667 758953115 571871422 368319205 849798102 282445005 952460331 748130870 667223949 749652382 798982037 569999514 710613348 311820586 451309145 161168033 675282061 558057784 849441357 773570023 394372855 430576202 42253571 852881268 287468153 391464428 214701263 329873455 154314927 499967330 222118162 409066732 993864118 301293980 643331412 442157588 730955482 769964721 769403937 472235947 652702282 537943531 878683275 372260073 990849578 748933721 340464499 716386756 133065602 691901122 102169096 13520789 116094053 224113059 883543498 662508987 914154806 624648775 652216850 565736459 951025926 284454220 749896807 561319430 68912470 664101168 189902198 199454447 538080576 51356829 977039645 584334021 307991171 648128602 530800728 709604477 162347597 416734331 913385955 446168147 523402729 915548011 780549626 592138563 156485711 232460547 747735566 117584848 663174903 617253645 979685307 19400514 693404 892298556 878061698 464190793 932438033 507338253 851158905 310641126 706952408 259212575 609441067 121468671 852392854 240659794 686951932 329693436 24185735 467768673 389165976 67932279 543857317 995353798 798631190 31244391 990218538 451019029 887653408 586053092 540615461 902424691 966861718 268385966 818495416 899683806 658911128 738887596 339151071 211883907 144515003 248479895 479660503 13168832 522924373 590829333 71562847 331794498 303706602 108612426 652717144 21402169 747193262 58574479 114859435 474791935 97218060 521256291 213359037 296101578 169472938 622020257 971400802 746558200 874630587 949250073 236628680 962059806 573923584 583028484 295082303 662888627 747880961 65467898 319391198 873967921 859182026 768541731 341123894 658933926 681017169 605689684 591562545 159971483 553029747 784483425 650009305 536086998 447722067 364592655 560976005 470108750 340895779 447665424 809303490 744928682 666077169 639139764 984502503 148751607 873015394 251901273 971417321 803870213 600642935 422005428 339862337 442483139 210433667 266763537 915868724 827154390 239269333 6318076 663863147 311794772 654614119 54437484 125191055 370536614 282710942 10189054 139937716 67802273 668595948 237552163 627367369 894039952 417485410 80812411 212916347 163480882 505962275 593289496 970874536 858627405 996855453 263714569 237353996 280328886 346191112 751314514 906517397 65900904 288215480 557238352 249225684 767116590 479934496 754914107 529351208 431892525 739177091 195509250 303524680 739239404 841965497 595060227 116716310 232574325 27927618 994638058 255690969 380879916 971922092 15730190 4124635 939166819 963723693 376124213 182310166 495948851 959503951 70636829 813776597 437920724 891172959 928596888 821750944 762894617 22796216 582772022 448220017 765177429 731021474 848510119 469561313 635127640 694390340 404605151 898704988 248365162 805478581 586400508 75722151 726102202 861094236 451651177 234628924 964515254 782770454 460985866 608024329 190924564 680272483 111571502 230709218 328861149 384891197 410907795 459329149 582221349 740567781 94545165 410758042 508790338 62818084 929626414 943249346 996670011 887971437 814666507 638523645 609464374 725475938 176723166 338240061 919307995 606292497 379667512 754070009 855567103 446568579 143318651 617762773 732843796 499209612 433179644 47677331 640596633 482330812 579383327 150131224 45658184 467827409 857430030 657083818 311856199 18840336 312365237 347677733 249492311 448693832 839188834 475454090 563091285 761981012 192306141 312200532 577995349 449445189 332947306 567414777 598358385 615321425 880356675 825775864 386146727 234013059 664206084 816618235 825697116 338405504 93551178 614532887 823816417 467547867 714835260 828156636 629621802 595851702 164410070 705715737 907705749 836104536 935369076 74940037 353906068 601749518 885918114 980765267 818388727 956931985 757651338 250439265 187378918 557942301 314693006 317424341 78785516 55761408 481199312 366419662 409592973 22748271 459490176 826923348 982004342 412172067 162668083 488694742 998289775 552955665 253248564 677328484 133737075 178668146 29006526 738114020 995451740 202856829 955986125 216304118 672357191 798762103 649169404 191434285 161960823 51986899 691090378 218265952 571107051 3223458 415779086 773704654 560979577 806159944 972787922 226165644 452897211 402807597 899213117 901359406 599381035 698669595 39789657 311874359 208746482 974646742 909613009 744380714 73593728 876120413 78971258 852898640 680126456 276852454 609698364 557228484 885704880 682362158 573657616 259689483 596841662 245019270 939858257 188837520 187415297 872776019 637977864 594921689 186136761 70582943 428981910 983955850 88524289 822251683 153978255 465821292 922973632 443632225 710312654 754826811 18928607 62374465 286443562 810320169 217024946 883388944 726972496 518435946 221045423 732276727 596370633 818035027 218832207 556967858 64093469 740337043 775376541 557300113 659270169 827481464 506312748 316999597 316097725 788455763 697228958 587796647 778463008 240329726 398090839 741276212 375579809 439780762 289302830 453151081 68175044 104470688 809398139 846616701 947802961 443805392 838724757 964833599 883862231 38286571 482943152 180871783 763908879 596597036 992222303 648306417 143946159 585439716 949678259 21646846 734901639 642241513 837308001 41425388 658341824 77986636 634727403 264849246 974730892 766674430 19946405 411562281 918240943 351132862 970050901 433739168 792295330 483810199 203067269 749746939 705587887 160835238 910142893 79357816 854955146 100341724 817535350 144651013 450372705 241386354 428122986 427713596 963659158 753282916 272402497 880326197 800061539 304661668 164555376 370093294 623434778 814642 972661445 618538545 158037257 640583827 565639938 486871831 718926564 201218862 563769825 129439751 709493769 649995887 581047221 962930198 252506105 280791992 25501578 814449984 780268205 908946714 704656991 185947714 884174142 917397670 823159148 159305897 240687339 21993661 555827789 204151941 182940846 806574975 218057352 910305864 478406178 756909454 179444695 206977648 667903557 545616750 380292646 61205487 871276201 737655503 790170652 466366847 765338953 467033215 730849028 813537602 202430745 717629268 930662902 692260206 580099120 775543263 22769299 370386078 998842023 276437091 21851000 697780223 991385212 871370581 926282506 901909895 260853794 324485395 315168760 355105322 295015955 674847717 764746442 452761121 37527255 260023193 722510313 859143256 284762117 754177054 184493458 434237285 33030732 312310926 688283666 761555189 633355883 94120261 432452598 483374393 555034743 697891709 993879874 910942197 410086045 696636614 592549350 208411354 637560652 158415628 22621098 683092385 38447955 750252824 720694816 789481678 340285428 834590680 534487206 274084764 485978273 740142239 536024467 687181677 555157862 108673166 331370421 727665784 348734592 858615660 552279901 733191838 661299496 52175393 638969130 20147776 595954419 669297465 556464804 366674116 443150211 653569620 6209277 979053177 187185093 652276865 735500026 700953621 686019609 151750650 122443799 166724980 459679360 873100081 551106456 893403968 362870461 535924122 197819363 315202170 84992088 526573710 261917425 32465767 753948812 33443862 583392901 950863256 499556753 504716301 49183847 835051551 646345844 356865948 600788834 556435279 150801307 49417325 11763940 708819787 882231049 83387084 924356696 587987939 387512461 593438101 113578020 930662983 234076801 807324561 533144341 892227736 423855987 832603794 516805177 311163866 169034326 81757370 722844876 994089124 891958622 229109758 332594427 776609320 191777466 130316923 264472476 39741923 504568242 384075866 661487057 549113970 993105514 712508164 542360088 229279434 992766913 407407665 496542064 976547942 13115677 557640050 461435208 401372557 394027815 588364541 958482964 172943615 537817596 62979031 657603244 38531943 122647631 135562796 24904185 482456366 663231321 708235196 315787035 299064611 775830728 81007898 843349333 806436300 940289922 984956911 440312451 961618746 673411071 261404564 765245924 848121281 873591952 248036967 409664051 558552072 591574238 907279020 465075836 736306209 155853391 499949769 927155751 699764140 341223448 466842742 198916752 42233793 215819023 168524690 94108422 736348846 510079417 131962431 573676126 239927011 509185386 62052976 696115645 148135666 831669680 533837541 419710511 953144330 197917192 229545548 390559948 224662721 550611439 993855707 777598768 604382067 900335576 982313462 569533526 263654539 793091019 4386060 848992647 358352206 391053657 696529280 175547896 252075946 647095458 845181313 780402367 213823336 319170838 409292290 328605916 640660966 316696198 267802188 433358776 920984087 57702926 545824190 321370328 587611836 216050801 687457049 25055545 495230806 893091064 728553844 877290027 734814180 929547251 693823312 330649834 990210122 433909147 354571490 393858877 243211505 682469322 397121507 774099452 99307428 653294479 27890214 881653386 157934244 931656815 19517655 278261489 85968277 711201717 664412428 223532516 343828755 266845229 82357890 865184681 868203330 920637997 307670112 916392159 545647121 249126986 619146600 840839432 544316860 904236426 230401967 285898577 141203123 962713432 671737494 132380326 968075899 565214833 905393297 319667041 884074447 674914208 653028293 171397025 509649457 498639138 861046556 468700803 609557917 192236180 538923180 515516998 973765898 527597162 653986331 5600618 420557556 895703745 855850439 468083066 236638510 551237184 830617805 447002127 208640150 815865300 167502742 66977322 914986919 381025024 682979906 688356846 819464151 621388184 620816603 149951856 365218805 886320809 781929523 433608778 507767633 760125218 817168332 135621097 291137457 680871875 661521129 975568598 672254624 477628506 695979710 884695937 930994709 231242209 9819626 931743268 632626741 982828710 652231077 205467821 393693562 231940418 904171346 907950857 522918967 30977235 551819362 526426132 290579297 481310829 983769159 595203780 655007819 632090259 464998910 322835221 523946217 677212217 823675554 656295031 201566726 716681537 79061796 782103228 75602450 862636664 482005761 398640124 915281979 791187610 817844883 381485335 604060607 737045912 934818136 45197382 677262399 880379801 552947402 323714212 363261349 185939399 261019697 307410627 963631570 762686301 670630782 743329449 136223764 494261901 790246915 503827957 427282577 910273246 922610161 698903824 584249362 73935598 575300873 483282454 611519036 791117912 465349957 669510490 553570665 930411633 288394612 603121831 518414104 315064843 282319994 569322930 73594357 606281694 464953097 92161486 859110440 843533113 651963696 140634231 986819610 637318898 997140925 908986736 90161214 499785847 471707724 155172832 657335886 521624734 251589715 230628034 601415931 46120497 55971398 255499477 317183506 778291537 335493247 926332682 131244721 352358617 293932368 828222310 682279256 276763565 452923492 130982208 312553735 917405216 252161456 754649106 160128557 47700005 32703371 197958124 751093301 254555771 302563462 66045646 767671638 417412748 639056178 337374068 332674026 313064948 636870772 38292685 513141655 409748615 59427853 872755070 897372547 395036606 564914155 351266553 70706150 622991565 803980377 59709974 118863968 141020606 211404294 262725211 543335999 765688952 807565494 905513973 719771035 190830543 55454378 166266856 577879308 532969576 811898502 786877179 64320254 131687750 654945866 786919803 262076817 427424725 429311098 829763597 581659365 898195286 753008566 209996538 450217214 893292678 10991473 721248196 975014857 36400742 694213067 741136571 375714646 833695255 50055663 961336469 737198474 777724977 694970859 201078486 549564564 544656711 983701182 593314123 301007283 334781948 550529303 20639943 209507085 616234344 335504225 18497286 694532362 66741277 102897917 926720258 991545856 94640451 928723007 34341472 510931442 829315491 873645744 337824082 943891887 115593351 421078268 809794568 651817675 78212000 789356084 10311893 928767957 473154223 800261135 398054024 813142819 166009526 50330086 177930221 337206603 230379423 971214347 907538903 910133218 423652180 908818391 299836328 81874167 983820084 380342392 535623807 482711657 624728863 742855535 500529684 285425153 928052714 303296043 673978799 578413582 489260069 553636070 202079802 204673691 95929666 992701051 303692829 119994162 123967653 472980159 487972958 296594230 499550946 80704350 96703287 526762119 797782511 429042101 604087108 685131159 712640917 753687092 117414529 623749677 817836397 811074785 242605753 486571833 910073813 31984908 172838333 382927446 98047593 609145865 297426165 363666908 846715274 633362665 191984169 87251345 219273772 392720052 18250067 345992429 752664988 475486137 959118724 1495848 956904451 765937945 667940392 319070908 272551650 675706695 785134935 84994310 635820620 803154159 651065661 120914428 690621287 47613603 452059228 987540853 151552883 759873602 563563035 399725468 729258893 682965715 226480458 900242620 689895639 931524047 130638205 440453593 534469495 181731491 115734515 475517842 827891216 7796566 58838405 333360960 280613716 601007731 298695845 86973562 719168891 870268669 908086413 369070016 494403249 115110920 126546019 14492530 631187083 313295749 887301092 748259065 464195209 757000603 435804687 294489434 62735180 65520605 692113734 506151181 976590500 496729338 18978434 722738748 218615277 483231518 676660854 74569308 882429448 456844618 196361275 223224854 223352913 931946474 913555166 168390455 853052644 51058682 710933416 677505397 169113137 590265544 755764800 58542140 300887877 119858222 745585 132630982 383268077 227179450 262276087 303728062 30516935 567568434 468911569 88072387 214177730 726525672 674082879 567369417 178861967 987825755 883433280 520060955 226622109 172039673 423518535 911544461 542973314 895356702 716850315 797787838 536241554 927756696 16201009 75728649 374111619 271685518 697818987 833954433 872698169 271233792 366611052 432882985 138467463 975239508 854716169 279079373 8704735 239435222 822015957 23670584 951868620 499993736 113379109 525219682 574866188 77879125 96776968 802575382 431086953 450560045 306794294 863509351 599548945 725185678 959260343 651864536 34552902 201182219 700381757 912754154 590253411 938166199 292296340 877853455 936846071 18787657 657456603 532016563 696517952 919333429 321760338 238382776 22830764 856565217 541731914 642856547 328137550 388759642 877876973 422843939 780879166 134635827 931063105 748516609 218182926 42315557 448215757 370229484 12752068 237910645 118907873 766601607 347379821 646641502 464444840 738969508 986830702 164686203 661884216 455776639 191445293 90698596 174170324 398322292 640717418 73702954 782345197 358621672 577347939 548191021 78937980 639201630 262761929 271606815 313307909 743040120 394300315 700245073 747672767 549482727 772510135 803656245 425472119 345752295 102585265 29988677 507390714 493387197 742710601 199366582 836079203 434703535 343613127 380935784 10879963 16142493 98962251 333333323 126568752 588430575 693183397 517886556 146241651 58482421 85165387 222982090 373075316 459453015 376080215 16507420 52841793 901705095 31790040 370031331 603569345 177303927 997207379 410714820 406567665 297316165 155941872 753702417 698453722 661790178 289576492 179443152 682565838 436214602 365466756 704594027 856813840 402095560 440396748 111515171 546050839 547530589 428790857 198134596 183503501 761578323 313189637 282554643 497773089 357189333 727278661 628652504 997113199 391896795 46589498 149532314 723919390 849544785 115667027 933847107 482707985 600966164 779114444 260072846 705330469 106176539 460552064 476745940 230584690 399945517 256250687 896182101 690416518 536078296 42450945 162827684 714956972 396220404 721877904 338260895 127799133 477515963 189552412 144526903 871286321 543964197 486776969 663054033 262844787 201530211 93141799 282271916 557475853 900787624 124487812 519700411 690503767 867255779 392606572 908901936 783100213 601828776 401910702 163353879 653683045 442355876 753073470 601376308 737896145 197532279 267480942 775922194 329971209 351661795 499411998 513048868 717086473 276410957 984464102 731232469 355701393 669157193 183300508 681546723 181543902 492673371 175470673 238775460 26083013 430522420 999092986 755272573 619388054 590694230 721938633 815553276 479876574 165813897 697436777 979160308 726863769 352628031 712536369 432055889 607597469 98927152 576186102 495750899 796176738 30887147 629289730 986435677 947497851 70104580 46913497 358334558 782966858 368679500 35441427 462280834 752612071 896645478 471223758 838684181 287869097 932802883 6558461 708450340 921871324 322152069 419485678 692286249 792951384 614694744 168913335 329137705 65996457 41164116 63876907 128531000 534154287 246769750 3343186 165152837 952868471 299527936 13611577 914259541 752571107 226169559 197546279 563034031 353207974 791986525 781977049 439727147 350993663 791073329 475504402 545914412 971143408 695234394 306639441 92686423 305818032 387252150 490576631 452551283 637744563 917846508 134162795 641074899 274409432 830350348 841370890 253794113 111402985 48478565 145594935 973504780 950243264 570684177 607968502 507924276 572260852 259122344 847587469 42694373 588992772 577720175 988066659 944405859 6346807 791490046 397572526 149477326 648800687 915507405 332559191 292375523 818363332 941233379 943941498 357107223 280081520 234731907 24250010 72837895 798227847 760595779 447653401 605060170 312755668 949955987 962890595 878538063 394284314 184295002 528854644 10195944 375150455 922147255 768745262 145690970 597144698 404704836 947193483 852381202 632171691 808906854 267917125 346795140 670693780 893992223 3316925 356167056 639126769 836324024 355888939 970881144 137533982 537684745 977374214 145373936 647323216 431646492 276575073 529638895 730414511 840678388 657989995 975162052 557026150 847384881 617525772 841539882 753354077 451234366 730084843 933515158 860351443 446239604 184564021 182019901 548795556 787210523 726392501 685402060 142011241 683027875 493047988 578212478 413567659 437190554 452480501 827332804 918749508 554956576 659003198 972931072 149302102 12883062 359930782 343708273 986553079 194780153 533891355 34702128 171027451 781092963 322759949 637660803 405933506 198022706 872841024 48059402 972746742 304689151 641119113 260038099 409384881 507781281 82478703 517915737 35162339 254139254 819919985 540066045 561061804 542498129 69727109 162891775 118318191 923205078 761471326 718363018 158559020 896510083 208474313 641185630 405322248 881085667 409863427 213842399 198182203 474506794 579227783 359641829 343749855 727029760 8260989 444908528 432422928 556297385 810998294 761937387 753459403 841540764 984703876 869451684 635490606 223823699 365478442 775990164 795295197 59350971 550315817 830435367 691185233 947113166 529062836 479338092 556241582 632068647 409792342 290074075 388420021 691365186 704799721 392255149 669159378 149162281 321550885 677915805 211754222 24744152 281149546 679896651 312983830 246295379 890880283 945028975 886077734 152560092 339370000 650402550 435184189 661696167 14533948 538343927 79757856 279481674 918516994 606381675 506105068 771931779 517683695 174091806 480386935 889915022 671766007 204587865 714474040 507401221 779186792 75732041 868176792 703866758 267827498 764054414 55185367 197295160 781739464 336547799 634285842 26580674 235618932 180476027 511521078 320407409 852043921 839511932 485868931 194079318 780659536 751709683 759867208 796573264 523910158 775076637 826528268 363407871 565895858 796828297 91042090 651891795 799268930 298951288 229608406 798579642 697524366 636117329 490437405 775896119 643111964 31778631 242700951 937875060 187849996 842235510 815813601 97222827 235067921 390305228 689912874 52143885 448838185 541428336 7429175 101195820 71233305 712707295 391205283 158849116 788594377 294494528 777284242 289553261 52479421 894233248 713758686 944349266 129965308 706704076 643594049 358790705 911611633 493233542 502138414 130845882 523877260 205932949 397099514 596269613 179142479 146283763 983687982 456910134 34863451 627489671 897614201 199440338 904439034 632167179 840578446 459381890 870923200 833957573 420418980 11922802 92700927 27866129 387651342 247409474 942195328 955273678 882579155 820107876 191292673 391283815 682649818 443745389 25769277 876685754 552326535 476762255 446402531 871522121 301326624 179222983 966303869 363486879 645592446 442015098 380779559 228451069 106911355 939648228 744301307 24841072 212026826 810524112 850962763 684661422 317617765 312404321 171619834 933055039 66738636 397369317 948097789 577843189 545428157 438677196 662784012 634030752 537194412 964802426 691250833 216556599 310890953 298546778 130276794 120170472 244022690 543315445 609699074 936396752 757927197 155337700 784098749 270777589 791738906 366235443 219753842 690333724 330692297 55475019 551737019 468197670 429528013 972337 199589067 397282017 16527756 354454930 703429120 89126164 617742038 134821399 614797545 337279614 905583141 81718540 264454670 880647393 360851293 998501423 32295767 876641327 532243298 943180863 962065715 919698065 595721734 417878377 992410761 357129729 456336863 69445405 138917339 931266306 321576502 620636262 71262777 444858737 671119062 384879446 577332496 226934090 104946340 124126475 176873892 421498962 552853955 467328782 393826622 158817362 360041326 255441108 275691708 433873812 779962702 845302460 279149940 651099252 949930057 672868373 134006453 461245258 316845588 262948881 869019449 627737664 251069571 588258617 673154777 545733609 521592994 934011249 903179544 626559251 185114863 649732218 460181283 666479331 232288409 221993654 568304917 725958489 59564254 86311770 159214896 513384460 284897173 558120817 984440962 662925786 955260659 853063497 308037176 80064133 806319136 282877813 582627891 595904508 917371848 744391952 794180090 767009601 154806025 250294242 417127296 494549970 604474802 737759407 601590661 40975078 145883017 181736701 591244237 794005367 308249335 342344970 571676303 710981048 611547004 48614 865421808 795757173 2649508 934803686 356079786 484561495 718107966 304912572 177321161 713211600 67388535 786356808 326283753 198650439 690108344 888645657 591151746 64525789 884152090 24504531 700948435 448222648 378032890 49111856 721820908 129977695 583206927 551633196 410529424 83064157 112965923 286090454 324760565 769359225 793148434 714673636 818947202 733784889 209325449 151047090 334781712 172558792 242731912 608391690 109818324 385332711 33875193 317797584 591637982 288754516 357217244 204146667 159781204 951682350 707393583 354593554 597977828 986615668 799325221 485849693 301301533 323373138 521714418 964319175 394163788 258135653 949033980 919409752 753308355 773942188 909734302 922670706 119922107 692738202 198470587 636167430 587709709 804266013 737184574 386086707 949385611 338964548 911689672 369318277 746746204 597895260 384536749 947136731 932041004 665194840 531689009 824298738 455690054 110177158 3403203 858260046 682308251 615879417 63780511 969009034 88041806 644670826 363033337 476169281 913193755 223014915 32932165 101175255 197503592 197481319 855092176 734821446 873343059 481950047 695761084 748888875 689888428 98635454 482381142 435051781 181406216 79574949 975209601 900659921 832555744 291539637 253976627 595988451 724699457 606462841 946692997 880995220 699790878 56645628 359288641 303592278 347209485 454022840 894100725 888394321 927836233 840338333 831287860 797734010 445782675 398816671 318648927 159497575 980138770 11166724 371592060 154126305 201316200 636165518 188335292 453825083 831512827 883180103 55775116 752135305 582389609 482432892 721187608 810959501 213770795 879916379 417025935 84431234 714464749 132641816 201636718 427710484 206080960 858854955 83309323 66311780 508871122 840924123 632870913 60854698 4214615 926972703 686165883 960456139 874881338 765508336 835466211 357176192 830126326 466934654 605969791 668372423 440536003 865805296 891833540 348773554 16137152 203334635 507269692 117326156 707614210 719449724 550812277 828786435 97536282 398761092 593211333 753290137 748223130 584795368 174279543 786063797 611445156 486471995 524050088 78176412 206619248 224332586 409298302 264608860 530519573 99776749 797633480 209573552 909683380 803155651 935966743 300297530 931358838 236810271 645700471 930867540 122529786 595738445 551629113 181490025 729422946 858114176 47162100 656105961 62612688 455217493 306891003 584612537 542390467 511584675 464759836 187653265 576263468 644706119 972052254 866685258 206817329 219443128 885707725 125771126 680950393 887392741 940035293 600312892 90057999 890424227 131863306 293107902 499093007 444689701 980909614 826748009 541408888 543026579 26104385 128073382 664570809 291352139 622633115 294030226 799682896 409604691 907564035 962192134 581634434 957641529 879371125 672104162 878066484 173692554 936135761 707199684 319722352 34219474 178428615 661301371 935815774 686988060 736703182 40514989 679195992 151696868 640192877 598840384 42394249 80881731 473773550 573177426 30446059 753973366 290563017 438160327 496136147 499884741 64721610 938258850 203034361 380030655 205253400 692449217 734258709 618456316 147065210 901223026 933098979 231454895 284409458 425169381 259989810 68736633 825247510 836718601 329940981 446848994 186236571 8170606 105963635 824162352 70364461 67727030 262864423 50779539 444879349 53757859 388315099 666596740 821432746 463275691 53118392 298590587 219624251 364080279 536207028 211829014 818857832 502113592 467760626 215725000 846692726 552280011 362310718 608026693 669247236 663719988 619363580 826868482 811803521 191970752 316901480 350170953 809778058 150164511 994032943 822747197 164566303 904477954 342523227 246522923 451452627 417397710 682997333 211313062 850464001 599524969 828246649 200486473 884764101 531179724 363093755 381209904 578186553 101106596 931239570 541791768 907374734 552935528 656898457 625686134 177289472 753380834 227735944 171924682 351658480 889754169 598065061 422435955 486136109 546630737 731232919 533097449 715814678 783599912 190485372 432522190 822009428 97011526 938024071 616579690 894922593 690120997 603517792 658414322 175568939 709540694 43186964 851719351 288110262 577967473 470992152 327102395 608246459 424050055 749411811 992080025 758677897 344196608 129163374 148706778 17851257 8771474 969089315 366138818 938194718 526831845 426223443 827925580 244811854 956995030 837698091 939880455 490733450 538639861 783722925 558671981 269047084 677270582 654392263 371408260 732354511 532183585 570629888 247508600 178849029 269790824 551899566 582030235 528378787 137633159 859497128 790888443 716597501 898218318 947903361 739648589 951468093 666234570 268559695 810811689 866881729 495461442 603086311 878805707 370669937 768438332 555580018 382894219 558514275 105584902 462202163 660861229 264232710 166336249 413803854 855826010 451761002 181107690 124345209 663895181 838870577 347079881 856333462 879532958 233474701 185399797 664822352 130256151 370275527 527804098 649044977 976657678 341416417 966037317 862142305 797184710 153791218 86752007 614240040 333296985 284417779 476772399 968825759 202842368 557138575 502032595 771505110 493575617 123075655 929237685 323466805 464948240 17079322 505610915 691711972 95449699 249370196 205993922 318042673 301077192 877309600 496724082 240161339 311877515 993956131 864473766 217695948 632044398 212419155 593751841 286648862 164802693 162039332 441461874 937042497 747581357 43066774 19407492 521848253 675067947 537321365 374937353 431561262 896510941 359919897 296590885 444189274 276920234 588432382 191265001 920484249 511410642 906134522 347087734 29712737 77290726 432655909 454040717 40412183 389410477 439702508 388248885 712074212 875392540 800310066 799953488 412284733 649654403 459934213 742317629 599252845 121923287 697325745 155037176 779991015 64868267 709351536 389624708 512149448 756074211 815803037 870091976 508475242 491352934 467003676 550122314 506779871 684063162 806194691 208896605 529779110 411968026 701332708 383102154 868622671 212090117 288921801 125224354 78559654 485153758 945888700 971602705 279116251 172586364 970909271 71622635 501977194 553471478 251704121 173993587 336785930 436220320 113536016 550288927 214633969 917009936 158303588 709493419 414960581 153069512 854959688 298379830 96223057 808298288 993000828 436205843 399198721 897464870 481232916 600620336 306913233 659369882 606268728 424518090 201508088 884864713 82043215 827063546 116022045 44015920 116547997 438897353 221890633 267458738 720502077 875884364 186155885 85427968 561671575 43269087 97624279 479284962 833552576 763887009 457988608 108399165 658816406 546963481 398176825 567087331 741358210 432550471 403314826 67226405 424916568 642382270 985010351 796765376 118144000 758079618 346461796 712446409 26443903 957280274 17677061 346212298 34540201 445223538 613038536 167580495 349609844 278410393 748072457 286231679 106299181 307801313 176433726 269785248 666426644 980654097 170138192 756141055 774600544 890110408 509277885 44160088 49010280 740028746 353624381 590075826 520911077 386146303 628012998 799115239 696657809 725885948 731208974 633639007 427995925 143032615 75496943 3375560 636856219 712144761 722680807 951494721 622614906 207318423 267330461 156267220 583593109 730404510 235003618 727712216 213756805 873197826 543192047 336482217 793569037 305934411 449607112 149340256 941323265 145797615 282929266 250325634 279824975 553875806 150202272 664598029 763192682 949861707 618916138 37679173 185665356 904346445 382475703 225915266 817932991 346669908 278126025 227147320 425570963 778817466 931309640 348242658 948197971 460517568 157733902 632693250 913113749 403082984 871671953 861615439 38537978 672269383 642420377 54891459 453777403 94385186 747408410 874982422 194192298 746750206 514353307 574959684 460112171 358126232 842665070 648662037 334628805 730112093 192307532 643480981 942922714 922164539 257634158 691854354 332232335 44648780 5528408 584219685 376601118 861674546 459796047 202081952 764811290 505022449 883945214 537343256 575377089 876693392 28355857 163368665 758441739 294582017 394143820 635651593 712944326 40153937 613857674 807749477 910903478 143574716 335838551 92633319 724100896 136183593 66248730 634793200 852153310 762069393 475190498 798137724 981399601 489676430 832344421 706476822 49004686 646025868 131255611 86957776 135090528 374895765 357318439 337453885 430082207 455958403 319931407 946986355 518996405 64082506 146820758 38045201 961330717 320005528 313302108 488329476 436592162 828112175 42697584 248398067 131240275 191064576 136869437 270391647 17914199 781680375 392006445 789990161 246186606 619109950 758377222 307738258 35376957 229340880 948184204 517340954 243073717 83286080 341792913 729414199 958684435 909171556 196650575 941584987 109665277 42304150 857734715 864694607 577571455 885526871 852252509 753123212 701075656 167388076 915641720 754338330 13939807 448844805 835522215 475147886 594222033 207642172 639247967 919036206 144425568 6221892 496069168 554436707 891957273 106639499 262148171 950940251 313513742 563769708 851790372 656444215 993943081 661972043 856916546 511927823 555441757 958909599 993508084 797491886 825780870 198689811 644403931 140238813 369119461 452267663 83329498 648547034 705739054 783947405 606470374 476574786 754285729 448400740 265883248 11426695 75404206 759615758 88964794 93108795 659178561 238403892 602560076 246454724 792500109 52740135 43012052 63989748 900670392 247283708 569511723 42490780 218610545 936602607 543633368 734288222 82857674 491246941 92807731 132783945 924722360 120572523 228579117 408319258 638194693 874851517 283294587 558587025 388529267 872851396 835597957 866759106 399046747 20589029 467365660 225563543 488396898 814241018 808305680 936798008 591759683 991169837 746503639 687198293 820578077 234848998 417010887 773393092 173389440 54166731 105050293 486812852 161720767 679792134 351433287 435099629 691032457 735960461 624314878 218191943 803841856 183001538 732725463 452338112 727647442 789816584 573392250 764212480 837425006 338713746 237978794 364981378 880272305 150015121 615519369 492343186 356454461 316076230 210070645 726278221 481927361 807604799 109196627 74931044 339621930 105624580 736469621 811367136 512811937 882921199 283322434 511708830 969551396 824347623 520811038 862742676 771640870 330701266 735131348 825674055 233574391 656791209 514244674 156040967 333555082 959503203 782134572 249087686 512992842 899176393 537466562 58020312 577698790 61320011 845441830 754539329 487796910 647163740 801052575 337362965 916429074 471695635 447337216 995299247 767119822 915868204 9540926 354289805 670225568 98595152 924405131 535403203 365410472 431748367 502748864 731354377 22065135 864209713 860494039 508397872 501168760 9264733 641184761 848098243 564624484 48748910 912474699 737154449 224562749 714183569 61292990 966619657 775147957 926253784 372384183 742671292 969014650 537651531 988232255 492827507 253109041 864256202 990650399 836021291 222281520 313950996 792230177 441626022 364537967 565521977 277076662 161521518 732703823 279483542 433121563 84729210 384315257 599828043 681653375 555943223 644957896 108048388 427352481 577569669 652538046 530170211 384330863 671987501 344950182 694038720 562266394 468401870 926426669 255245460 491462645 884649123 851112493 11563492 838111243 193978381 251804419 86358839 307447201 259744479 581975770 189024565 91649843 364649476 406563781 279538320 904630491 607833387 266005225 542485592 548220431 998425456 919187524 516782091 324193840 460676703 501458104 742570339 10496563 642851605 433520150 716661084 539420811 400574501 99437268 681039765 495280827 428971617 387679054 909642333 990785211 385036155 823248031 579633338 128145397 907348907 183243129 138737738 106546870 951999132 364987256 777215355 269194586 911148883 790545592 44717145 926721568 677198490 761841727 888912911 614296476 594325716 752113888 203314292 880859291 861238451 202304052 364910184 612619873 179889381 387595917 571950279 280957968 952209157 725982920 677124503 190480800 267062992 365892593 947169479 207560685 527860823 461069540 208012038 790230712 683604460 812229073 620660241 454652619 499734341 586930132 390135838 712688927 862373087 531576111 513423013 185858993 992297205 266799028 158927528 690030912 333478624 983952505 380562748 337937976 423196211 796032485 271027750 257516289 2979239 413277333 110631222 822885774 972672144 500960487 683090524 767714498 812002171 929678403 102205661 42513362 738501115 25204818 776072421 662639505 546450729 498880579 501838881 553274906 937745704 477710448 581960260 890904534 355413411 520735158 122912544 355870539 273824005 743639036 720444741 884100984 364995933 458369154 796891425 194596111 172395244 824766461 597279694 891511659 515835182 591857905 548380942 646342483 684070222 629696862 906126495 372947435 936276503 139525506 623420069 758092659 666632459 853656350 669718576 216190205 768824878 590027544 980341069 594189721 878346154 133820863 300238641 758349883 595178995 898233199 433056925 496043584 633866566 537941049 338643171 918299185 817781760 801619192 958791952 856539908 58544316 631937512 644025694 343097712 575098447 41998785 944508061 131865073 400499853 843896422 658801362 373663494 145483651 554545492 208272694 692327495 352387267 509993398 751979305 726092773 806131882 313729869 980291377 744446426 173819682 82299533 585210248 66858741 340507181 802180982 554445436 548128264 410839624 275291758 44428316 491729956 739404468 622465771 594894144 66853548 783909059 88608428 496662158 403836393 622135685 368104456 535218703 924934576 80801317 475139956 354992380 776194223 303928938 147299760 271650376 991186222 198896979 878619036 520405617 339701719 714206015 784494870 833038960 633931976 815383073 352327532 992086272 230919792 967022596 512801911 125372474 36027699 142508892 121610959 604128366 382136925 931589463 353447232 230050379 998328952 33028830 762171081 525094813 961480199 773952865 636536526 788888762 344005384 134095653 152369857 163422151 630617992 104933258 747267776 491159448 371386986 230971838 882971094 624407091 59015550 729416015 331789180 19113168 898114556 481766508 556147302 127920513 222978013 867801041 829078539 352507409 744526156 695759499 236148812 664653565 316645633 228789015 350461976 378409325 749019702 86322875 807192339 918257854 107337335 375441941 906480547 397689003 162242949 695466369 791715399 999545914 799774981 881316206 959568963 554562619 429683979 578063701 555752176 935261941 140682361 888240283 612556998 336865261 729275724 604795921 53422126 672182627 718670015 361725173 440435560 950400551 334354273 374878673 699824398 941345448 765599765 523305923 561203033 741074336 148419038 765563968 755951116 720611672 711624421 309376528 694399879 170260901 272369173 200097925 304667957 208414913 950476040 561770685 590896671 666335179 13614319 530007743 855691326 221609709 787653527 669782150 625691970 868703082 491570766 965710443 655003069 605933188 18138899 946137914 22808916 833984846 674218117 966127882 877623614 996403583 148174318 793025818 696304051 99807304 688047699 260764140 417759185 167890070 989527723 981385827 299478315 5476662 824545865 485057885 311489155 648627624 223528626 221523690 230671538 26765252 988750738 285266063 138708852 494370552 222790548 317428630 696598218 271025182 888071895 245094135 532262102 2554548 825540570 41729278 441129858 427704568 703373116 340947090 352390863 379647281 362654443 914533484 634599397 389466212 531839925 508475435 350807393 941292636 651575367 7228065 943766564 91778741 923834913 475337203 834778244 152759734 374582670 246101330 798801239 693460975 315866585 177022496 363432281 414032866 798660336 826974832 300226174 233785445 894965227 985787143 195939166 755534374 428956074 693515688 7539014 907057028 125116605 195716789 841523421 117827440 309513326 684408113 290656686 996742623 505068113 835706236 38900525 187368181 883686323 542397550 581351152 662780225 457896407 266946668 707646635 445810455 17530945 201165533 767016341 134030878 944507254 250567021 983354855 145368844 630052709 877453224 443633283 955167486 654415852 779819640 522687361 886922812 279998246 991217885 551273084 126017191 490261190 300340961 538643989 280965452 624018170 247698787 4825609 525669088 896716560 627101087 610457106 406404072 546592014 810906252 949817842 197903515 488727064 626545117 706177013 703365075 431234928 291202004 405605138 955910463 788069141 919544149 516035728 625315114 872124000 422849385 489317349 549282144 638681963 285411187 334197788 597081491 49365891 895898356 126242751 783646447 599752903 180622494 19740049 916071917 642948594 175454856 757886916 766734126 552584161 624018706 245689581 870894825 934920723 805866601 355107409 447670082 556236179 381771273 534158611 281376946 428959358 168441333 780311306 337989240 178529207 721749974 320298880 20697776 288865018 432904205 632105205 171005512 440265000 806763640 7842748 604844338 375126232 873318220 463651615 404975357 66640139 622572857 109913118 628051002 197247569 976400780 246549621 635199797 799955258 797794234 201781015 67492019 563146174 982026222 67416844 536388127 224184662 994973584 205078003 939979929 204078782 922315739 410825086 317627061 352505396 527566505 488042127 866066238 934434995 905920336 548921521 94925744 118994366 471397156 146782029 548781324 138390810 763085708 872292761 203309602 355603143 94682771 43978931 721992038 84194999 150190434 451893670 511674971 848117920 270716073 46409709 927695295 854030155 282570165 475067102 119758368 168759666 765475359 528577210 720907825 856376932 686272844 374318106 368881919 993332732 819617136 30161350 965926349 43531230 87330862 269694875 177994836 649220664 76405416 606130676 952444934 895790079 414141073 688694876 571004107 276189570 710998414 601738571 83244509 146055831 215865061 635675523 137032845 942076654 365600232 320631865 248258100 395626550 995030326 184119272 165228243 79363280 945243649 788951536 316047804 374440394 999054909 623822576 136982388 898597253 797753863 709922862 572979531 126522240 840876941 481631975 432099693 692772413 240549979 850940581 668987459 622828888 723708159 337862253 161810427 310287554 171846679 763575489 866458526 550223576 725366539 372664092 420253436 184345053 580514649 95792346 313564398 160532234 626255399 490983695 670561954 742249080 88194263 180188735 310596356 436198340 353579309 91453997 355308872 937264262 874761902 228350932 219279966 192172839 809313263 834476029 172320482 245216369 390578243 541022137 9022044 928313034 205830665 281835331 589082639 843506772 368109678 888464514 673931796 335779259 516776676 948890439 71606320 987974025 993650730 956379012 378781114 874525272 608561282 856596749 35526930 316590254 234582561 828260000 800161037 647110216 732629707 884123427 881230407 241786319 453722246 616634622 757835591 849520599 727776724 994146674 131047574 531473590 520607327 74464489 855562504 397286251 894711432 462258060 162645323 40690953 503245332 886904655 85724631 776857427 726841369 397789476 50817494 353163134 539791874 461984137 182441996 825512620 741231283 795359136 419818940 208132792 556168634 156171949 693379235 669501565 352990549 851662361 806737723 720455917 72982223 35844121 247492583 718058526 400401866 447498241 414190117 863298856 250854106 886427545 643728816 84981056 137888314 815899481 362444235 681786976 701693111 166781281 181322363 989101311 564111082 190457449 589915903 176279737 300672662 41416895 814735530 836428151 452884681 388731888 453770516 617678365 369523278 869761641 63289133 917389492 781443597 379074189 185287460 802457014 351871009 259893245 116043214 31722589 153335603 399312475 654155093 36100862 494819400 173411310 356718886 589299979 945456961 318109321 548861912 176366491 591265402 654087458 347988921 873275495 644812848 280166372 377400378 415306668 359193447 157413991 295226470 736231792 108553952 731081439 25989740 892150534 273688932 10852177 50200763 220915993 708293064 305876731 268136617 106939951 884651535 936126108 17387770 930239806 13141288 68445989 441015353 375698166 802116223 332825936 29703225 346582097 10962927 925829552 312287917 63162501 611737161 100276964 645416306 311372067 940648766 356125803 984133727 261835264 847780450 774153620 871835879 98733122 236240107 900787197 78438595 962257570 448560285 37789576 623057888 230913347 176311359 663346525 293909011 180092252 659066232 993163954 152470098 851573634 931707436 473747257 945622501 560451881 437501537 535649648 521116768 791304821 220935976 503777988 180008094 383667660 871170826 176313339 139886997 563973981 615829497 153910943 8217620 423441413 517924928 566984911 308031655 950163184 796555828 830043635 464295037 256190507 537206021 364014757 414150585 449880810 467610123 676311838 576536256 301572210 740541412 25521798 755165752 304024727 338648488 795938879 95410971 476749859 322467972 354374573 536111251 797983758 579886435 287950393 199373076 388559355 382836807 945367929 239231829 164533363 176823420 942762522 667479176 47649716 145206158 524396234 195499684 716689136 975390714 951902358 445375506 213270 255556624 845378498 425754431 509156397 234903587 703694521 300980464 1893088 609217588 561846365 73553364 885326413 958294345 514055867 797723976 411632005 284297725 374472288 526825551 917523578 527476215 879268460 759141813 63550335 983474132 944065806 947201113 337464756 104717068 269540153 207886806 221806685 969026791 773880894 667666409 455006814 640590335 201757843 570062493 590138266 749372067 443544801 680227833 222452344 108606739 884914696 99012209 511117635 873165810 927614093 378917423 900175099 940011946 710678967 458861834 699964727 578124799 844372664 117614819 624044704 190066636 228862535 141386037 662539142 597844407 755425606 866920711 734179770 927342467 244990400 991495865 177963917 967970781 663938752 776363865 922086645 280254452 517757362 62700688 241166010 476769744 929186190 274208557 387335378 936150802 612295572 716644467 208952553 766581913 359169697 84371636 101201376 715168477 685420547 153062772 979783442 707260028 45868996 649071854 564329357 14443015 710500655 739299096 735095496 719742521 692521836 151157670 639233705 874302199 369504299 334816976 650301426 989088411 509052509 404406776 262398511 173388528 583635700 809424627 812555619 425719199 393494812 639068675 744599717 200237904 367827433 986155361 990007658 860626521 891875811 463236759 325856468 15872075 173997509 840203925 647474235 55022604 894194660 447712201 56393569 559135621 790362477 832413980 907947636 797018404 352337907 56938693 570347468 769447538 580255192 70783977 616619819 67474878 170939648 130755088 383215338 120601800 263374967 478842892 600280940 516311088 485635836 374648300 288016223 386324054 375479858 621049729 664750404 508063218 138286946 3644149 966618083 120893252 409776308 153591900 899034448 575295813 326287167 930233858 24771618 421021740 487028990 629361821 750463411 807606378 604988023 939621004 316549714 517466181 40885574 164783119 944801826 963697160 6577700 19435396 185052638 182464127 639651351 852479354 912785401 243674309 704322508 749192761 483887337 387985661 383940952 995399015 987432083 727690046 616163872 77918773 564154379 555883194 542231479 85788750 535864728 548069691 375483894 675642727 308662479 88885666 448333923 839062119 849269907 189894263 929169677 195466906 572404740 604219534 833167999 13393066 343870076 13569178 525516156 251013565 13114913 869992975 221285382 882636964 653289637 505550516 421581790 287438281 986741531 475754573 834581669 23299184 773079558 479870800 235684651 68088961 619830871 584981041 528302996 992265159 143509115 100158174 550916592 851607096 346579381 744767561 663538610 81462143 26419146 671690030 261408338 734075374 928911698 935283627 278797504 97379481 106114548 303031421 10246340 939532840 342229392 829767435 749162257 392342876 763673650 677697425 975739064 88028655 222053367 73499846 903790659 297784085 400239707 666450284 705733944 956508399 659984235 887883281 260715202 779563312 105281218 958251313 993718754 278038474 433301341 565835884 958979451 18972927 604957818 444649794 458903308 546054591 33165614 979631480 820314932 216106664 454160707 545641641 257382545 663551042 638792295 860688073 299131627 306450932 865269787 62428110 595695919 547054522 94743275 897495414 471576300 136848148 454902390 781609250 617856121 751273759 397544125 609015979 365968431 747650013 548619001 729203918 975417275 901656453 270351818 258448577 772320396 641489877 727453135 622652440 286903497 733469923 284496947 204135589 315000255 512151726 864827738 305864732 263156698 898830439 667682281 649901061 906924412 627532582 15248907 678220476 236901801 634203206 322210273 132732909 546632220 439155845 920973872 213259164 921698564 485445745 867629637 965968403 700665692 761152124 478368554 710894365 482496571 465351204 861828712 977373938 497514892 306052946 765110887 746078324 42847875 718027548 465134100 327755625 977492448 272077488 149398210 967966447 810625782 675393097 300623000 122504719 599462914 51381333 569254668 438611894 60134100 365764357 367485306 332983300 389573654 833224582 378785098 359022320 559372673 111150901 153628780 770221376 703842223 488317502 690973845 438564209 237731759 791145295 903714958 973055646 410800425 676011697 556778262 303536127 543598874 928097159 408330966 698272743 328383941 310853900 634433045 588626874 532268392 942496228 480255806 780047932 167412386 535711889 770211559 971219782 401195480 993736933 867398953 142754242 146786395 432968807 749731044 939245046 717673266 130430885 921584167 219314186 550763269 168399722 349173924 486550355 7933715 706346125 305172919 754941595 14664570 786983515 959243175 212682951 938649683 978640414 545750381 929077767 969105947 131144082 682309015 815922212 758095868 289017247 689789642 537954177 336129889 581246074 865135272 611053556 989631352 87192171 924349454 341069240 586723172 182521560 97118996 348114625 105653489 447375560 413203103 315780872 286045107 606491411 505748710 149367820 209409324 752386763 263428935 854884143 143561906 379488726 700574876 390709505 461367732 226142906 225183383 322275093 327650905 965835638 159144626 217627545 510247579 296853277 526182189 505332706 441549059 878329210 648779887 33895606 930770683 782581729 788376533 844279647 872854508 824943041 135087213 170250802 73538813 482386743 956801871 750558376 238424611 351921194 521879512 969806146 583802667 248146421 753427574 699879198 947866415 69915134 247805519 103963876 633048980 258238304 327610171 384330961 316988567 913598072 663980829 287301309 865064551 387679681 418990808 408345717 104276519 549691425 643684138 734046280 917808298 323157908 10055437 78972363 337167397 686454836 9998836 854102651 386118933 778522729 458099602 592726071 479771190 888702785 2015312 875976469 613692225 141303263 365193254 918454664 163357580 111956724 573585054 592220843 989182187 577223677 313221828 895205792 705746313 902906401 279210210 791601020 898957611 89539528 498885544 948392636 453564764 4056088 855181765 885138145 312019947 566310357 376737660 592079998 859774763 319845450 266727368 680507142 462056056 47772570 70552298 946831412 389676274 217901697 255197568 124795397 722011317 603227893 305338440 958330240 450864577 955674140 29395047 174720893 693619235 84366561 519279345 190751482 681405190 698965971 943864445 536931609 605551781 726688016 673429368 404721762 760231362 293137308 325680472 384518901 341801819 470100576 949076841 341769935 12147614 864802964 39245229 996557995 363102092 105027994 216501007 94216878 672916976 291253114 829921982 357869542 365676052 368698324 496330988 898871547 708038285 336982526 652957688 839090300 307477429 887531034 4254798 54808605 352027899 64570323 366177920 915214272 203062882 315400354 690964601 536673922 24229027 219809591 982017551 987901586 470819905 248519904 907108167 1339512 387400030 655553531 860342400 165845585 275609575 839861069 504607174 935393630 529472203 28515965 593226587 537025291 7790149 58897072 687365910 729789809 228730452 250915978 430127110 408380560 944298279 501117440 456967895 326863015 944510637 268519445 833015342 661916666 647051992 517933866 413711014 394470535 274893716 952752816 642588352 219385332 875491785 565448240 564303746 704907971 579771245 315918174 848972077 282368492 867676714 753740038 370275988 777850595 964335098 555942997 2113749 816826001 284456070 51856763 623251796 319555874 322709459 273670324 961294576 580826038 624346714 763996518 111283996 677045035 782001740 885867873 642117740 539672525 566203716 315953447 358557202 390435176 607667520 834421549 606131915 189200855 245525706 357836540 962496722 287561553 815261383 293649569 12459755 603308336 945770665 17929584 176379867 201247867 349743886 112042991 21912362 312390299 853220991 863117625 873347514 893222514 210045373 608855748 253522463 602942233 921624691 957163838 568776805 47140395 120552693 170209096 895484279 854894560 805335680 663999327 684001542 744781695 59146084 71366275 112909798 622389407 814449371 618543946 225459102 441857984 847517647 919760362 88500047 895743977 148665121 330574854 92019331 846448811 665736185 796022485 118924193 767222483 513111607 298498057 517738448 650270219 107396851 299070094 677327397 901025437 337474261 579751562 4761072 953036175 64692904 993740825 618377545 614242579 384714113 732892056 236372874 981092412 394666314 892209361 476580291 641543495 179531839 445406766 659463818 586875394 612811392 792626338 245969604 328535811 77219043 168844706 252398568 389691209 495898194 526984150 279508802 762722109 826185700 256302141 910603957 827826192 23176605 712957981 942375313 480476009 411578748 821501651 386766309 583701267 674805769 964710230 701382900 277445862 346514264 31631504 383707817 307007635 628650774 672384426 83517172 325988265 883220292 79585977 902411872 291358408 913427762 164362907 831139826 834281276 306217261 485504066 802648243 644498072 190341912 437140492 464142578 25469924 523401117 468094973 612371454 381246600 637426231 112020148 567229430 568076466 1048463 620986008 126513161 402950305 809057427 560720204 416830305 43979767 592009654 592021873 699561671 802925680 818778565 352840444 300686444 881271376 890530317 933929916 206040915 935952340 439082364 4717713 229757066 737994735 147430598 476276502 924383679 711827020 214105580 285814780 79374994 875876472 137678603 596655979 5270207 145464340 372074011 79390464 104592512 61132845 431099203 905462069 211318064 356853747 877124151 250109666 993793665 443784801 270843652 276054257 684374981 837053263 371676184 370121185 199514689 519765258 467009185 514900417 354712208 680889048 752179348 412512843 871107871 543283483 912728869 655107991 140257508 175278722 455702510 755083325 76689173 431908727 936794754 813553976 968191005 684306416 45082641 974496353 739055242 117037013 122945123 881297295 368806288 586457633 836492115 905367058 279363877 185002737 432675338 450256433 572398694 155695087 475079813 632940252 437235047 494312888 266118005 895664295 534673961 899481848 926431906 172885966 900376727 9238247 615205304 942578240 755553809 410536846 652263955 698182813 235994436 132546261 454358040 994269854 542310414 211400976 302096974 408069141 535851546 412001250 853162419 498415270 614436987 378012801 131706121 210522560 397446495 288714534 913855887 933060072 929988517 204423710 342179640 151157572 252721002 898594077 184091814 713184840 424926335 908298554 66950204 644829569 305598964 10332991 366700250 795229545 399699607 469990909 658956136 575957948 40794865 225286029 300313671 252598492 687173537 605796931 97395235 751273256 775895623 215213302 518856380 829219730 553600216 738978790 666838956 354564566 454412072 536298595 896496849 108713435 601968528 585941580 596827475 356437874 905790089 646820015 297786559 732410041 821178254 648242916 675964785 273917786 490462983 251746957 458544304 668411129 640333066 664304446 820965485 576589876 3342473 649168972 606361231 859129000 355931129 549547091 702591332 190402615 823312989 50688527 471064365 704832219 791559567 396968253 932657718 288963990 903419111 874148694 458411638 944244043 480676861 999606155 434739561 7123890 578619631 328887619 824986932 343287088 581366388 938453725 739157421 236914351 889648326 445472060 736215377 300230713 850911224 410001784 903999629 846187923 286793225 696143254 202758346 826704423 592887160 627335018 119978712 315188538 994077045 948705281 943460229 558362277 356406512 903331721 541428993 894417960 775130242 745702338 646274929 854446779 786608577 968869481 240173326 930112898 993198050 956644645 596304773 862033111 994320846 896521308 430469274 972276704 199002704 471140461 822637775 878882693 957734469 432444723 56697793 677631754 22508869 238904214 593252878 564802162 615102654 205870540 949220859 739464739 610165860 740404491 540571954 395664649 347740725 722742481 744203608 60197342 576782638 591535976 95333657 152819981 871025502 687424035 656988361 147545923 859457417 36394098 193486302 351931003 529725912 838032217 210043945 920740631 911914181 968212771 35525625 901729934 85828441 149466944 351487846 397234187 579552469 289551631 736936358 576416465 181194693 288108748 222816408 968835798 846299504 785319826 982284736 535354655 432478967 519875261 82677055 175097469 251104854 897647029 456669682 560028738 556450030 757691980 306200959 852123741 157349124 364893292 858180805 946938820 564696269 593358582 168099303 398136788 173647626 478931803 372453007 955653891 329070162 290200148 936522364 354824236 253462630 564936487 853877809 748148482 73542017 345330450 28947907 78339047 523479643 532433866 38008789 543714027 925934222 318990774 4265435 878124279 454679459 600233662 288506765 712157294 134758769 321665165 604394858 125706713 894296915 374172101 202294173 218751084 749644487 595363338 699986341 466545076 589852568 200601824 929008463 347126286 489839006 197075054 89866879 877177244 612818393 526681552 91761862 559593215 601969667 213150812 363074623 633037117 200528763 832268217 94670091 454016236 202691656 432120661 991246661 371886257 680916074 230775383 531637659 749005588 132288017 890361612 962445540 42274801 360468641 162973135 875533838 334802116 714013524 840704250 262428611 368495978 552775981 234573582 267438372 22635240 960994086 955845557 211367370 504547055 56644036 434161476 499933860 873581773 870037851 576637507 309288813 487769450 19134081 959248104 227046861 899100043 298242709 418972078 835046361 767979626 706135916 515557229 117030034 948213630 142904827 695650127 145398830 354601064 343254717 301019142 610218222 970657576 986814086 337916610 866164492 789092076 420408543 726519535 975464455 620138039 976703792 599050951 144571032 146099925 944816725 38630541 623776808 785476765 799619373 265994467 704834958 156182994 118312452 385202783 398231964 291878685 372971958 588851951 921424095 748019950 615331524 663673675 343735344 42493712 762003524 234126694 305535038 764343391 941183941 862380931 296586181 970943768 565508514 144077893 332386476 995477675 690280098 506905859 148849225 353953541 113621776 662947769 477377891 802661713 104293637 996106809 671188801 122230129 396914670 714039897 267245037 696345046 940924893 645118240 671735320 97299943 979429860 850251033 845514687 240974290 563042068 219385694 898820360 964370690 922560441 502550210 493840543 714580670 22216214 138458796 517708151 98305501 370068616 2628213 438974298 968398588 872612955 92907952 679327629 888208205 201024310 1521451 273794703 395886055 191174750 814008286 987894003 772758168 683492454 377740650 164142035 249558004 590878619 649912360 263955303 470310061 570937087 891795966 255704100 467058109 518428327 790202481 112825271 801577538 465805253 458456940 128810062 441548669 398364662 394897917 885268718 647815933 814122411 346804203 614871504 507209286 180808610 469917206 967760443 222942786 585207161 477766221 530350362 598604558 277080102 962504535 319426154 554665691 176022095 14162487 768682196 133672365 178410824 437626810 29125 48961773 8326763 627567569 936981363 888995243 653955648 91646976 665064655 927649907 534416239 453470118 878165044 580041132 960286880 952128528 655061560 898783200 460042680 429107121 716769109 643384183 747981248 339366729 893419272 923321450 315437773 138712677 335940883 160861590 797339305 837785002 558587545 459632467 358453064 684866077 321964861 7648921 541015898 819091887 272993173 7736232 812863083 671023866 773466600 973524349 609504721 321455076 355770854 396012009 183826044 754428911 83785911 164983625 326246699 516197936 846651542 539624931 762385245 670889362 97754367 827433355 522940744 105669245 378180746 584134784 806072570 696178423 788757375 646065933 192474486 305003397 593851352 625814775 875775364 987311494 725605897 3604718 209636167 376973377 391015702 389753883 628583231 872385591 254254504 880085222 9642295 129874237 9398579 254608396 887365996 894696146 609810579 534710367 448289553 317110114 849078256 143411793 473255773 790330488 362082409 551758931 671403453 585914560 121710338 190253139 291666663 436210293 512098008 641799668 907695420 844305905 805675828 208268118 236401953 941906234 221991166 774151021 590767468 678157474 452204221 534728458 430779656 785087851 238152870 618304410 897434853 154703660 350198691 29009412 3335821 126193301 501812622 592303525 972555505 403602405 707833057 74996348 594193643 232956188 884952353 310259316 7733168 634267201 17554281 274495952 736868956 123209104 21568437 436748368 731935251 78937477 778202936 262725401 34249617 788962367 107181172 233227181 479043480 548270541 393600111 818529394 959142413 800294227 844815184 427590945 215710726 595246030 255742642 458116443 795454249 809164179 990613839 818796035 643637879 659312652 649056496 454797546 560841157 941532097 466250457 107056776 736469557 217847880 462424440 897588856 18593196 373247222 386759209 805765320 743759261 942230608 585573123 376185699 781749725 200701915 466851606 873505976 412811231 976595122 277328870 857190714 261196565 136760681 481820033 285806472 26449097 662817791 374512548 711423873 671775573 378474219 479887959 700729394 601887543 862929677 897753794 259728274 616642060 813280012 27459316 355080228 990336172 233614562 69949137 514674978 61844986 710178992 157818375 686191558 549766163 545439074 238085256 629887677 414553501 399937682 94984777 393620709 58503553 86253806 844795714 947687655 829008065 815416846 149727865 33990979 67857453 265407606 53167034 599304413 608576486 600229103 755886135 677946660 402949594 997227976 174776113 636742711 821338133 197749535 819135995 149322570 515199066 96612653 550878151 455673276 257634264 488875169 164370820 871415137 689728319 130465476 415336487 211376502 60564459 409706002 536434709 275926258 32087200 336349219 624301089 302129509 452902167 362247291 499025860 435184643 57003421 616110950 82325599 272288481 136417804 768862876 214933821 1157434 931454661 323635836 704695639 881440902 545648509 678392377 25170233 68846336 471124714 580123052 360749092 762591711 239351666 58505500 417147752 743348209 738226996 195141663 449197498 147240099 953972610 138367194 297642494 636236258 807856339 485123044 995727879 347767275 793891770 100977164 312974595 781573162 194120455 587983587 223872634 778118075 170707714 751843089 601925388 771553024 53170426 697217474 969490396 930935537 580546131 305333109 749516520 984008474 669532421 954574097 971754278 253683665 978040440 755397893 235061305 173594865 252433478 415827433 325466045 619391615 298917867 93983013 59867534 899448569 427804350 960642891 86030120 858385461 179862769 969380314 943383955 935524775 803232938 365918699 656051490 870250393 130341706 219404062 200785763 224667946 447314964 271429775 240316953 634139705 692442033 797665853 797073705 220990151 14821056 941868353 852054081 836855083 5255547 522779843 351450421 944341025 635754073 144525005 951732714 495980126 65428919 874129479 584311198 975715430 571359058 11007496 320688236 174292328 771938302 147002594 314386907 226854257 920302987 932014358 282362347 472183900 213559716 780921367 251625715 316813580 446535599 645632651 919503574 616175546 66670202 7699300 535900439 178823649 955379566 489867811 367477339 915780863 640076657 621306519 903521392 68685419 744940385 500208808 335985296 583194581 359493176 626872241 930205228 310410370 266240926 952335374 632639080 67594320 225323280 910529329 449815480 738800396 656654740 678980802 896649012 44851901 605936448 693438812 988536725 79114648 322577533 692217042 750240373 14985336 71256105 902742658 202660255 114694482 7058829 347985090 337500579 771009510 626404598 259747864 190636643 172886464 276584373 842597031 530175614 5754147 400644089 914333432 784976090 910931726 714543170 98506976 182976154 511758345 668671802 944337394 149322219 348960907 635525197 818648408 430599632 25020853 458438711 894255696 43056361 286356448 278513332 437994645 972331220 634202370 994691610 131119858 918602320 276067860 475316354 679127262 889671254 798496616 930882658 923568702 570105523 351047996 139403508 867032880 996094116 27367880 315040547 280688608 74322885 135422630 151005870 120973162 192898971 611905632 448664034 936976108 152620311 717696656 51002832 729986329 582756291 197870509 226622903 867027980 960000955 444343309 619141031 603274493 281558555 562836645 389831148 713048944 516305892 870801402 153239737 691928956 285007498 25496520 139557036 279833321 301353687 621666420 889518133 970585938 332851967 144832697 309059130 987168515 679862476 338427727 44908243 721743593 10433165 347896037 451943336 743840754 54386829 790863191 272959271 769285917 873529141 176285509 621332031 735803954 320057954 697648424 249927485 736696236 785148923 908114713 854589161 496267750 8954906 58527874 474110587 920749975 138614458 86327716 372061728 61647958 634199741 691476945 119257677 223418278 66103585 818901663 939550347 823658833 641391485 496345513 894747012 307644021 633449673 102131719 595608545 774755200 785699365 227213925 481295847 310776895 10240133 629938999 390092212 812405442 728918923 371955858 28115861 852290119 59334712 719871802 250376418 850968277 767800266 315354703 7309008 624919690 670623219 815305662 954985378 438124681 806622770 741639403 864667907 177387855 897963290 286970313 790196767 284878348 992340646 707242788 214820095 705439821 152045493 564728459 852745385 69222385 223201524 295168794 115466027 680128611 109424768 199299015 938644823 797722125 826564201 214802763 450969968 264837562 455059129 790530908 958701828 327743515 720913994 429079404 953853364 141860163 600923485 897071464 175691442 101562148 874390842 947870534 627915522 772499461 797508448 990486703 611463773 740332502 569658628 85734972 665311078 421333581 551807609 592312235 926525696 63646242 147090213 894182592 126197812 229297000 969531065 330259256 305809345 222647337 329815896 331043123 160866957 55921835 808072587 311486616 535518987 995676242 60702586 77974988 491940352 629772313 604908471 473817666 592396444 373744154 684782869 825744607 307588364 489685603 242348692 229886765 594776317 123772263 915193886 354705307 581477484 736645909 748769171 518362573 861073456 43418475 470864335 917280812 8096181 944810500 386941109 719066516 177537934 650098990 109278443 941903477 983544960 514952025 773519284 152683016 848391054 729330858 636311309 870345607 380500288 127455895 521452568 786390799 267400515 738591404 493496912 905744214 956307965 586647488 685346068 833210018 145436717 752198319 890410170 962616959 12136788 888229175 897630035 537744325 142846276 275221821 646897748 358160647 140269728 617209207 994311156 676127926 419692329 700291810 808095873 988148554 296461822 945526508 602262945 320708880 281189404 651214768 643638473 234143149 534547026 511634743 88963850 620785489 813745016 385446630 142633081 899294740 752826349 865106691 593007803 34798672 110412051 45154129 43045907 796529819 533511959 153316475 411097435 563934501 628880666 603805470 951260193 177873251 445352930 134525393 96820263 186525349 962917217 545975425 331754572 553753614 770340290 443246042 556524098 184757148 75149001 848441019 915978920 351846145 328140629 895032818 777617164 768511870 707375894 718246599 308502625 616284023 865521073 230825597 692061163 25885507 304650144 81958268 203984201 943237701 991657198 825461926 812418680 330824995 28893576 670731326 566472512 583988122 425545682 731635480 536387703 325037367 137923321 15136366 314936705 662570476 984005665 1220336 390465324 380435274 703574781 780412027 609593522 34760167 632824595 969976831 326147989 881319787 934761834 313071665 874029232 277348156 620593186 632532740 44987443 900000266 12245557 145175123 753846741 571166045 367801052 540023458 869129363 272694707 830429223 362337523 421715939 41695616 511097962 308531921 442736742 323261552 16844782 380306402 720678160 872249631 349258599 630021114 316875255 191744339 352844952 664003910 8288345 195143338 823100022 391639621 190217268 818875115 623185699 815716947 619742656 897419691 300826747 567825060 350259306 45918993 754080858 328892446 376236603 4871256 25687077 70819000 365282624 712684572 448491608 527795918 460895093 422275792 856487917 682069470 297151805 139398581 40294249 893500066 730184916 120764790 53628233 888335931 57951169 375970787 11690498 526726570 877899636 292700898 517988547 561518588 764296087 260533415 100002096 594100429 874255259 681311370 371211750 105939149 424035897 271198795 57634289 209607032 745750193 219492765 936621535 849648925 681717710 707677954 163657655 377923030 91291524 289502451 652371574 296529512 842075839 694251549 833256253 456912495 761243782 385655102 26361600 137008702 485092537 904008775 928272608 821544556 374435052 520480121 121510965 974029102 419669925 846737653 28523642 41550284 916459699 571762328 154608793 522112211 51843510 259116671 500063260 13231825 572022310 825268659 506806037 311276643 350305002 49891640 417405445 974894769 295834141 781027427 823371520 975360651 960079113 273709334 250570802 982533209 18719327 551875246 376610197 748954270 558956516 703432302 54946015 718872058 109570118 438644097 589688942 33446594 29593995 904912788 496844937 865161594 78045826 552129655 912991737 259735111 173039155 251712226 648895583 771753855 923237167 459067609 246807949 566679300 41126328 124714328 72170400 710868151 354556289 100672844 183410492 908379035 226415426 606358258 185198096 658158654 42206300 520557964 890049773 714353148 787937868 489610578 570287936 513938639 132459805 380128588 841809868 384896489 55350645 58042765 759357033 374900647 471211348 127095437 89577811 715465859 256187585 284126745 530253061 842124337 162981033 618201622 762869460 609998109 167099521 659545394 619191495 500163778 607664851 307165308 78546506 798181373 986389894 642189920 789915579 874234709 352887751 119217473 784274935 579480869 105885980 447848953 55849760 479933302 692880259 500698148 5356504 439190645 740969064 407753700 982487217 819316233 78223337 890848439 380544624 368599410 245911472 66864135 261070375 795554372 218011350 267029885 22160760 564274793 136268048 174301450 830137086 258410748 744322801 578923799 505449536 660917529 976284662 227131213 958991263 468982794 662562465 247113037 854357929 2424913 164177649 578061035 484006034 465443366 335242253 911785558 61213447 746167435 958626776 324072530 69027289 393027044 644789111 736416954 250421229 78898997 245303746 458829013 218423757 79680025 16553959 135334758 550967885 399673122 386633822 432823419 716856463 605864333 166921272 145737061 930286219 389193284 560886753 668998587 769242039 182481586 52289110 71249969 11069838 652635337 277539577 724588181 941861011 629461041 449370281 866407622 861535294 979596504 745177385 38235689 839885588 214797856 357910368 179190541 588257837 488358787 238101064 661050060 236292366 440127248 286808334 231794027 294928495 92638218 120442984 917529914 228537323 26572233 83963744 486965747 960272691 613900323 434997208 409585574 366494800 313111526 459555671 469188498 882735930 975578984 713515990 948559350 457121594 82988345 480029427 166343583 735414634 305601442 511731398 517783289 894136121 45585858 519103473 116266144 217742377 423973884 551195218 403040954 728104174 832929335 50447215 133065137 939892288 614037832 87376366 688100551 331917442 705357691 900456361 568366633 303573660 823703623 995646864 816440390 667697291 936233403 889422328 169018158 802629213 722522650 295094646 381399633 875150547 709937269 930904902 503644232 596962516 917970084 584360689 408282909 771432887 221133625 508699808 464472873 12066376 309125901 444780561 476981093 462038047 344807809 904833313 462108140 714541817 516030149 24448053 771009088 82636379 828585473 312455411 655185738 75776458 435954552 595387116 999669324 986435691 254924710 307319926 789903667 541554559 13862214 634391639 648620478 228787939 701926789 38822098 859601557 359616356 465688387 369992225 629132345 250810514 658620594 540536303 290279627 831121170 581524028 873495146 217314061 822692850 310115002 523099344 245108930 110561655 32522054 580873050 750407240 796482055 379488937 324017841 763414780 867311634 44025912 794735239 137057831 25108665 36762700 782468076 819824573 341251411 167063786 332996005 463214533 765954430 567064548 894311125 535217553 396452004 95031755 86844365 577052291 550230272 86077232 309009271 508680663 599453304 946625605 113958419 518207279 24730857 585762743 386311781 906628935 640870540 915738523 686156953 644067508 740451047 43896908 797730441 674683867 622049068 21943804 68456792 497926077 623127109 22631904 895483953 788651620 410432904 776243528 978069339 456568539 27687687 372875163 29622737 631925174 34743035 995240292 678944019 356420429 435087322 607746221 926500207 456478174 660940503 715154117 193908150 4407153 555295808 979214764 556215858 206614983 833640431 585127486 825445269 401033051 692974113 787904362 31050723 874220662 790486367 777160131 568927688 791933096 788927908 804103743 900827255 943136014 101844105 185461063 708133484 519190056 719161973 701153096 977588299 332234192 436823120 192081698 921343576 618338233 631898215 728942327 194239840 35461824 939514999 592317354 465406057 530981260 382408372 6823088 680061998 615286630 4411977 543988648 846410883 675539123 277191256 159025253 939161758 424142363 161722516 303170497 434691646 950542797 910927935 121617678 13225455 99267459 330975227 614874012 19519767 304281061 925061590 128668678 369219257 935577085 585059645 818941783 696880471 486897952 833931352 287807025 875632578 893096114 627262956 567036914 81116321 985322464 920879761 16233303 982808664 255006375 584821686 919334722 466009742 455343050 957535368 73001079 800809297 339155561 144286226 880592157 472791121 838749169 682087627 641145520 481294057 565945937 203466561 286960697 175584657 142126446 339703125 104178904 622180473 175027100 350869374 843764601 5240379 702871558 702173871 482248039 449227663 751241922 932572297 281446802 602798676 684828782 275938661 572668612 790222931 668349813 450803286 233932280 296006135 56879726 251796781 816325542 40440902 779505665 891937570 652045957 660242137 145943409 618096717 345519524 318608050 489916316 652219409 370401505 471414930 684882450 837851362 647612912 249448304 554291106 298206162 381044232 411893013 708955979 47878720 810079139 167763977 706776202 757209370 170299417 535581651 648029108 382336802 583077604 73342313 150173506 810149082 253101425 445270881 553900480 476327064 593145898 236192971 625139843 27672955 859985185 469321284 307540957 343918702 653395943 141680572 256571547 703938439 944368356 590768559 102720099 93202947 761890598 618913422 340278860 772329735 19780590 789921452 498115258 796061986 415156034 501530629 931867900 103503549 194048937 246815645 743536871 798277426 991075657 826214879 499636519 514630950 823085644 939081676 739825725 922627682 920554621 460264684 406183543 574589811 104927345 478198113 753224930 472126088 310387263 757662955 426721291 486696846 348627933 409432988 791174002 714372560 919633481 683690227 285646467 138512150 498630143 173503201 893682437 632838504 72493204 65977221 257425009 754428031 364682647 114975983 519231543 378559484 277314993 936724040 639460492 612160574 755303733 608095156 735430185 32376948 917261843 63769998 275877859 673137516 193009695 145499848 922471410 657137066 852760386 555697519 552242457 701857353 746181708 468485066 70881363 704172676 261837576 733882478 41544967 848169559 949526083 998909192 398797282 386593678 569621824 557036525 804249463 532274974 891674404 211469506 189979674 774393997 55339288 829535924 629129888 28764098 989355435 480182911 912943876 812053911 95450239 966890833 62863406 925654540 169018123 273338281 485164244 780414810 273492289 401100075 875609211 994645566 971371467 35473036 965015405 722219377 545605985 176109140 161177107 887713112 577637185 847723472 382462042 21385209 245417203 435901400 758668737 819732495 473563105 167073037 904803345 534305143 302677056 728309626 71485736 674879060 375118585 995493411 974542154 690132964 557857379 676404720 982308352 207650038 728187548 438408608 167299616 171461279 616640470 490215936 718319416 621569737 526766365 774443762 767342360 850071209 437716665 774078417 767851649 947669433 948629020 699714326 919948032 388125464 985730681 618875142 292296386 904127631 612498335 843550373 493727513 236030839 736378015 58713726 402759220 189329307 398097559 355917790 150211335 816073792 724046030 126311246 758592983 487324161 590107313 469021026 112359478 991255365 738101196 745835303 292429874 38974662 234019116 2663049 454543880 359812417 737583440 886540036 488220077 787394910 404893569 64394185 90169353 84144918 770904870 17412242 237380669 562503940 411720952 905828171 950148713 389813290 934172044 855742395 13975900 808448331 9780734 287996348 708678753 95788217 352046976 277053707 586308747 854459332 352754252 50226381 416341941 130804012 580811680 869934025 604188856 736650060 905149222 160309228 588114624 186063398 44858269 338550031 38915787 872131447 542197897 837840018 406784999 795594790 882303452 433550241 614509797 371066637 56458516 28824791 381433250 489934986 684257663 643581138 779790208 687716213 139933829 533438425 157381427 113020240 498530027 626464636 740949425 546273193 491628515 872098901 384842652 545372597 408691539 16708507 611519627 672624970 443869767 719698955 965061249 210285650 580845711 414802898 403852070 731314788 270385576 26751043 868019127 602833260 398941135 453358999 56361648 60992739 45215134 319592774 610691152 531689733 256647791 558799526 431679109 716415059 223021732 815642907 83044254 383198898 946973657 476891002 783427493 999225270 860235744 632474673 69919200 817508141 229182790 854692016 284685024 777679228 197878452 521434329 822018473 895216288 644590786 445274867 980363855 905191180 124200160 21322878 43148874 461687543 234148716 25971284 378162254 940924180 298521354 715836580 192813019 224658405 32014142 666435745 39057833 816643499 27975547 926321255 202316465 153388864 285719194 77351890 379925667 321945406 896151707 132886400 120871628 169331215 580364523 424913661 838203274 153202684 663523035 137145683 369995564 579137503 110374136 760586642 33263185 989756832 80132402 637022217 653745993 227018765 247340436 868686318 303312252 611492422 678331150 55530304 59337414 578266877 245647634 916656926 172005762 295572541 859116895 531865895 370567859 438806994 39613197 297307550 47098192 690064109 739244531 333660799 188133797 890026740 832157150 456505171 401070257 600114779 936212700 649544453 411062673 288618431 399857015 464406497 868287748 456185661 710312205 531753491 845606202 365169688 107584131 969344425 124154333 674081947 273033819 525703183 132772141 568813071 934777446 901721448 885561274 845599093 607501162 298994321 944973527 427048451 830968895 619571738 764492712 650250106 675056890 176382277 107616251 793428678 479676593 72698744 716199290 294607717 69502874 659153231 708892342 175341238 197771982 347238480 769602324 373906535 172815872 827836847 162360994 850865583 123727301 739224872 29505255 618759455 286186365 88328279 723105665 303812624 897055006 287568381 981271995 7228705 887354827 212759068 314260381 834475169 917805309 281362700 878015362 819529359 595500943 189048234 242741627 508111719 563791104 886117031 456534772 576861862 926655255 243729309 55693335 643709332 164613755 149907127 756384527 635304802 567438675 146021689 53663745 764377796 935302926 364485937 948022565 566369693 915431243 276086240 400466099 296980964 799177705 919264453 100278763 551724836 371292739 918001676 322695237 194323142 619927839 3346683 849551210 789120902 229228575 826757909 424244913 539930886 104700170 127281688 983913297 384178694 393467082 58433075 990099432 30157401 339615935 28104837 745585769 164834703 871477411 370874827 353087385 979704082 750174392 666538662 207882765 319753673 302059768 48278403 704717490 923464743 914722671 780983200 685337062 876510029 196875208 306546771 117297150 632877481 446345753 149719468 987697694 663054397 137703177 111506374 425160089 659345481 970777017 543307669 144263980 625916065 276862662 731406507 163791594 501018933 40168690 990628628 954874093 940342924 320391304 760572171 128936435 419117518 378357189 481311305 337401111 583828356 414615575 507775687 915773822 440221 698607875 34909281 307810180 832162521 722630902 482265580 368766845 707049697 957605762 960814091 699521511 848473440 977867623 480021104 290527665 605633308 281835809 71626995 658840500 344172081 590983880 546053096 184333760 224772691 256936524 404051050 996631327 681220746 391047175 48909356 902699374 686979597 413533120 479574906 978281890 377328173 193992456 815379371 419694166 570246609 459178687 397502985 359565278 471989019 15064195 591171674 490396367 61994482 327380633 410389752 203001201 241685639 232749446 432619875 423035857 430013269 541721154 420190515 49625380 675314962 688834014 787426304 195823888 562142189 639537868 214447260 462123620 937613759 785914799 457621323 371400436 650348805 181470645 658457702 974618389 446338167 980468810 759588224 717373756 205129799 687473345 210192617 57466094 759923402 794706184 176065483 426345057 722637683 188287105 305595384 824066354 503300054 512030336 90054926 274201443 201508677 114486489 357126659 75494111 331988161 153205254 713411509 589561324 965541505 9323867 734071100 199829662 160833719 871604613 2112600 81350477 717093486 893006638 435525379 540328940 8941119 203011924 773420672 946069827 514693472 940006114 411199307 135847931 814287796 383359202 188001387 340449340 2406514 232743640 452280235 512927147 849463647 784997870 395604781 629253886 64400421 230460383 589801230 279275030 549205487 905075945 716885466 356970409 719579454 205257913 186870280 703216684 116576723 274101792 604449508 457215619 729356170 836971065 240834948 128201804 495076722 864817441 606323178 491269536 31505829 11528979 69602465 560621510 965971835 922011029 863718678 77213561 892502074 831085559 998519081 651010245 973756122 775939357 563545044 681023348 343233425 243349156 302346834 631092830 744722310 583653246 76191576 629498986 114211215 715587094 520369951 920149632 910087031 78972233 375002891 68920395 646505001 539606074 848347446 939334923 56609332 57015079 952197452 52029497 287930383 129523100 707674444 780102504 289177075 832438270 553155384 741225377 933771954 43637427 406211080 367344026 413232498 106434650 549447032 721633240 367152945 268231983 545460759 329769418 195573945 571378521 859944591 518841054 609353605 277210500 82713380 912720191 323002667 809841451 761818052 975388866 99301286 656980687 142814842 455844670 187655136 810455849 130653990 992505499 892831542 114258695 106868454 538502474 473500173 544475198 340406605 481150545 933041438 105979803 380858889 130296318 623472578 194918455 660302875 232713504 242855157 822225626 841787669 375301551 971184324 704844073 364864881 596684342 410812720 442608347 964982575 301713749 146249648 839705648 282357976 127910403 73970212 700079694 128560938 117519482 580253628 555896578 428363629 502688655 171686105 348175742 728228027 891015000 491493109 443849087 901814862 952418326 787505492 72382839 343552528 128402255 334530290 180640727 123069387 210984734 963974152 32329772 768737398 416725629 702557620 489113923 17440284 888348738 65212385 905042698 844178258 791287959 565777047 433231848 898526123 642094823 171453778 331175254 321703655 638650665 68066690 237385465 105339051 598550209 465137155 153524994 587148895 966740164 412969092 882564966 730767552 404876233 955240119 180135210 679484673 671473873 65631206 780420026 825153882 987368554 631124807 625752190 286407071 579457339 315817177 800853073 259347506 274230664 787628002 300247417 464316216 302548571 888019208 518694652 803309749 796214927 427939259 152316933 373075739 727015584 960342719 512852400 797135219 983485094 911533802 431107632 156009469 752364140 165915374 464433072 255096401 625058812 75448324 332668069 524043641 91592738 762173038 373293421 54112241 590233985 884293267 136150977 362892842 335750943 422272345 998510139 796371669 97893713 473567921 763731087 396323430 355464416 631947811 514659133 6441346 14760099 115397119 639998733 124690816 375567051 795736679 98470597 521859917 49902174 524206732 668386151 153714304 136744511 826364305 419394656 435696576 734491301 610297872 993996896 349695632 445101777 59641255 29651016 958818814 505197231 675311423 529370695 417168094 781860559 78469702 545521764 39321029 926372514 54327810 812609759 586443005 816436365 622295862 289288663 508022013 363748881 136603481 881666633 576828142 423812285 616003912 94064688 179192826 284895454 859370067 438783752 153531778 74225367 955423815 927055274 544463723 605434046 848360264 574290567 194458841 177818979 34427218 602251679 297340661 139740463 156864889 986012050 966656749 771874512 273434529 776265837 955727569 750939288 707358773 479731134 279104434 81208613 765061692 330548281 75825810 291626523 161905152 518949664 909599016 732495720 470858084 112079536 846071538 953821959 176709220 367674838 659767086 553882470 608855432 880033794 651786028 243763735 839857396 162051411 621784094 356659334 521489590 485368068 366440064 462684710 692474142 193448830 826872188 398438035 696608195 820554298 169133998 411311000 800464707 718940795 455746705 975044422 231241209 395200152 382505776 274408671 482794010 147744890 433053391 721516631 245070020 342380115 528809019 917127491 507307075 598322342 968755959 97948896 940390079 240459487 624526505 68072589 726637992 633634787 194562831 153222018 768741360 937883851 425074612 817923135 78933605 174779557 985805275 560668186 823255121 444868034 55916695 472110687 257249988 618751968 803075024 349804362 940102519 808800782 992368283 9057020 60226110 328034336 334177336 427625118 618555446 887597505 558460380 689277714 700194158 933873189 185105624 308419633 647271226 995499179 188975127 809775699 157059020 803036910 774380948 304907182 569705742 165334841 420591426 285789704 563434018 7967472 478449686 410314926 323764823 75030557 44216568 329194277 411295150 516860470 294541369 781230546 736438895 581021153 747734164 115152735 814200627 349527566 77138654 478260843 422000921 780610356 866191536 682821736 30626039 801457107 136454434 694595126 487859849 319226213 611072642 812334662 357350036 877058036 894360077 226350924 317475935 665310797 684801779 75932669 253314436 232870840 346406420 481598526 838337988 655464985 306145455 26692188 93762623 838724782 712417214 971984654 171803288 65839101 274913491 699414526 573922070 7116350 533433059 152461345 758293559 375881259 940039559 690661270 320706734 572021146 948953828 895052002 81643924 795764887 496274124 605180432 679095450 319971741 471628441 52935580 693936374 678760416 855269278 902698021 276190907 941137917 391125369 782380135 470687410 485143986 849101497 306258011 224732796 784154883 823207926 812674478 53879436 763279560 689702412 790492366 171442711 629526884 880634623 604879058 900195707 182262440 96906017 992380644 721397726 503500491 720435551 785864009 716239917 506803120 437078512 369192613 398638939 730152195 351173535 537424071 106889203 595404760 835693706 379803016 38973769 206970206 101527667 109114309 946351167 817701925 897307378 607289357 624218731 551625355 251033820 571901560 382670903 754576663 12065822 269430323 866813521 31856503 21895021 651217253 402469206 156711090 400096781 362514103 710976395 855899173 966502117 355376754 713887540 681257926 253259880 284078942 493029111 96686206 983093064 126600032 369712491 226406082 477909936 920303238 166867442 650002925 658349769 917022784 223201927 692046077 29555405 198135735 682833228 484199363 911151529 180241695 828564914 76987969 7681938 672984308 573787239 242364188 524740015 517428841 933776885 343053571 162969490 395117135 252642734 724198985 34986206 808007562 564692133 67186446 123559595 665376112 212051021 267872244 969608203 357661175 779186240 349915249 796118202 819458738 159850174 695789120 375700445 686011172 592970185 747415600 356891522 858898949 548944304 96863537 347181498 692738236 160400634 909285983 894329394 147662067 658618567 891436634 214987098 539618118 378800345 839612412 121951207 885969953 956556073 588536852 327212145 876685633 391775151 335925814 751143293 385129633 358657409 228554497 659825668 232321577 508425225 637496672 773893615 623117299 731418303 297812731 250487776 676757146 607693420 108008994 37147248 97991236 169319176 105168902 41965690 502125449 84295346 719929542 769349575 800253974 525189737 362914559 327040075 574184151 417003241 604228013 294356174 256352698 733426315 635933099 220209406 110148382 324169127 408398673 759490983 576030278 669686036 675415782 229634718 905539234 930202426 868943685 649589805 128676378 868391733 716891077 516496497 727745473 730166862 275035622 933450017 686335895 236494269 651586261 451124444 274861600 850281834 180439578 546321955 127906681 523657596 861389726 928871816 30590147 934858404 800981001 271116892 940611204 53284041 20669099 809373048 115013893 198755255 471417149 215174537 138247843 706002927 648808589 707923154 38459438 462424681 460119494 102357745 96631610 430196478 494135852 681385579 163015483 321329586 480653962 262060777 422239055 210976418 821477338 884427306 794160868 797677893 21739198 784734572 758237160 59224705 180148692 517296975 685702515 713735045 142450803 993197989 114802966 351758806 902751384 489235235 964636148 841585988 493709365 640911541 655980840 850183401 583390647 19317936 261634499 689810220 531988197 670247538 155399637 434095006 552552807 38041180 45293579 44609329 432397063 507045039 624516471 389969214 150421094 954610350 86240537 853131836 206154023 148966040 827859337 140373625 390796486 819439997 377460502 369704851 189808737 78356745 480656357 119475028 737979434 201413403 842432618 617002311 804965005 54504697 505133101 203643934 412471670 873052108 636388358 445268403 294157072 838646729 721760202 688692705 168998066 818060692 85516211 662591598 9031240 483203216 244490486 562204553 338905890 649366891 3987340 873260884 867131257 561750548 129708157 785979841 97758542 188427659 268761059 609057547 608349219 813161303 356702974 323907288 585126094 493983382 132493937 462031851 813493857 572443314 393219206 839169366 328756935 536662481 472329304 163603169 212230315 881643977 607027315 700395880 290235198 319439885 892333741 615055419 551378028 746893046 32978606 416427745 92272170 261372357 704067814 338440547 931561260 155648025 865915131 891768543 431645124 797840341 511212792 961899474 782339520 192043097 395244494 296344040 178152675 434546239 680066475 540284634 932962262 642296803 4770000 216698997 241106509 466605013 405705417 63476005 452650399 566429581 640359400 394234410 73858180 619542417 275975001 396862183 825353127 108237888 253267981 483679154 211306312 721095051 418519752 833695995 468345234 776245244 839328821 24282260 532210070 153343872 998334438 638500519 310658327 283562166 185601255 32061852 444515003 110310183 539182201 982050197 584472466 82546037 957760415 585401333 720969581 216100581 681663888 936535995 525366710 456841683 969919851 130935368 750830354 921064449 723866418 13320355 333341279 83491845 659118637 800352713 363334905 136494494 847015828 49585748 159081497 245626523 922646601 485773598 973491417 118856709 303936529 23291505 110168447 794918335 193602614 737082300 172648103 697584000 333399480 222948595 820469312 894000101 332987165 126843304 944893631 553848793 182211946 738325335 653625817 701570990 406629836 545763857 31864166 478369099 479900770 711199258 915760755 795281763 871628895 957030744 871754024 824218660 691011977 699240114 531705444 367794490 462849744 713350360 922102786 398185031 547539120 123620288 454808676 348761983 715784643 459423767 323513769 568315927 854892630 784538058 594053835 332816701 463871365 859158942 8058214 390622768 582993812 949216614 612540794 51512858 170327516 282191502 862472909 661911611 228325514 148519325 788478439 482524128 720492469 486106186 356170569 357834794 567751100 700145943 969361493 212285992 854797471 664665428 718357044 269468975 48267803 715034271 898749439 889186417 696614220 520513694 75689223 174092749 749460978 392363506 420625589 867248936 203873675 688086061 263418780 834685337 808893764 301345730 562777400 307909843 470074674 586818822 821006475 974775752 714905956 892031743 171153208 568249929 457496277 481004397 87691175 321495312 430471461 261870904 834859110 219517093 205438643 882314361 325199690 439646373 408876088 965593425 778284229 367553214 409830456 789428254 130217152 52359099 328605681 328413701 212821598 604655846 995944578 615158284 807655020 84343060 357381344 137365450 97283550 66275134 924320804 877778031 438931719 868312453 134442722 87670551 997919486 111078120 149553314 803516846 336875539 778020596 482429822 271326487 610149518 674749157 157738460 64899090 225136435 984852153 462294597 390617745 953438146 623629356 622868789 179277808 380894932 885184764 388183045 151792176 932919541 187884828 40820217 596311487 297066977 202185971 39320972 103856594 115236355 356431936 214041580 112921443 434152162 697654618 250947729 634658564 90873421 195783751 288705022 262382194 811129260 163243122 428678397 703007359 937203326 219675686 550449040 717235488 474968054 232201582 147124557 196786570 150761178 178144309 399416613 348841258 300520966 795070309 226846653 874046312 871623479 203118134 12418320 521582411 557243515 893352070 525598988 853495693 4981783 127203386 640709977 228677917 132932132 780223778 84265195 778404322 145508947 975461463 83032055 573605909 321215395 74051212 484344923 502081713 425855629 343291776 384015982 38788867 743613044 599291866 711615533 464846804 528767406 950756606 843343256 986766895 248806082 534618482 978725386 914587771 123835482 1802321 545354951 138420675 993217858 222441767 786087349 33244756 403526802 374371986 585055184 566294614 49385691 964100649 801742934 806897816 519906871 806106907 791693844 854457635 150076249 949556120 302477565 664759187 868115946 17455263 892532781 796611921 437058397 594562357 975689558 146066885 876966454 941690707 471204898 949456806 384154137 17552358 421055108 741652018 994033484 522969576 315149221 489065456 947514503 593579603 944014536 397284339 297625887 743557355 417564064 866314136 103855759 438135552 521848759 721096163 33694757 151002297 732770240 472792359 519548696 309973192 507811129 984498092 373114026 49250031 316813729 671669573 339574526 810383443 554711081 641559777 990601922 838508680 898989086 946527459 119459353 618273060 101842431 346413480 65291517 209657114 831913189 424541882 495325532 927486532 138600272 227471332 738064909 35099069 182450648 491838208 439880122 544641768 82147249 116528599 427843437 339354696 253869618 986980411 680633546 878297230 555401155 387917414 115548760 883868581 565043214 290644237 155979131 591981962 90180046 364726545 331496378 562647475 278439799 337325417 950761898 285371840 111316651 370842734 911683631 314040518 968067701 754886286 434397579 300103360 343568103 29853964 584787098 829670660 276239236 353752306 624371776 19516200 985395863 650348530 969455674 595024471 894685624 956086589 874908525 90327884 99153666 283071535 439192169 400749222 447258060 512386757 472219308 868800437 606462121 937592592 381461671 264166097 86054777 821383173 226223949 566691240 163744704 45696224 950907192 9204956 884643036 494226449 127261991 480115738 212393019 612414181 597056778 146704874 259956347 93709018 315515469 830114347 597586696 479130011 150851168 858086397 181163444 448732276 970506948 225312049 215185863 661881443 335386757 445049327 897503449 821122726 174684478 248747621 82367786 310970040 188386626 334185361 485840223 602923798 315192880 968453901 629166511 579506941 752172769 818894488 948290846 623838247 607709462 524889759 841668700 282784126 786205900 406522020 790149793 951471188 896813653 269820886 752390087 233591123 343279739 989199417 864283507 984795658 155626285 950991614 476599868 105520908 940096002 465074059 288238350 913781007 861556918 605190722 323683016 151583892 680000032 633436779 60533244 276330760 426956604 35585614 854468072 420399381 647103742 690089310 750623641 653120757 497075103 598211211 608787255 862158192 912777949 657245517 53555209 867941701 953167573 905178873 969248597 803858854 248889162 829349326 663794269 327179426 679034011 574894914 758174388 407053599 507452785 611277702 563295819 585983843 741635261 304370969 822753217 690083281 310041425 105371369 601946663 480137151 181253250 290013695 74338667 205351406 386506174 719974837 150167770 973218511 121413193 686879887 365687536 343936169 848820957 746317829 875500741 105711848 189287553 334880139 731528358 527004293 929720530 231280973 693612052 949844623 37288217 732839637 177021167 469045853 69608268 925743853 913619047 846820978 816769245 812606441 36950440 705055444 899632145 995618781 714873724 678207421 578475414 340268985 580339458 353471130 88584780 27790718 629245898 627189638 547957805 400884613 239452221 551056440 514814667 760236987 723470959 38325985 740868603 155401129 927420315 797429659 810331761 630568049 628016011 63845668 645754812 563069109 140822334 984201534 516627058 757278071 189218656 226017985 427885435 308841764 490894388 525062451 60300625 30830566 190255695 66251365 699245440 16818108 506168319 603478923 225515363 102748372 777019820 418841231 234221146 742984758 308520800 776120678 928164359 542532191 917399742 706775423 845962458 848907525 991440152 830047512 63977248 189457373 329272300 252022325 132711559 903864758 40845928 661755865 911124338 148218016 702974248 652098578 733372331 541367344 93094512 120675327 279021406 476491929 284694185 672270916 732865274 875693672 619414673 478364343 625910961 657809948 478989400 772139938 611977080 96202740 409298384 729855219 393805921 580294677 723496670 848450314 546364361 202738077 465392082 966844006 958414622 667086278 287879863 415624386 479986467 278362420 13152117 712960106 958309312 303668215 124660029 793388752 560368151 185256451 983447457 135684733 994516550 927155133 332656027 924503464 418268121 680498619 409346737 58139541 63507881 470322457 767459481 172118129 839097407 121291641 722845242 991125832 213235909 525440272 521060977 593304001 612056611 799386374 774318421 571113234 403807252 851437652 641564783 276852344 923142243 525387263 953250663 863182310 248594182 74039214 455582072 896362628 630228464 773517888 116131636 466109877 344582559 287192932 258955618 391576891 895915864 620107739 975699203 874116758 559703020 619573934 845833123 694661749 902333812 529143899 950072645 149467702 176374446 295609502 840335664 308568443 225723625 313508038 330941598 360735250 417674760 209938534 790499703 240917772 861339006 828735074 121569389 263164249 503487409 462205477 369212443 95435522 20597535 820693499 744188084 980181340 604638930 567242628 410217812 269159545 865368190 70782268 360050001 920581567 320172174 583711919 71244741 816669122 705613703 686181776 557134416 494662078 462061356 933139558 630152984 856824224 612180215 801159595 566151825 7057624 797320730 665342641 320547857 64497974 287843087 577734060 678059607 649954973 403476711 188297952 790424854 250647122 883013623 735012779 977940225 802848911 190193731 580951549 555409571 873478816 877503242 327725360 122198818 452984062 35920356 997981873 175158231 906694859 144371480 380431239 101191813 277465379 423739486 932850780 144160045 454733826 309482093 677512961 555426543 607461451 487919605 40276883 909187074 681468904 842591743 450773658 744092615 102925310 35936037 967765 921061179 275547715 909637226 708518477 555574987 659406755 419313616 76863465 17779985 476899370 496848479 214619273 27564982 419274 540257205 141419781 760577030 316266060 519123558 1613716 254986804 835332959 733172620 607614064 168536558 939905140 437126696 639926887 614169232 674964509 494534260 680085864 959156075 727819195 887810862 565154856 466727875 435852018 154272508 442202334 488968000 875952389 114823036 853160392 149597377 305242684 75499099 239967614 862107023 691698495 587263606 659577820 311361481 43688447 938839044 807989860 897791510 783050366 651659906 98726474 984556190 849282088 477459141 352133761 762958095 407954106 864514235 484803827 240842731 388336307 365562295 339446449 804495409 513996338 200722766 201303033 968945313 742402877 646330460 821035985 970230457 625617188 868414322 100479572 784627085 440030279 782413582 779409488 851897198 749877710 186992673 221263954 29439262 173593195 688326896 617800400 709542319 708913238 836443260 709045766 646113583 846461455 907861685 32102173 104512312 589273637 46546644 804969487 525564530 960111460 252875628 12421331 588850693 180177614 830767461 488153019 424259470 350020922 528011596 370378213 921684231 607054745 268154317 171929216 668360174 718528937 321781678 887655786 560970232 808517842 938115130 365963253 740424162 918770015 408250966 77449184 535851779 934714400 467941526 525203821 659697770 126700630 572658711 62671943 200660193 861183788 837589913 849450593 816146172 926820503 427147251 961914813 567426059 516783532 181795639 886460955 129631654 623266908 852320199 37743014 728391799 677770797 584853191 510700405 448699075 882733572 222934033 901368324 942644157 799559305 344683492 344801290 683520271 406847403 343385869 403072602 953677407 416792421 491657052 748801567 359515174 725829340 149378826 164984509 257657610 446603213 647662145 433299048 762400682 330107855 990177202 604508776 222981484 593876129 822964760 36949644 995581594 480636165 814796860 63122080 526178329 767691717 49266208 491282898 96790456 398776408 655767256 37311624 255327176 697519598 189889493 282996 637723777 138389268 707696098 338321676 115056750 921211995 649101351 686920590 87970619 890451235 804807040 213523779 452141891 776432361 562403419 83401930 343803013 312100671 721167564 633760453 448229731 833903538 144026845 597678943 54798925 382573720 543819881 396131921 9891427 772917096 117956878 643470080 132148357 744861375 467759855 823583279 67203928 646511151 77138098 947286936 572265435 640024316 817647346 144695998 774507105 407749102 287629942 973183493 395288353 80767012 481728036 314820769 521633987 139523586 260402541 848409988 478017110 457012786 451236552 766978645 361551217 710242347 358591236 369500660 716760964 330781746 708286404 666550316 85190162 104268125 74969304 598579423 149890057 511769962 123536238 690093919 853176713 947381081 144997204 938914257 440324545 154594620 897101051 763586179 987443026 379609379 816967691 69849456 29407243 70123629 252953468 925890234 348416780 120651514 297399407 420174384 674785173 179578302 767850999 37749105 398157811 484964992 587660887 237618248 793140588 880701431 528601660 567654736 748825151 627254762 492513241 684622982 338389672 434669779 616759216 214585483 267441773 800165094 939948507 957742439 545484418 624027329 784285359 481233275 526948011 653302508 289744171 389134736 578120436 408094310 740645997 297622234 949429086 895765321 388042446 874960544 395710244 481380427 267036918 206813805 62085836 409382765 830243260 725591949 778863036 746844803 471303852 806686014 279912680 910300374 205323989 445714204 545332851 562837893 606496175 568828699 63344793 866167745 536453124 754820208 496695177 934758238 218139871 459639679 534920748 970422614 193748419 124026428 314086711 308702851 23538562 39073760 678909699 60425927 580568502 108385138 44662909 24560619 977071899 928596998 850187747 245464735 895384687 950908667 761511625 920804712 837949841 118349692 626786891 647414187 437186913 266234443 567269127 990796857 358948187 117170555 686282591 865638308 550813011 143287072 899476163 463792888 745476775 398914474 149569298 417133624 360800392 385664669 813194885 10704912 62774725 676828098 315521779 780313981 878582380 182509185 582801850 712065080 398221208 463793452 120496557 568868093 78657057 515175412 982292460 356798687 211953084 982864043 755954021 546891943 612769754 383412076 773288990 304144121 279413323 516306252 299260389 640233596 134897446 74098569 236240929 708099233 100823264 286440406 965514994 255980718 722257238 891257878 160762732 907985944 164342721 28641178 142607426 871974882 488895377 115371472 271099808 609826988 500968017 229410723 717801802 685950246 228458611 601038990 420113864 693361167 31000052 738616951 331027517 903882751 772708292 272064960 230822916 865063250 114755846 412980717 812607278 824857714 524655250 815412206 69264569 939773063 473478061 708205265 239429416 41806046 93472568 830480748 316904001 572132719 995669269 766995738 391379211 303902761 346246009 919959298 190313004 512574743 27764395 941071825 323467760 273293418 570354541 992324326 968822974 729132042 857148162 123782503 652847283 394664287 524015626 575445942 888793934 371015837 442133062 680836853 267818185 712061948 55372152 613334170 690404775 885004617 380041220 49395925 889765559 794160317 95807767 612360975 391409836 251021660 796263207 247283791 355339488 568035632 544225674 166532105 495238483 828836422 598910637 969988936 680898858 510243116 987116051 102997729 911871110 490637982 559532571 608176805 632885018 431989660 888320316 452352124 346701951 439615201 597683211 262516511 284406195 396474177 207994707 233968398 152280652 734853505 239571463 454843766 799776465 244733535 157984751 708612017 575989947 275200750 382010257 233787523 537397352 365289218 886303100 385852731 771924009 429175792 278085952 378696100 897018375 361636912 680071466 926908433 790769887 186558786 66255343 463794928 474455731 871465047 845088602 197478572 946436896 747969112 337982764 264671614 300331403 260260927 972556525 874213143 801241494 280021359 798858169 997384114 276076989 404193436 690364257 241622692 575823903 119247785 218053762 108955832 495540211 452719262 960899727 101879378 786980505 289671358 133853310 35176310 603263343 831175963 161444006 93021589 966484321 846728811 992031337 807154333 254571423 985505820 359715327 459818184 727396720 318462880 478227862 771601127 155542137 345618017 23104576 901533411 469690579 876811177 15661050 273788770 165395969 411091195 276241326 404639926 65359439 294637118 889862626 891663086 842107714 616368275 688961738 767895720 664032826 323817064 151134505 797068179 472419443 779060599 816808502 964870227 126834441 164499014 387125301 844689331 727527091 404121319 755110038 258235802 939259519 962174215 293452274 608463947 862576751 162656380 472763081 796452186 215069325 811243288 779473471 553302546 131933926 198419577 298838289 55708584 319929559 496409985 362372560 389637380 620658749 798301694 285771956 629562204 818084574 910049866 864886699 170716828 303428530 910176057 213940123 106422742 321094011 17144554 186977682 238425167 582187248 105510023 157765559 753405150 117847620 736877619 32971277 404015615 713085589 137087663 170561970 913634415 314010731 732250322 156569504 949830284 889891148 792333966 337909157 927359446 120545610 77529625 277021215 536801796 922298816 236608236 387578498 883735478 79300730 60999096 538428496 965810245 469130628 154475879 278882422 606404569 921305660 55045864 454587369 445216197 388897603 859225542 28421141 553808750 769567250 436413915 776639258 663492930 209226572 146357873 162684659 727908735 462659105 99863586 832956405 953739248 719151170 21599386 934215637 698564758 480743445 816361819 637187163 371372289 10754655 551707915 585365076 434218400 462935361 329379381 535597908 367824955 452028023 749844610 347730783 456999002 314683546 881309942 765695845 277357641 182872750 255628098 322895851 110564610 885289150 848602170 411891239 322938788 716879020 890875555 736544203 219649576 440079059 731013283 270762412 728870528 196199479 596295293 957922383 96703013 903925773 859638462 992080917 855130403 546168091 674958031 515997317 86583437 20301518 704696142 211205274 845842812 936067953 805218275 321965966 822150392 639801841 818554746 880436114 931294236 286572863 805460496 652336810 626458858 522657126 180723981 440666253 835980810 116167332 381016149 122492471 574075029 806849644 966680921 399083661 600473848 27638437 849427257 615922800 778048895 1777731 823550464 2759786 514591874 191361964 257866546 219533471 106539089 247865829 212440558 314050144 907059768 184476960 191168413 975689074 795207510 512006026 896286390 423344932 28199772 107589590 853455010 729501800 72677359 707065312 148262181 999895656 439018057 978902638 437600764 179813623 424329746 852958847 779858152 669954219 148878159 109820221 163653357 468690885 114470885 917003110 66923258 144468494 60301663 238016786 537839667 824882469 866056595 83015589 18722746 235788622 931987392 188962871 596988733 311528771 908232348 286729054 552829628 144406337 107860484 862128846 42672029 432445358 392899108 88995507 817179346 677696327 830281922 654788097 355939477 930261254 883297804 238862793 879598955 205190223 747027427 263881771 418579398 716584477 920315196 302784590 391825873 698581763 587071716 552932231 875978855 3364554 114489667 802120714 970079313 947120200 448515569 601007519 385575312 425552354 329358856 389630255 837184504 115514672 289637365 959042786 350095272 193546741 903170564 626749780 19675124 546620539 423017170 189660173 967366803 537400737 807069777 395419433 850497211 225513537 493066029 831696594 457175694 594165339 245882802 842073184 351990701 420051093 708613422 205954017 810965170 834920882 658622363 644809636 491334395 347063692 53425378 258314328 946627419 562484067 854682678 308060512 386917357 914225282 261883929 303056742 698301904 841938884 841915026 414932433 938087982 284231261 110570241 895484968 705282698 240400794 923696393 994515370 910350201 219325091 218070857 955251228 211205015 739509269 378393412 885136357 410194940 786337851 538130495 866018464 836760000 175908960 827617417 198728929 145826590 838507825 75981485 484874871 735657269 940859049 584761474 42667053 1173659 887448745 440017676 337242137 516011950 440702173 926216018 496592586 985407474 369222836 385685772 180315563 236385426 398712553 247168891 910306682 846767314 18855470 584498292 68518855 118554135 736973595 467433989 173574773 196287317 726422145 517016792 717930598 694927995 931634986 942548464 585553103 687329744 954661967 769013971 814919355 945577524 286571438 531616879 375501524 558938959 492448755 633178576 638685318 632480764 221010605 124395384 510080160 23224823 109292279 903608218 214696198 860340536 107871338 576124933 840650138 966327283 141916793 553727832 175224220 602321801 214969409 230799436 539103123 298554084 11446486 21964294 985929815 580701677 904265520 310674292 139621375 639080051 80333172 355283728 674275941 2459686 755210333 979086353 395103335 792972647 430553791 285443705 855194930 711499207 366017942 143190405 760488405 926016330 477234905 325321182 212240849 912677614 31058256 171582035 139691766 284661588 125105813 220781429 536665584 211506980 41995271 600606400 124108210 90177326 269102593 387693436 312290469 758210054 671483837 593392312 90551609 333676276 333683017 559654042 952758353 473525385 352128357 864644851 505216971 372218740 447681819 660576060 720552495 807917416 873943857 366365063 738712152 714102644 689283170 927898974 603857955 360170340 584762169 714676844 907486071 260528908 894264532 157619675 624386264 448545381 173430342 443070849 684438329 520112296 649356206 741571448 582760507 405868860 95225149 508388717 396712425 376222186 907657978 991150983 132598105 690330268 676053941 893223027 918073076 657987191 39885911 807484666 16625861 193109928 49865635 725470464 401901819 992145824 655036324 12103257 826634296 528122619 770448742 797917573 814855690 678839502 56175840 294052875 605415180 860980607 172004079 531249234 449290203 919785673 374172404 339872192 5130376 967871871 397917192 620786060 458746539 859409085 398300063 214214815 35432793 687649568 279361446 566522441 806197417 312638482 867075061 789897551 469003170 534354318 894756646 34087120 480736663 596703029 572572171 346577759 34486111 87251466 125344739 681021939 288462574 523646078 504563551 972612685 477266629 279210334 815900089 898308426 866541542 860871994 813315699 379138382 270414486 946329412 824424714 386344928 862684154 340315345 254947901 18787343 37371773 871524517 41285637 487805981 750570916 636589501 489118198 996283271 854629518 315467400 517660517 53444477 593978030 358235568 64600602 220973550 98009578 525492567 911315926 308234580 682323135 915139996 414667548 582359853 905498931 565956350 932382373 21318750 965238689 116113013 424838413 303141380 713985692 375330868 995685479 622814146 653633319 753494987 336841250 926528542 713619648 389074875 398636758 928123061 928655647 473462833 266642612 163599188 394990295 633014626 12299296 810647281 630712889 380829843 615083009 68205746 546369652 53640974 654483406 317689647 960361589 280786795 618284091 602241677 130562550 817623761 153859381 694403890 887262402 144773778 52405276 298480630 991481982 684086992 857899451 450105983 955278569 487253253 70780864 171705878 784917115 714390906 74730391 418701025 231952280 332145366 537438313 597629985 540675636 821008678 824146592 88820113 539413718 593015983 693117541 644499337 258074431 399839899 941369122 807366246 260604137 154697321 807690422 342072311 711111579 171968007 81579005 937422776 515731588 52069967 118021499 160652193 250071166 521253236 992582091 729308251 795385150 61659905 63449664 608629017 691434996 437066134 938179552 915023109 606083700 253791966 643647516 521064742 916588300 745009980 995571751 588602764 236603084 285972669 719764526 76258367 133363532 189615078 959483625 513520311 481977970 136587907 730125167 737504291 817255488 83116255 106412037 713304397 453396310 434394447 615864210 328503210 906958017 169837475 779080598 873827300 383899500 738921983 153112953 958666218 62011650 909342492 629596450 173999804 258291081 702484254 856546628 947378378 364160690 663295347 78452690 836914055 280188836 324425311 909550422 605439355 761206511 357349494 911483306 919496878 99713194 430186500 423154580 825760915 923147617 807801732 11743412 923912666 18844035 324136245 578657133 812526045 321931498 265685015 884562191 431655161 543994131 571159962 103397316 364049072 540952864 694863446 254286176 940244388 346015172 996865868 132742856 455653448 671080012 113767725 61870658 671854237 905694107 596248923 182295086 722599689 408564196 87724354 126156413 624660185 940596478 440355847 307919855 956590879 100267485 667452857 446695939 714591207 572734198 406829108 73886060 132881978 20758784 679140709 979163451 720778961 405150702 88274667 186951095 536803332 752039084 264516447 443207658 246337692 686536057 159598469 387358559 877723838 501263040 362913523 81755508 388466922 232357680 173981404 88775792 625505014 727054736 980069344 757821163 465180817 71159729 390056991 546979548 559686487 429092876 671563283 489926056 69964025 362603332 574163595 938846079 151671939 526499006 450675074 8690952 534890176 166863409 313528292 371620196 611939002 622634141 599077423 613150499 808248670 96923743 872684452 366667373 190592115 3615181 884053949 208228683 116150724 266174069 222792629 643073474 942546421 774952720 663428932 100297116 964130422 124502288 785422664 21463256 417258313 632690327 913138177 792886959 538896123 386445292 664316891 891884740 190262676 706459752 680033384 961929839 956353441 402595900 536314138 418865796 916305085 503819441 204779547 882989161 632005821 265992882 612048247 617866650 512897987 952803491 783840508 82793720 696321087 930849147 862091109 801631889 287596021 283535947 316014055 849705185 696363836 76402034 939525151 128866528 651596778 411650664 229684904 321538631 958067087 451320183 920458701 494204920 516178798 504570321 19418342 901116797 410500289 969202899 714041994 649676324 700776316 945829076 458381308 249609383 428133257 322845648 365396299 634889330 758002816 514208709 116970128 741699561 416412696 369516960 350337503 319892403 660972769 939585069 142894853 445484860 875698854 792943024 331222762 26305938 872267391 35561435 569405695 608208876 527014277 5345692 418199021 900000872 971608468 728512918 182407868 187366062 359771395 768071030 185095668 615192499 693747475 967216430 433259870 837725105 803520994 57067077 194777365 208920402 71017157 459510935 310593108 288072159 656765912 818412956 820974007 168775472 541473709 789782599 610448275 814885841 17640298 49804794 269292798 862242832 865451564 320316988 993246623 247437660 603865137 287035378 426339039 187937619 689892065 591958477 429763970 500057629 414970654 697020011 100743945 431611648 176305024 480501611 440149254 133375172 891240428 893206534 533367545 798057232 276598711 825462678 363744061 668067865 989484643 712252263 470679351 257180843 214162466 965390027 138822908 70779186 860429786 450375725 557318921 641535673 878099365 711837315 574536362 750592553 128827008 396670890 339964790 69102067 806834818 487958418 283186601 1852352 556082682 581867953 103049589 637932840 99229349 664917667 62119008 590920637 750291297 462185897 113326685 293286167 447267807 438683154 622255244 321910035 36096631 768917957 89853611 18129896 309394586 657102648 634622749 332903533 755513134 468236515 772749354 189304150 976614150 439617678 20585496 760411571 816530708 855851087 431202381 781192125 141824108 925893919 757922496 289708293 138234312 357917090 885900944 805439031 965411198 265979965 822998516 727101013 85156993 499652137 626487499 491112737 449057642 98265796 934453698 457586261 450431548 595762664 334894478 276035728 183851979 303675243 842525063 594019800 334447933 66390771 187008663 340915732 829498841 79526489 590479593 560857813 784252854 898490155 249721389 337533266 18676437 869759910 506821062 89193671 795021105 406463065 287692444 407046049 363548351 117076644 292534970 512989378 205439779 924384398 121696874 526991906 258752565 359856746 909407007 364936135 879897624 249349450 795152920 290598656 230135487 192513655 264418993 337710035 585247542 49844748 85785712 984898090 349440788 218632 601662378 370020400 599509205 262845582 374292238 611873953 602503601 28949971 592447808 28618561 694520529 495356894 330733530 968090850 822148808 267969527 69019398 633933086 508773670 427376803 124416286 94947066 185128552 965845901 781339340 217388229 105145494 303553033 227167464 233097278 724791006 473882465 716782477 829975672 98868548 38274992 222054072 880573296 795743407 778904723 394123764 55690223 512183218 374003861 225391948 403100640 73450252 71504748 471508943 414138567 960211202 944421010 20669521 770342124 640482445 678398941 485982542 397353183 494972721 51392994 150436875 230920264 76840963 167431313 212004527 689037830 918696174 321658351 871676089 366723671 720710756 790877498 587640486 117778214 966941418 111834774 581581938 341792784 121180324 879711107 614979025 124763812 78921336 681507028 819541918 624829205 62979907 398921521 391083988 262336979 111201750 504473524 707650405 42380513 846471744 735412116 835351544 96900947 306061837 227373462 261810192 855276944 886938440 989516103 39139252 41867774 815125152 336179717 205220432 511494208 609719633 747202543 536125607 299267765 294390478 532287783 470517841 706887617 506427942 330518352 468199683 10067218 739887099 441104667 819461452 30326537 233865184 941292250 787546288 499067392 102684472 467098054 225270807 573437315 58844335 328279958 31067442 43438713 887622979 569326101 128292951 350330195 69810761 7685601 928293607 34267985 958017461 314124851 352975417 931530338 404104102 624527102 224935493 570596395 883740225 637779931 62878008 773330024 808131102 371568058 121365892 733945025 417737958 147884462 586761365 351734287 178883879 347667864 992624586 119194653 937538682 479243169 495012281 495966239 49578381 703776784 758360073 364692216 619655344 714986245 46935360 269165423 836759438 721480444 598557680 330795057 17993157 272484341 842226077 295900480 994547133 790522037 560635541 775233586 311262241 221908052 390071224 507330997 420803952 440907076 780253476 717386081 987946321 929886752 810686152 587691976 901613329 423815549 514398160 278304232 306481538 381093479 8122164 161680897 79547759 104137600 620051319 103736010 742733291 322190529 919128037 696512467 324163701 864176447 628365519 387282133 349488070 853123950 173981755 245561777 443455279 153367016 643296610 102075123 852859371 783649680 228579521 466401586 705252431 601316594 559803705 222523489 163278770 470363103 441230719 727028861 160616925 865637365 516514374 561306407 949613776 676479774 73059030 313777808 729095527 108198821 365762284 51363775 376194176 174586778 952706702 976064335 276244478 699967437 151976113 330878394 483613372 909610220 178128769 221180408 958482891 56642888 264561849 660326104 688257933 669099256 91454788 758248033 528603024 669729322 849874103 278656126 65638153 718717945 351510936 823466540 828134771 220971259 339024024 953712084 720628844 586580981 596435846 743604578 553752037 608612644 961632057 39925509 112896186 209974784 817620305 218079808 754447754 137089680 715661815 148551273 143365199 344756036 611238539 536912090 427555462 828425200 589872351 26960843 136334208 534568928 349494773 18662882 348239503 405270223 189256401 403792677 611191273 43140904 458426953 294462510 408272800 683826648 655089107 875914898 955041519 856675384 619942156 183863677 151587691 624012842 181191144 72608166 238998409 120428203 219022627 175996565 123135119 72222331 33394418 991838681 355488678 161095231 927683246 492527588 867998126 615289501 387734493 748550987 357802220 648935558 485267386 400251400 10554142 598048196 617058547 895748359 995798868 619382035 694895594 628090960 372992362 785093414 981558365 167522199 114647526 925541174 218012255 455824353 305950225 941340124 448030506 141517576 638799818 522868778 474664245 189709284 39957174 692053922 271914573 242551538 999192083 632116974 39895938 447403801 501015434 74136147 320405044 350786007 104353980 265820591 694639374 861856616 601129755 240303543 768142631 878754210 934521150 342554202 952312364 750763563 347264502 14659216 62839283 416232204 219247939 842241452 466000665 328296829 202492680 962871084 563500963 366562682 806166453 68243966 921388146 391724293 603635944 802124128 247183614 232455601 288980415 766559561 376230263 475300557 962861035 91698011 712900939 580764964 953388098 781666892 507232198 380245373 933206892 219817597 414356721 749058401 642238159 22518952 307583534 894747957 69231611 355207349 160985870 480628289 776773733 822652903 817938820 151507230 958659256 87851572 166370415 176267713 688762290 736688100 911066979 433536727 137204583 704036234 921912696 333832398 749228025 221214907 129954965 630880068 17709034 848162687 97465851 866448978 836148008 403972884 164573030 348157196 742925322 372976119 696469563 69185490 310858702 340252459 303343321 633382810 476068876 395430367 437179378 108478278 275049646 713718128 533145192 858425999 515880065 649727202 603082360 39041566 806635931 606153198 440397381 497393210 394825678 948404898 936216591 130296140 593999678 694944002 327982086 703842742 278756036 205234864 445877508 448069012 923744789 322660783 158253704 722428749 660484602 589208391 616305755 60735483 180661204 943010980 311132356 716525110 923679762 593928004 391957737 32176419 455191481 583063168 455353904 993723101 70975723 359701648 726143584 293838740 937352375 91308074 631230566 101164043 65691985 75098815 882747643 138001141 145469964 141916051 249097671 60207187 699428167 988066713 727609296 559726827 321843452 52206615 691914911 810515540 165349945 97798527 546030191 339572902 738845708 840068428 385031184 386469543 783424585 354772327 757742720 438218010 380070938 665802375 126743548 25553765 421457489 661940155 60233879 724831572 400182361 237786372 587664099 626825318 156594097 644566992 871045589 155604658 760961838 715406451 306090813 687862284 549628851 252590296 412874086 127606947 398212246 780587382 34359080 334205513 735216694 292708144 858526838 211252123 733635454 957358834 233154084 111732712 268410643 799079027 784739042 972597656 139917907 501659820 235740080 170228774 425643894 66155690 996108994 710308687 48535199 22708104 530807723 394690857 882564361 255922812 580112074 263216182 885553826 284628043 850826390 270361129 44504379 976274392 599602758 829159599 138752026 92533435 608901164 511693810 131282989 950637053 695294393 705730155 810581341 420681427 258915166 909755582 849589234 964988456 134382344 720491921 455690157 419505551 201023041 785649164 592491265 701270306 336184335 573798561 450998214 271328184 831176004 110044321 31912972 557618629 918650527 828522545 767690931 90459658 356845087 73017300 820685115 918789461 525860599 97913567 76957862 443748445 876263481 895032583 918539487 696536128 205241905 944795463 141263825 700194056 835753008 82703221 665462722 80581052 814665376 899386647 420327065 367369315 34841577 540196145 452469369 786567772 108659972 978757649 701683377 438522144 397273901 826877944 306794526 122636571 101895216 429929549 620903359 704159249 335699673 622581306 77134666 440032545 315491557 454654449 545349350 133723073 531419028 366739260 414228663 339465544 119652081 837537620 861414119 667319245 509561627 667295370 743133319 279528304 26708632 227845637 347480381 608425369 564562867 267900226 25839274 888115429 890430078 702946718 477833738 992281111 756239787 491646472 607939590 91768462 41098361 579803411 310213817 641759584 751035403 927987139 227326463 17987737 782966518 328168777 157821635 401074298 669635985 952434782 581252287 190652093 458531603 314868971 65303559 428484110 73510174 158977723 381464904 81940668 75742145 256595437 768971359 674781928 24175527 432647089 598536115 118742293 454228740 335111283 769239705 535640410 726623451 931979683 677237412 521150913 599560876 577941764 909125278 157091214 478348073 316149816 821934875 216449973 169302143 222254933 616854618 446052684 555501911 361916018 751765028 961737420 429387483 113772192 677758202 527342532 166666622 501443672 518420501 21563370 683155777 756666068 368148685 756433260 930744764 814996021 371150029 913242253 239920884 751610546 283127008 871790663 619063430 57582689 244994319 638438649 32575075 71999081 375812754 920517669 501938361 397327134 6781289 660307791 306099934 203460551 176481974 564644839 199054457 916960116 226318904 746762052 538409662 657208310 726726909 872503010 910332084 561178482 758463403 927215460 543214131 380624659 766683335 445188603 635681959 696040064 904338863 336208944 233904972 819436520 471096765 667125164 776071073 45411935 457970221 394063133 984776437 346804435 41224191 227779666 235906418 525038470 745515039 697077346 749923626 805121975 313912338 879441118 723824009 287530444 401548917 143044839 2418059 41939224 757075413 396821656 853497658 768011400 47447821 151200 989051787 859337414 991252751 161464698 74797795 133503424 560055577 360476055 529514196 405674761 711736337 275982239 954215351 689693655 148143350 804144069 455368500 266098683 859514660 562493692 991150846 500164199 286408258 145715157 492642851 236052254 434820115 380522942 864207695 176396956 846910324 874240211 201809481 452833491 839597157 177327297 131064372 577107638 78734182 283170886 726880597 423618960 259297581 131714537 372708031 904865405 292341867 430839425 8984587 885185047 142053212 239791153 312430288 40215235 179970739 895746791 5454293 443845250 499368555 354091674 560710446 4633457 73888726 104884099 161562611 596863336 387032324 335558292 344651943 931413293 383536394 919804927 995632822 438449252 652997714 693899997 524620756 641603321 530580003 788666248 398821740 337873501 573513897 143910307 389696284 442381052 383641780 275286580 575831476 958072424 234793570 104190732 772073353 224283232 708523894 654881698 915832592 501811867 298825118 682270250 239043533 677042911 90173994 15587243 3667410 338806572 937476680 139443018 433396339 52851263 162623669 463363743 715561285 410103192 348582131 389354158 738480980 371818909 667395351 318331747 163643940 285142256 75134554 868057438 164663043 403811309 753078694 616375765 43709348 668477129 327340114 346587918 798327308 673929328 164697984 827969041 225214556 628579926 938217396 53549109 925828534 597375085 852310955 553156817 274993295 22095093 598440154 96680573 563155275 574470190 494981517 912477482 854978666 29251921 442389627 838375781 292798264 633579354 351994783 319277742 560853817 231173351 41785143 823447276 109865739 182154074 387855794 947205951 94750291 98321900 627578902 596858005 892272968 149611863 540859561 242188217 511568447 523033821 526988502 493630228 130263234 593899508 563224736 854432727 899335138 431566946 80177549 935892026 206846512 541364341 147852316 245573782 154319723 754980767 220166769 589731373 473744914 32865764 947911365 662581053 190461291 728594948 724590756 40670734 251540829 375415199 858142116 427932525 87451341 838208145 873453938 882564349 670687218 634501314 441942578 16311309 709125952 393713511 954425621 148686227 286292891 914047848 719103187 79862642 868038439 204896510 604418198 489134927 180125760 809742356 821313040 348290335 4056563 726837508 996635584 815348805 621024924 517713499 335491041 126481439 158208562 834163717 631871103 33411889 403257874 336406640 203195553 51729025 303044907 932205362 802292214 941367991 134529490 569206484 577090076 874381506 499478101 435263919 468126303 225081351 83580149 629334974 981436062 756855369 965773224 356796229 965560515 982433054 587709260 822937802 576375633 163589957 604663134 423011545 184032546 276895342 527841897 845079810 778404306 617932386 831897489 562377755 350213216 335534818 293270409 645498559 676520870 3748032 99782290 704885930 688788634 216367066 917871350 393512717 907619484 212438767 749486422 102046623 813300399 813621089 979517271 167050872 507024715 285492573 675976451 357413889 922972773 956266182 939128141 93218395 595093262 155095949 834034096 913829548 619472190 975318098 133946260 268031357 710166565 908953344 148066455 40352622 733027866 755601095 811783666 477783986 767259714 23048694 505039443 410719610 49705683 204689744 583289840 735475349 845658526 227153788 695970861 108530709 851157031 627102237 94707807 768760046 485507861 355059440 660199 259673339 789293920 386574070 329976406 597167464 615680986 207351334 950721206 193053787 784621995 19088757 993310212 315543421 682284194 796842407 318624473 125121245 109407419 999962809 446572582 310699294 171273895 320318856 18421609 955060488 26098822 134758726 954302388 107020042 459852750 676955744 100144289 409997565 661152482 328944364 169880788 857263038 648812393 13079117 508311083 454189023 4045262 96761760 776473184 566111806 248084506 569632687 812800263 7054392 177020269 62456573 754916375 299253217 13680385 808842247 32897720 444781271 604017570 984210409 987160271 477037449 861895058 937267811 965234987 640551778 533320595 799085105 486585900 559514441 881990903 554205532 332578541 616050347 540069464 308010462 678538851 816419563 577057887 649620648 901135386 755703940 877924373 294888921 775470147 285921934 395748847 560658060 342323625 459963256 323830677 745488530 910932277 796924751 708381350 164091932 623692902 206830458 949558587 223658337 654989964 130234532 27393591 773134985 574665610 189037747 252528803 539676887 999892153 522733482 867906925 754922331 40902435 240115825 650548852 820995547 593039996 548266071 468831819 280433509 631860705 376291683 480876515 36099808 258490035 976261298 924257548 172486162 884104717 594193902 591598386 651621559 258973133 408769322 461347308 150578298 513573642 353728978 725139579 316294128 247605099 290718454 928435807 220901945 885295200 998676693 156637644 134336032 65466592 698572864 893787066 356872374 493535351 307955927 381597356 684749168 323488293 568131563 166179642 188763531 674565766 338394982 963973620 698859235 226720764 953439495 937401228 199801420 599203404 687233409 741945999 892161146 852967993 337115265 301216291 136355076 881670123 600341058 576412170 338601124 855044475 515731154 885541764 12236691 4233985 406756188 24592526 825407573 636957859 590956575 71731797 644982817 806219350 442540398 465999228 672636053 570398708 56103833 25386089 220626876 143669281 558506099 192215879 52370180 911985714 379727077 65830792 178981949 422604406 232463278 815915521 395974916 727956624 30937435 596764945 344987736 522533472 213639816 61619504 318650162 174881676 18801215 715407702 156429919 718966352 44704794 848170449 341964574 804789786 480426776 986828322 768480361 972141150 992357122 630588994 353502273 221252478 776513682 969648082 537439840 692899239 194607133 809604413 759906534 170360561 807839806 317726867 671810668 205681712 499064889 474617517 969020963 476401245 903547429 405561710 874130735 639171713 356349411 307786483 448792811 410481409 447589669 479193617 373423134 530384938 892448060 996401756 831070047 792612615 788429627 487987794 903442053 794493568 529140755 822510476 899246189 118311084 954793726 585850871 437851773 743940708 822691766 42076094 961952926 653234515 900453664 752224009 142988312 605179655 131883705 491382412 490438405 289983263 545931693 334127360 385561475 841357590 297037212 208709317 419204288 159228760 422836546 975437740 105800007 213499756 788663894 624043926 223040159 285894016 789071086 315696659 457165848 465884194 526257118 202504763 319266822 411222893 350098493 988152346 675525500 263530342 378064975 927025058 44889279 516013780 602710910 22431489 358949388 958096235 901676701 26968560 978869402 436024710 967965592 35803984 64231592 11980015 366122893 303768919 474357290 556382482 143140161 398788724 590067977 159493200 588345297 248319053 989695694 864202522 296696358 386264898 435937141 281515743 886263058 819917247 603564693 879141684 104391878 647487650 995713574 80480795 664979404 361857755 255163166 758681414 631888165 249905434 427552334 796493696 588111400 530093404 587146713 583339254 655044088 624416463 837084823 37599463 72041064 161819510 229986124 523152719 715647253 905074909 953314106 504592849 732334814 371083853 33185749 73040104 519175048 505177288 406140521 608344997 507282911 351648506 662545203 539570383 397569168 513563871 492515775 893510583 953903463 861946812 531740534 605080230 97462643 182074818 655799615 53171399 439741080 828177217 91074767 314707843 188179818 872579434 89034018 806019444 718827539 374603821 937458156 801648179 146271909 746828510 107283553 967647138 341683892 662714671 483940193 983067166 273899694 262623692 495814402 902282279 356362453 235974975 146871713 291048321 123650135 957570102 791095017 452589553 265773296 800694167 785931962 270061680 996789475 660923541 383842516 819449030 914774641 838662898 364624022 45078523 686995146 431559847 33674793 959779153 295738960 638252157 197568925 344208227 39709130 207635461 636233667 652078472 240877680 846317038 54949319 337516822 140592873 670455145 558141571 955728598 125036540 412845504 252134837 101069993 481918225 805673063 688744127 120798568 539628119 904965071 745711088 776798426 675628526 761316930 601185871 447868638 610883287 772227219 143560981 459665329 410890744 308845645 140393047 522195853 421731715 613957316 265883213 676482388 243534815 219990308 164637164 914210805 52774119 685018020 627025935 347708397 390656913 706544799 173539785 160555650 66912277 260746075 84783825 405509875 428948277 231675168 187082287 156539235 458469621 480172204 690393927 374053062 236366266 578548215 492328755 412076247 381804243 750515513 578707478 182935899 291195724 282325163 232849897 652229037 182080445 353859234 470545749 536102722 134173194 680115546 630588534 119652972 497028976 498908583 193752635 237503753 228734924 120803377 84102098 708245150 932373510 959381609 247811818 951740631 526674485 17586676 244615696 175504905 405571682 210172888 683951409 12130019 428074004 26860402 86081739 577477731 850977417 890902792 860939627 691420990 829652734 565791797 561114330 913643241 337205065 970595223 921555569 509918620 591779499 708859871 880948852 630109904 371380367 662500566 533238698 552982390 744262777 259423338 191692936 959057611 368276536 90632724 77491332 380650132 128623784 520154819 626450497 96859788 246500689 947675207 806978929 750586601 179278827 706166610 481062715 65242484 874084675 349330663 513768220 22031087 924798978 962473659 86800042 366455673 281476800 325542770 534434346 426602711 431023813 58820009 962263566 983780471 513374137 526924953 109761392 390854202 267772817 394718650 137965903 782524331 49131043 198798370 330532641 76430008 968782821 156231961 912166991 604373669 992142934 204612473 829803352 735031066 521744945 74307164 53958519 451955524 707115699 383111374 646358143 173345323 309210874 913506599 254861244 483910864 305032354 425403449 564301304 464273124 714936551 693418508 271883115 855502411 94355750 202219997 911389844 109053129 225393253 511509610 718610717 640601857 197855055 243070534 453330185 795935315 947365760 985227434 220035327 787369602 671563848 429625883 470323100 421044205 126696039 67482149 42829265 315351189 575336607 236845695 187367958 452670836 161706764 610582025 642625950 359721423 807872620 964515404 539485130 925657320 918939741 9060229 987099255 10892107 268606264 533347514 991316986 606184681 549921230 701297008 643105667 164587733 134784158 359628929 312269821 707934156 440122470 495343872 896698457 34510796 390898776 833429683 909257511 188744541 80177890 967183858 474824133 846614281 934760481 646230325 92592547 32876745 218230180 479497084 575912235 133846079 50801159 595039149 622523305 153656229 127687282 715284347 959517909 131023670 534912399 162355148 595258572 657769344 685130430 738095596 112494921 507837072 15018398 533326595 805152569 483901524 43051295 998827696 608782715 228703894 316656428 269481220 647723983 412158554 309907065 534466979 103640136 712706639 626471511 492819830 36191472 593580755 807957727 646872721 894917629 83626470 187565456 148436843 53779503 235441096 965536392 98693031 444163992 625308737 917267808 488141534 355252499 664982534 8368268 748920769 503522248 811311865 809847696 286498814 550303718 454026794 32487942 294691189 824686104 151384702 757648806 825171902 713255071 829496469 378646065 620573654 448128641 687571019 875942948 249217965 834079613 235681460 571415379 63730089 437829441 539375673 987169590 714710695 252015947 855892876 946334755 129088240 91849380 451048306 224362790 698788907 650909860 793820393 882350033 298346722 449851790 978211472 948178685 194922665 604812730 418651068 369109080 459283793 57311960 663148689 62822341 347321284 144061646 491250365 845313552 70838826 480117435 897975520 700855908 864885123 180317531 29891600 81434761 522830069 741572645 875132043 741170091 93347910 538146462 711442176 712655405 155621209 609186193 680439925 952528679 135086057 83763757 563768090 701426853 717397258 425257556 244710783 86651269 469797893 384645480 540392668 684854026 832317544 341906040 392367308 547444428 670862130 176074960 609651697 379350343 516326548 382713189 33717989 51639668 333400536 561794605 605262758 487931084 879562466 926402466 862163763 966310695 662774450 534054403 82214990 130365953 568097068 435752210 78495123 371438112 128156708 340178787 482090561 301911256 841961173 717692880 594272141 798557877 498434055 988863954 667097664 552024575 71224063 38984616 853407739 753723911 608703260 778422887 499501100 552308735 46664406 178332807 757970495 904155400 313504833 980965470 664504991 859333821 658314428 10328267 918933769 715606445 589499265 6862261 390900832 51221243 752542129 749049638 505745221 268166473 752124207 250342948 954619789 198896630 213481423 224503848 266764642 930071937 445673383 915551317 46687807 580334538 689749028 987519032 360812085 465347146 7408750 717904206 856508854 717958130 413812544 702498635 423398423 819217456 190000108 841701525 29592628 984612164 713903131 218513856 514942752 108799722 77728732 787494269 705573509 72895315 333842075 140881671 750132843 177967720 216866925 477211017 29779934 731801404 69565933 412964197 179412654 972178900 242692810 375596466 744569494 981604414 752320781 932908460 671374403 850826744 54719424 674072525 265594493 82342816 816453357 456197415 313997333 319909564 72100297 540333965 901300280 801688262 712111844 479874473 752196568 106069217 772485022 614802412 542070364 452785874 447573671 146206650 587937751 273254706 27833207 635691497 927579519 900740917 307467151 979198841 321620694 611886060 769274887 605474159 835648539 205043095 22964635 223414666 125480712 441268437 276410489 411208538 32592382 998670625 42065462 601557523 275052607 415573236 70255780 817339791 931780940 916747627 261795022 1667461 654858540 735512111 116247842 966735065 149715747 97833858 983532593 337913519 170929972 125726864 507890454 865926960 89464551 485754629 567018325 93858180 365961895 712050665 375303014 731351066 440841393 13619196 534735202 371732442 24883631 516518253 64915383 86605627 917991577 834865545 704025731 696951016 433866247 446936104 116343461 564274733 861143131 34641876 61116824 536214243 131171426 129270253 650787247 86825326 10019862 521844804 384751620 318458898 307812749 434751985 132116898 57404034 552738105 432247669 533417585 823493901 590429798 70348155 845535234 225871376 885118387 735482429 906649710 883348463 657880218 977419887 485460689 119524541 814078119 836928437 806387601 128481964 170057699 956405650 348553191 979873829 88204850 104360079 323793489 634564712 628848370 518909581 963743732 186239835 240200069 75845221 891986606 252244940 979674677 670863112 665887328 523981344 233095778 625056509 89821120 863646757 639234357 742770592 104327551 400043230 365709918 274554719 247470478 894182163 980266196 418885519 605870362 254778248 728512303 498456712 564011517 631830135 417881735 392113022 394321773 544117686 802500367 646405233 991324056 316773954 289448209 574262589 585998301 463283789 336073744 701409835 383609972 854941560 677763812 612476870 744959856 50629863 124328212 555648803 901766275 123123183 185418370 627671503 800681307 389785231 490533724 182545170 76244084 385216265 960519008 874116943 988126803 322438593 265886890 702504173 338835134 727349793 623656509 141685906 590325458 97703360 21276416 879362042 895542635 333665876 279658482 587208782 54141239 873688350 461926362 147997600 765729974 117138418 88146031 865001800 896248660 432163135 607730856 720545267 652469784 768960872 120144539 938450071 594919095 102454763 27484054 732719097 646043285 656381265 727296413 499837154 834221814 95448842 826351471 882073578 7220853 970911080 203975682 908357242 349856665 706785530 720039430 31576313 679956623 733673616 317703268 520063149 614284898 256460322 563341732 395115056 394041552 813823363 593768113 546518355 442757477 440996122 821141619 959305967 751842563 360055719 490284338 809899545 872317537 396093527 755906781 389202620 569698385 826274000 449162262 960414552 788874464 127034047 77892450 206622666 929015671 972901644 860226563 61918282 572551756 761246346 476039824 529658556 559500127 251046874 405377472 594200487 557378081 127126036 7142250 112388117 547992640 926340322 356670867 320791658 706481881 436769834 984445230 494483104 641397503 654678906 423889945 609995053 699457275 453498420 416548431 599690060 155368337 893163412 793146007 834857320 489735627 100948652 764289187 500759574 371773258 210952782 722648389 10272929 432532123 982260683 835288593 723090211 947520496 203766678 997108515 131835329 372437449 790474269 472042662 647033882 690222622 414710484 768602496 461985267 325998201 456718134 633838301 349696442 263671247 606758496 508517409 63561925 866668046 868507788 79345511 350230461 549991319 874230382 61305396 482760162 961982334 263045725 218047769 934476209 23990576 588163302 114823768 821089777 695303312 214385254 204388050 680679144 129419257 121218673 325473184 18584692 374997235 790869635 592775970 263366027 641923718 221978970 167059387 133056097 821599690 955681290 732245531 662908792 379925236 262025185 513572072 477454625 575676275 599601697 925311496 127293181 171511744 469534861 855388521 397185786 18067466 586316115 270113648 709901859 48450923 757736742 334000882 952450919 968185455 905729207 943607277 731665492 482706773 889183973 394119366 78224813 455584424 543817467 469754522 402090156 849472374 61397585 778226313 705930309 958948425 345495838 892040672 674311201 153406680 624848325 678442722 917673101 678297460 710782392 166945789 637276777 758497644 161859307 473446846 476140114 792471680 544318285 981604960 760428914 356411235 989037659 872977816 36185024 550693275 315238277 721361040 6256096 564676654 212412698 877584749 944453966 40002773 359815005 483399063 487500835 980157668 523814917 140883409 798075891 189724862 68801784 527071056 759250190 808720439 368093071 402844097 124023907 448122003 516226382 915277040 85701334 420325089 822233132 921134623 338936479 836421308 531946745 693295273 601702332 604672281 980980498 63338705 215476495 379487874 899422332 466035753 329903150 154585987 241690534 3231693 395497385 649673794 72577914 660316809 187798697 594384853 872362020 465368176 80805340 192592814 573435930 350101518 781875167 921341814 978368010 156841886 416634068 164536061 484217055 262470808 603966937 728194375 203381791 420440614 202062263 268386985 510716708 171664914 244088210 931800847 159446649 856244833 312645421 540075196 211745038 363212027 604931660 365546161 271511130 418751053 56376746 45156544 287736280 34173545 151683358 253685749 882269561 280266124 70085819 688008583 455037837 792565059 327711556 126135819 252624207 215306257 746709538 677340463 604626882 955461584 93978490 119421032 932049747 846773040 742933611 486928032 281843208 32645113 277487929 29716297 812355442 874705424 194244189 789113129 127223908 82832617 453863517 285162865 587613292 162413282 189484535 476156027 390748751 681600831 832948392 860711790 341737265 212074755 829073545 359565676 949709155 660692482 389225042 225482540 225754544 189201589 729660572 319223714 634676145 303612576 922254224 148839513 21958614 528551437 698756373 884591957 672320916 471277169 321650252 797593995 725602185 392851237 475047063 413361757 256128261 677221410 287760516 575412218 385478840 496292693 136788368 282011026 536128196 25175234 473313797 264935506 329601451 10292881 938234422 771802409 74591327 532121788 436531756 660571186 71701975 946026142 352268934 445908405 237872155 7347489 174724460 277646718 825563386 114539978 479071868 395544266 546827209 869675020 976540190 18431532 909410156 659051193 527342387 729532795 375089998 322609538 372230770 5073990 329985248 453449730 208245685 950768844 600527168 691257217 944371590 419188657 711640162 536589756 168926943 524913014 435543317 504542869 275958769 44561320 701593036 844962033 306933351 448098627 918154423 184472967 985279340 450781713 623265970 924514105 991808889 552840702 888902771 626395961 890162733 348917287 439890974 336144858 95885111 248470531 999810637 801268258 731632769 29967851 166838145 981729870 906978711 60223928 303994826 684216308 501124272 375612590 172783334 471087442 555966827 839839917 746262750 836046103 144736860 248562965 555320734 991099386 72654105 731651741 3486697 197610592 712973629 481205436 889549430 884659295 259079874 684186930 530518735 3561873 610124933 444403656 985357806 635097336 383394309 625300185 115179897 371208123 537222320 613448 385663305 875945696 989682766 168968591 134078556 18447581 69457700 538018144 726183712 564345135 976921143 940883772 141144881 734142438 767105931 211657440 475131720 585648162 925916995 907638919 281256183 801398954 313462511 639147821 475679374 109801466 408357195 108445321 277095791 776652681 530168575 844160811 839408108 127121526 374516779 445984268 975690795 222001755 409650809 101018000 626840705 136061781 350160060 922684767 867549957 473475379 893199522 128935282 745542464 274557453 490598494 712123711 266478490 201227627 801374059 311806752 849143169 530010691 378836746 942424401 543976479 13540801 922199893 519592077 810799693 806954400 846601979 572903731 49683523 766122508 529830029 465647534 29518275 501209264 856776834 276687190 301235558 648031144 514797648 825245654 78395241 624214389 404100178 579340323 991580824 796452525 869054983 972151273 831669897 195098575 835703177 777311527 26185008 828361037 414123172 907340051 322225010 969488141 662907002 490586397 613123417 188343030 592662608 9567553 619677627 102062897 637247709 606061671 510730366 188368085 49296033 872592011 672789737 106856766 915289007 916958307 497933710 473148481 39357994 652370153 693323108 391363824 290860110 503888756 863104608 67188952 411787066 108588064 17849018 10237428 478950795 436456276 828959552 83081781 551254733 44286333 132556906 503805219 633103369 652284224 873408229 669427016 629015676 999532864 526532190 617231135 920309862 333073785 685582301 934687531 258367646 777081622 557193318 164733617 690284403 853463503 579118320 24344807 684789957 775650470 569258550 887498543 796398594 886092937 746662748 68103282 330577750 45969962 621010906 349181510 142487801 411959124 813819310 737193768 383312542 109953280 936888354 755350113 208779943 946318579 386118594 381429919 384671338 277171251 775972903 982993367 721292907 864720592 85358809 556526740 313125444 739347911 64280659 921200760 605838229 361798036 108576695 579431398 210831708 920835711 90295604 829999385 839529531 505870051 253325481 695840159 14923262 280908388 693415368 405824549 804479019 443960596 5721966 21491515 701444696 502526323 367411482 310428980 581165481 236063063 271938342 220594373 833406810 918683222 881119585 648854682 54078111 939591428 945157555 927027746 832718100 676558072 208225894 50048352 855106176 741514665 408245786 57021005 752787629 84472446 222008932 157900938 852960878 645260217 156241922 502574027 293822084 16326875 75398763 742351890 815587620 276764688 95555003 21627505 317738738 736143585 485733718 262640407 273962372 44506919 11673008 334568697 595203100 321417793 678351825 887771047 595045153 90947401 132337821 459209497 370546678 813211514 399306570 22658937 244917461 28038591 157089109 950125231 454467406 491371555 412888339 909277250 478184983 653424807 858052701 570699009 897912955 833563517 300288521 774301412 149147560 326860321 797461227 314046610 500478534 428884696 21135078 851630127 803360919 588375685 811393187 535517381 189700856 336061045 519869320 564855510 552630441 982051164 996432852 396995259 502509387 450620303 561498508 426576796 72918940 369250723 846028002 704481341 998091803 237773499 930200466 769444921 76888681 427102210 755560246 74920602 614148791 150692163 663021679 493893134 369365206 40183301 423034263 156831007 56412347 664248733 422569251 463948709 205703849 399468258 898397349 174304841 157118615 710501375 568460167 496012749 500606042 24462821 694733079 288169868 807677026 138497686 534105026 601549648 750056031 233026950 52636984 223287048 657465847 6082666 505925410 11756876 948027140 325642797 415541490 407991875 114291541 579580328 502260606 431893313 437265554 419776238 786495569 82445745 390277938 649264435 660075203 623463725 570519760 650809673 159766375 804961585 785991243 422541225 410787988 520256285 942876371 680926188 691014541 966172508 127519847 22022455 135424366 10711880 40801462 38107759 551788965 526212527 961388375 592780533 73113079 501131868 199784960 673546461 398460393 210037760 84455364 371985495 65936584 369094142 372638798 598313506 76834503 178088959 488815486 93564789 853294607 650487043 742230751 486910817 221080737 209694529 483277705 280400635 498511104 285176789 65220653 593567814 43170737 577582175 474729234 598427984 517542725 728992902 279539080 796895639 958787441 911450822 349484177 142688548 746694266 453960062 319284467 239161658 970439889 239246280 644690708 106111678 309088998 241569450 390604568 50766077 266479547 440826741 63227512 725663152 604988335 566368409 562186466 14751643 65152233 714626903 689909776 140240754 481269193 55373380 800127957 856306800 923780954 88118829 272701358 381857513 259853899 20310939 82634567 245619436 754488946 857868661 172510748 826684535 599524648 980050210 144785163 812441787 289973371 782458627 521923178 225456255 67025874 373310174 194492139 405487490 616488249 830289843 640663835 914507972 768707105 412185280 643061632 662198759 581055657 460512276 610449570 410341926 763824348 2389200 263717781 98233623 665514802 336648697 331911074 388241934 793444680 323489653 66100397 899473686 823235001 288738147 663532127 30540170 218888002 594662821 637229176 937173967 345072091 91930182 623821533 46380693 687067211 10193296 260771958 369212188 794494675 292787244 507586045 486721086 831755106 403361992 653177080 948989160 545185694 561120304 25706447 822851082 156482448 325230370 732480972 269533376 831074400 272735087 197619088 54969966 973316396 397457912 969048987 497290508 203926789 568875392 757322901 179733343 300416213 980666782 435635011 237158038 926238366 418802378 440283174 262123540 972896548 7816134 485848591 570186424 224288953 678085927 41814481 69370518 346461818 91010706 561929185 263585716 398319850 393505125 423431121 905822962 740420811 137928573 928707573 615240572 318633682 663189931 736656488 174774279 328029450 521692264 7813049 577567858 607064817 48158245 738405831 850040983 560548520 162430060 319246300 514252547 476615462 481034763 116497620 597072750 112776291 416802870 769282021 254170794 552916963 712903459 103461655 974523699 797211295 311374687 150534347 677920840 660329108 837358401 143949839 968633900 376973619 320997845 191507511 738011096 10861371 288192049 928129328 610259474 683636951 334844613 46366799 891666598 942121332 910115396 66844196 990223530 749785712 200943780 36318996 935583792 334643510 791339032 691826380 29639501 928242323 803355286 768160000 607771324 594712389 848282827 32854383 338737571 325898714 290078231 926195925 489854728 277634854 469429097 1949445 859331281 988508659 419450397 562245224 269345680 323054519 22084465 311261833 952373832 822627852 829967626 482430150 227945469 909127697 926227532 136695816 343299537 817554250 596781722 374128698 145061727 935622215 405441762 145574957 943610651 960540739 945260184 90126312 517801175 516783933 470633637 520149613 303527640 127930773 573553849 568238705 877295921 634026869 492329964 509322917 32656698 123045116 689243912 502086018 100467747 877249264 326417191 860184242 303251445 327676154 389876308 496702508 558901074 680138290 134732363 84831531 727731840 894156026 771312436 943392262 697314936 459591721 825660543 793193293 317178328 868341188 37465386 903491336 535638710 168930788 79088695 2658184 556808541 662515779 952800846 827518753 263861440 703195652 79021412 775952509 576428896 940145353 921354013 562993502 124322198 250899480 239294183 174196201 674502329 414929193 570713856 723545264 425065865 170213278 132981617 450456977 188913226 988793488 246142050 618828480 417609181 43356083 222463094 866331113 855184126 761265546 514096726 956037470 960073534 114920748 751476895 156705418 657412655 123622564 372397769 544017469 983340833 719146385 895848033 970045583 331788491 891626547 871539411 975914881 204915569 664530007 896795314 846104782 752793872 323198394 102144360 578140590 580363230 587140064 751123525 424052392 688853621 279169067 2753425 536214642 106596151 264378695 416618608 97098287 492007439 691617191 94192662 812258182 215748966 382607351 545451941 994296739 476113788 447395968 991864223 903480171 776520914 891932242 91641584 936562587 874745320 870188025 65514003 566052844 253559063 940733849 91872900 26624650 250776921 137584634 85846702 244998959 793310884 32645738 305418395 803351665 88003408 217171853 655479531 58382753 5269593 972385929 701041530 509556285 242544853 26673474 580304038 874948814 521720143 189661109 130332921 281693135 477811707 254365649 511591936 800711324 238999755 532128660 106655047 694450829 4647767 658226158 897067536 850326144 240287150 95088485 303817772 633314958 864879204 641646559 920571735 515394456 198150924 650348487 826938007 248310632 446932048 256152987 519556898 402030220 128091642 243429758 40856530 167376142 595964045 896342909 789359142 402342814 595714420 883075153 6362944 92170602 535996237 79573281 133583374 892648439 152131529 832035286 2352623 548530656 602150315 365350252 555090062 422393829 765690971 268792854 346496276 945949389 411820772 400701906 945658258 641514937 387932799 351056819 51819550 724127178 553259722 400856635 140700429 435765659 428868195 127501025 154131298 94902916 233485266 833695175 693609557 113257528 179510676 815257272 605800010 959120830 925092552 323394327 147928922 124110516 721537460 482099603 910530637 979691085 408965124 931527704 921296992 215995737 932953607 280197656 412880513 46968580 852098003 54201329 703839372 670975816 790880961 951340937 503761737 965492718 242239581 953485569 209801350 428418108 810547192 216613810 487163484 261669519 145773107 367521835 653225869 812217056 738652861 399513037 815574482 943680158 718264292 364408812 433142701 942291097 935260768 481815382 411426889 655379139 659773096 536401695 263673778 56596803 990481895 358217415 809529015 40624614 743401979 441835424 622794063 717680614 842838459 131541406 360690594 51991290 963315809 708304223 818352233 848646210 391507316 862347726 897648129 14678288 706031094 99891923 105805519 214274316 733484084 310168930 622374114 798393622 644765586 833214943 997411718 266634310 50732161 146604149 388810150 565818139 884562240 342813124 402984407 344361845 896221381 694413223 361304063 587546095 470159680 891214672 505687717 704443212 628981551 700020044 10995509 356596683 595263399 503597605 163278622 376727825 729305597 187231195 382247001 805314439 143350791 670495808 123491240 819592772 331968631 170441455 805907857 341090602 156394657 861094374 170069865 838671714 216817066 991864201 273952280 736844526 957054539 744705320 581689660 867123304 229743377 379538026 520772261 404661243 920274582 195971215 297631350 863640763 410404622 597061176 62439540 246434970 981698180 900102010 740321199 96862588 178671546 587475891 582194276 706099091 720333157 17452774 213478914 655820474 896698045 418216659 756367075 757374985 387285762 201195112 686288141 815046659 899178196 593566236 126076518 760540397 817880668 531578225 375136713 133355984 73192939 911623899 162193426 228713684 918783827 736986726 611423341 440807919 394533826 645067585 696363004 33713139 271032642 322827748 632180452 422930077 185088348 859457905 902467303 356626265 706329783 645460253 116119155 989592269 351009545 835960631 141888379 946334243 668167284 496723018 556876293 821119523 213885981 211020318 613605064 373472490 9701275 966514448 704863189 850109916 801703318 626391958 61588407 327416328 862245175 799561089 336538477 263338512 961347318 882176221 163225809 200930799 153795824 963485819 371156733 946605517 397707931 674260955 402648136 438072382 966229352 526091741 608230958 551389903 115384297 798023043 953873283 618190260 907731159 246195249 944623157 537217281 305640871 161995219 410735218 334301017 833998456 722943642 268865014 433016739 695952505 765518029 283790102 133231274 650285881 588216284 619293312 117519765 911904825 762668887 111897814 6563000 103115207 152377768 403879086 179877988 107962503 50603738 625081640 781020759 583921020 254043609 154682799 423090806 863459864 730552660 203977765 322876139 965294575 59866049 284823784 950826861 396163742 711290006 564583261 779016462 67203859 859852620 431244604 555858116 109276597 403814393 185925635 96775250 259505972 615119798 182680161 132871953 787815198 981653207 774420026 661545848 909371400 892570164 570480658 184354549 718895150 909401980 186442803 13969194 99985039 87356767 121675653 559375591 492969633 820293971 996809919 772943576 50293668 190711504 225832802 310864575 180384023 582622782 475207397 111805302 755836568 197467545 194962275 533186167 812235905 334596051 392798704 97368323 342313937 734724992 621925903 594314711 135475541 504845225 161470028 433722734 944823537 765889819 986391826 373053775 53056327 978191393 649312780 949944659 861932944 664639754 345972427 104797390 984482477 566468422 523613511 599156013 157841696 837080552 611567798 461935940 190572346 576693074 380974154 572491864 551959285 720614385 427679779 704207283 698888934 852179633 613041779 856241723 546447161 846545636 673523862 787219992 934237569 996650061 441268055 675018491 464164321 124666510 259340514 347851623 956269258 510387907 388562295 407158033 857597473 104455848 819265145 170533011 560442457 960669544 515216530 246327503 341747945 31309967 551496618 614755506 855368906 865811813 175114232 475593062 47688166 661263141 360877979 618286564 574847563 355872991 522826131 920734551 286627539 775871156 815445205 573255043 748192228 154508309 167020011 668086733 837121960 575650750 955968977 245802259 556287207 581713557 985707388 399496055 490194236 619468975 733734488 889891846 416807707 142009583 609734283 115619630 267438396 654258037 639682575 303447899 229427017 201329701 863656934 905133372 450458880 153067557 736942474 945039862 477355575 561112706 417556445 606275468 239248218 179158962 304151376 970873409 999403009 381832178 122773530 267858859 923106649 667938360 539899297 858422577 850695985 890790608 718140832 692429802 148982238 300567256 831079049 460846073 564365836 62479907 974559964 375446256 436104563 733055202 518004857 243642907 557540999 578597853 199831719 150124686 415014746 115071253 902777185 255384379 265107517 271609140 772125696 547377572 999886695 76020386 226684842 632157342 265902618 776510936 63795748 490409549 475235673 479307215 52501737 456147154 213712450 811021238 93377509 767824018 977948580 952144521 786830344 355968967 723674219 159049377 768292668 752279163 407034322 939340551 678834328 809426430 944307139 633997785 753112124 723043633 604956648 416771345 692913560 654842915 445321903 136920070 697585389 290860933 651324143 399103197 296171053 621802651 249848105 39445180 843664066 942387290 665405051 759269982 521183896 981590703 759328391 522606676 582286692 954854531 542628276 183887911 389282916 29607621 400460718 468264345 832320068 261517352 542310610 406034959 306269963 232816902 414131353 756923661 411275717 988628607 323849872 321347586 670918844 958069839 621644296 534206023 700724361 311337630 579610293 415823038 41352409 420643342 335614460 573174755 345643444 848019977 250201830 755451095 241463601 797758774 340103044 157257826 766915055 244966338 488179150 60261795 615943349 714746334 474833632 268607983 887996925 334595586 897703892 666687277 65604052 117314936 233007587 548738949 441687489 297475912 480374983 938064377 109828084 1853193 382992661 516436386 660185051 990356532 309708603 540602466 265099835 316169556 35687833 969916069 921960379 524002597 546325941 559720070 515916082 136672151 595872071 884811369 109837006 788232981 383057602 22804042 970962709 881311919 268522364 317978360 985344430 72431882 439072683 135906707 549644693 459807894 476062332 795302521 872008561 614408979 65197200 333257719 510187676 646281182 228119233 387591699 342533148 720718286 334482642 235808342 7086617 416793812 370027280 426184332 195959637 619757574 16057633 198650797 440653817 193316235 430002805 718629199 636887217 344645245 335277786 914616324 649426178 706973647 370761503 492353576 911268314 475046664 409170794 748870057 118828962 486593500 339912695 294892602 302030441 961450883 858989573 577635257 256268295 517741915 130432718 238957046 528930099 366303807 570746746 261411833 501436123 502350267 818288925 730578057 414692065 896965912 437301059 887583320 902750609 130777037 612602056 673643130 507416681 232563763 672000000 848510159 948726977 720373720 696361404 491068139 276202559 169303229 587233546 398104351 326025004 643137378 34249641 760732724 517930696 54432877 223023807 796542831 675657046 755387014 871525096 396377015 750905062 900335939 929777864 458035791 602866845 683888518 520218099 870806441 183861478 767372206 768647610 944957341 146467585 60153650 980043525 64979626 679057207 96516545 906506210 968555286 598998768 861878686 890510444 844526792 394460674 969857315 974251504 776751412 223773250 763729712 856700109 542181891 213848242 575933071 439123337 54878080 36607574 174673763 153885227 441877559 307713925 982814619 349688188 835770349 148813533 386567275 755408478 979601046 376169293 428365312 611079760 204804967 782904244 651634856 240482315 716932007 129581413 274084578 886472075 687142008 36396152 11276504 73486540 361495126 854037694 114706429 501459227 17947076 668763771 463084646 687538009 110968094 228059056 112649724 198499156 674105329 420410698 773876923 750667400 154503711 237569348 421837828 485691443 181412964 322105601 260786393 349156674 301094243 104525823 774762644 642792092 928301978 787017346 318852273 898028026 50250534 709057995 761121262 314249962 795128110 912498121 433499096 314479577 373758052 551207891 542610717 282655387 697039771 311914407 535424145 590602124 381439827 911640951 266722211 939886077 485206885 667355715 197371377 374690983 585942342 304418321 898427329 54261778 784424096 421849819 244575462 4878496 809584730 395653118 738051842 617530309 354895943 186738549 966825430 371374424 681693455 136208848 955574602 673383625 368341182 565997615 818723842 162848924 537289293 55605316 335691238 221343458 261585874 202130896 233154780 783061501 582466019 811787574 820805 81940294 858631557 583858998 428015672 308193248 785277967 268904199 48873197 736390618 755714658 628954302 455009361 302830788 533405042 741108115 184195003 119457078 802716021 525486855 248478167 70739925 585838992 803406223 823001620 180614392 312638382 285948481 129054072 405335909 765126282 689415782 442659935 261885555 377330328 886810239 434179691 651231499 148637090 411278797 412453372 288731032 768351900 223738437 546815288 244404465 24444289 934155250 664740151 287750500 245224499 926148843 426211746 261101272 566472748 826016797 292407184 318609700 283860310 125896043 718062377 400737877 905058151 415497471 971815333 684018937 488597980 856048544 485006141 334748827 755589099 409800396 652268631 712586769 328044233 350144177 198608244 224986913 733681473 320441044 434857354 807542082 781699630 752886895 111458779 835124876 960471111 606324371 168226656 804898572 441563839 454624152 40627017 254870680 789957393 669813948 856336511 263008225 904899354 470058455 803170354 794920773 600207377 303106885 786220004 648445916 540397459 244005490 649580659 719194305 359379107 795769174 18029477 302339470 343708139 753650698 607233764 849705867 11945806 469665484 541778430 626583979 782790416 859636244 528463707 101348910 607799028 540331714 82158003 359421987 850583436 170605024 982079927 162406208 626902637 359789673 241349172 921399377 341867892 271014135 284308285 608400232 594915873 276843839 169121593 937163388 599620743 364104293 662160803 117627225 519230758 558004282 164110567 942009915 782133723 925075742 878855469 819729079 637549217 925060949 589945307 491061418 910950678 702742924 935255639 47369515 190628266 753029770 648336747 643121423 553125646 900773593 144921044 653862914 865727530 99598866 937561457 429445804 180547169 263820856 999731342 646718836 922823293 111443248 163772974 489981229 578705240 941955762 506406584 768651757 192073481 902647224 12130051 169546014 279470380 189853501 954009486 22643382 314961801 715123976 522346660 525014779 753023766 934690049 703989485 595713501 305916933 596246818 308622976 705570576 633214628 389741983 625134823 474578326 134249281 709017183 288074413 563996914 424184198 898583033 276788593 706556737 358141797 914932664 8058979 399079484 381502115 836175206 114725256 815971848 671126946 452436480 189744187 967459936 422157232 263355121 953466455 338214906 244778763 289800773 404237001 705762423 197739405 61068673 950588522 11688565 15351587 472884449 815789410 390461882 738672261 957829845 146790308 669370495 811973673 747262863 386518309 166508521 61206718 718016562 406233180 256268625 669366184 964730338 817292792 484300517 329466911 537170785 225607402 206074284 534497439 429657100 69194565 272687025 870403434 888065667 602714666 197548926 188183695 243766261 816821635 858830943 911813204 12976997 430917453 61574302 391582297 731794651 797326324 495097956 530891177 828929774 270134033 220450463 320040269 541150971 654006933 430637351 967756844 912544314 837876108 634037027 676271773 59944842 721403939 42793743 561883633 777828757 445778475 531896810 857648717 653405765 561573853 829401854 458490940 866839295 46554324 89669031 94549269 308759405 847949 180726599 864587169 778206270 706639800 161591883 474326786 766264747 651184786 804180553 466109473 978282244 121797954 32985757 42672425 399205035 716795874 310033919 487437746 243053249 152197730 706158062 499739799 758015003 789977437 886408353 256632316 454680295 731608642 311118676 805104172 16811108 335878809 874409516 770265199 511382702 267449483 849742260 929637841 545714360 744639065 248029254 481294528 264373588 644138099 196946643 704398276 493647268 379552282 760863744 268205961 386422945 42567413 729914368 100796063 885338306 824646116 241877898 32897971 190564715 756619640 878010806 724020279 372192174 338928657 549923037 534976213 960169531 81534044 451111917 8477633 11933012 973964515 340475261 48758873 248503253 729530593 469446684 15262630 597975046 811160877 253356876 429360707 441360259 445631181 119332610 661064762 888507614 191861187 611316857 630456018 813012171 509774275 812597735 260031790 112788621 825297069 831943434 648797474 588068557 428013765 421667700 601847623 395157742 163478266 165354931 38822721 439414521 252695192 372997909 745878268 242536793 481175768 501810274 547871349 181429654 71199688 868038292 442514663 776023909 771174916 886944542 29110109 982547060 117367589 948290528 398132025 186977019 903922366 899116641 622349200 38991334 120095612 748035016 655495450 820313025 805419261 506472164 654781009 787239682 864430817 933270276 399340176 647275737 611509518 158965489 987319823 737522014 78063199 710590654 108219776 986344453 430441565 608229591 548270940 504572938 36823309 625746054 626905032 365664458 735183650 752931754 817076698 639315950 570611394 689746609 186840811 935915152 330708794 815804290 71098487 725109251 657345062 138664096 810661659 339728408 28475918 810162438 657256205 33360672 166992762 150372405 971363993 537326577 324020174 774113295 285667481 931892570 486967640 401577272 879428381 174446852 589255248 238023264 37526229 602309356 2917188 618394683 521218994 192283297 998432807 534276320 513717602 101669667 413417350 525674887 35738404 459986912 878246417 450487390 223342112 286952853 845777413 372918731 603211298 304955276 266851883 824150244 925804651 783820050 434019643 111776357 404068213 229098212 914983957 613150957 826838829 588218911 560625714 95964491 607710088 603941545 21365221 159805964 536958483 43597154 757315502 241763528 502700374 107777208 850294658 475776991 507980973 399576336 83896153 51439597 241010548 492118130 648424634 728434791 761654725 465507161 967069660 732655574 34621901 671075190 214928972 993061086 683608270 120296973 464001744 901604367 917342579 610502810 492870034 611508019 48874870 638212093 390499415 653208829 126466719 705407606 923245808 514859987 685928389 77206101 591838838 768448425 919941135 311724438 881763307 290904387 53189393 643167138 82594444 466631586 237500168 483739271 479184125 738210649 778589582 174341084 675581413 251957380 53625513 934736231 957879841 922908265 779960038 614676990 19310611 683506694 617274026 770585362 346449286 264502658 967447258 421119842 416672723 61605373 516128759 290492809 950939717 890673389 646459920 137598627 645929227 902924330 515227151 876806203 100609833 927049986 241395445 492547319 940043639 192738760 185282008 69175579 855719664 955794080 76957948 735818510 401776757 878068009 519079949 879445613 231348721 260745044 959183218 130130861 255051600 680943483 204307650 754813458 689041326 174194779 341842632 853856697 56246359 159816427 82218391 835515531 776323953 375631000 766030487 799446264 722565342 284165071 780006707 320611891 33755177 987404743 696858160 158040468 79936204 330631605 528747001 830529287 185934394 33614240 204397036 702545448 471188613 88805892 505930930 650364213 351194891 978835890 950246914 626874455 726634715 531966814 168078125 201151742 469322453 312768128 975104831 627499675 31050101 76380001 441252983 897809763 671789354 419890147 432399167 477179755 74680704 709991944 951963461 76505441 348707558 992661443 627022041 806510868 719692581 222198012 175640874 960959274 863520016 793857973 579105130 869649649 908711177 609609334 597433166 982068259 292054912 669265422 532822154 326040481 866654053 711325103 983112140 394668233 275370091 317088836 401220314 229166790 688437050 481017264 635712924 947492149 278393457 158733264 935477634 339856949 573354645 208175305 445185820 107046781 320418521 147032710 226455499 251956709 584530961 448530683 963186463 148360106 977147207 194787515 406294660 3523213 902035961 755259364 235346556 432282550 914332024 474507780 850305324 249790605 54219018 679539258 674646185 279721398 989270394 988209734 134710313 38050011 785836097 547633325 216212255 795753492 228688625 972229167 42258401 374678446 966759819 683537591 634565200 496020959 728053643 76277207 612537382 214133425 38139317 67508993 629749006 612890427 254210223 472741673 934945311 100799905 384609658 612695619 677421370 728478906 619229230 787053877 337479284 73806833 111595069 169894095 274826813 301768090 443357225 847579220 894687104 932105643 447028406 305050234 932353733 113006406 553454397 886409386 538481926 742170870 841525431 449268656 392795342 575340077 453351780 843758108 58786640 47251227 473101103 108647998 326728741 657795842 691687257 91447271 418644826 702267953 308654488 586825799 513542443 56661061 511682268 861145331 551679684 761091811 653111323 239502638 699596624 442241357 459241022 693092095 447585667 664869805 66433143 421298366 24890245 641915721 945706961 203922630 604166752 466545834 668756080 89769153 720121239 870865788 604190001 68342642 57587187 722798493 245002952 347678018 548681872 826405030 609983408 112028570 520424730 618798611 296224265 450236558 989203477 682208473 541068720 16367692 797954898 700559876 18341445 307380045 684020849 170688200 485509736 427906343 972819636 461866815 757958104 916035781 786622317 648566872 947464039 76584757 45654373 195442843 499046970 458660719 781401710 722400092 723093658 491789190 177934555 394898255 311499872 10120119 135036823 15740828 940313645 476608186 573672139 714171167 209240517 419562656 902508134 506817325 143014187 266227355 912135917 853213163 808535089 447238640 702384836 405187225 878812249 957344341 994218705 26964211 44996539 92355680 960467915 797683247 974980093 141642818 318652787 312047908 240516573 703349156 773989722 768130777 476131028 365352934 956090825 9654843 6836978 929157315 812618876 871632545 780328365 425787851 249594383 233688448 377574155 449200839 122158686 672780647 449876216 75389059 662354641 349027269 979053952 372098060 899257933 241207831 243357951 639024799 571070095 424148673 342641750 426878769 496438907 22033966 259695117 419324647 425177570 654009147 561173505 564637817 307168369 943409123 188797055 785262037 229735107 197352483 736267145 469878110 724516954 429561949 354172043 6495499 725501674 630290756 691688245 183818887 644855658 21600090 729973303 192563325 613778953 510434822 82436538 389831604 14409179 631235358 652864630 223559872 354169454 703930351 981778085 467769624 705949971 271411821 795765261 78015265 392583092 966605559 40290566 990564705 364464721 408428420 787211547 943328419 512264550 404763477 448917721 226053767 852635246 391952587 617207049 108340829 307110927 218288773 251249680 341920109 566268513 932595686 663710981 656966540 354734320 779409304 101041533 945200042 518438647 814098587 224897252 978143808 478796680 528389268 144170807 199863601 812980111 255319232 68639772 402867820 248261459 27576607 572086199 656019715 203755841 206940970 56635729 789439381 980336445 512040981 97033718 904990092 343938184 371974621 411812844 915586210 342134521 988578304 35239415 606656300 27215658 982450479 469423206 354785715 456615300 326908122 46414058 938072262 892618803 5296659 13445889 120311867 900664868 534605499 208682485 195688972 284806242 143333456 356752491 886585276 768768848 246806582 962927403 395743698 952352660 232894236 878257130 421001911 463376596 315071178 281038696 459226243 750384512 540247919 204355440 571701737 995738970 979835865 636197483 710086183 690715178 109695520 293099611 162931790 117284034 455668921 606413237 68628276 770194457 201862068 850941056 521972858 855577574 979998341 573116675 666442132 455200310 203252185 211485748 402279733 737648188 344648599 602224756 327136563 472331050 753116739 660042935 164252149 170536107 553882661 864686080 435373698 375320645 657373539 601535499 57540250 76528656 981069740 454608399 319491493 873768672 408388955 956050124 246871256 193766880 510687891 643617525 28807008 362916943 252005181 453135910 506027187 512286378 980465843 775359521 879430642 986498089 819157387 249712682 89083911 16928629 228529015 435177126 483805561 829747665 795194246 249070297 425886237 322750904 732194416 786353702 817405595 360131502 181920145 548850971 760507809 322660301 227693511 975180475 486937017 33369773 320165568 71328760 919567301 649964399 591779571 445833562 456686921 3775253 681324481 904889753 489956059 863365334 397613466 55827062 724292411 705412721 397483760 84755575 45861583 301655865 66441757 204202981 101642821 807228896 712575050 512336238 795473718 992818804 203310176 206713654 39861002 869921873 655591469 860276363 164443019 173733689 860883593 242315437 131680405 418804626 260824868 378719762 97439366 959137223 79571964 200351619 623569538 748706996 27456327 725744998 972052925 359817620 302552703 958112734 121731875 199972899 235924583 328551631 159391910 41727140 762452618 681660720 575060268 711399952 984499663 860952061 191577914 158116550 567964896 530484379 423630669 112619638 186052709 282259554 444729999 329150477 154697197 474384758 199132294 41227554 761698272 51943257 315316786 39068958 566692848 660610528 910425090 248499513 807485832 501482944 127745956 798310867 27124773 339991631 498079119 746332099 787799973 282086346 828818116 756596753 572466725 796224849 671647633 391991333 63201959 987729348 453705989 962088190 940622811 548412554 318445695 747658669 296545487 501483887 799183294 588379875 790071789 53488331 250383617 100924167 961281816 863070001 381617527 849270949 166323116 685563711 915980370 71001984 542197815 367865570 590024612 207600715 525684046 827066518 443306412 121139156 922390535 271387454 205926774 306898687 920943370 554776856 514456177 588234188 483672489 350125075 161625889 985007466 145198542 531985162 622986578 873014091 98656368 93563764 33567223 335222388 680618275 96661085 266827004 326306236 910455323 767659330 883123907 36303506 72439207 286254248 110458541 235658172 845458175 600846270 59481236 350445886 739909681 451981011 254218294 26491884 643282563 497640020 236197578 196300555 497475482 496358479 35231373 830478752 602761818 471102008 353368508 65416908 41837911 821491301 27094853 62186820 590012649 806376488 619678371 465434702 705614472 765581697 858880919 422082681 514001575 487366234 367448251 877884454 865382094 74912643 406377326 717936441 548431224 243612090 272063923 468426844 282690556 197368791 634038256 168831326 497287984 802062322 415926031 983701106 694181446 703415663 730464691 591712294 962617117 451339281 72997979 816078099 782427642 72808845 336452759 223672362 803219246 185810856 887977281 504430956 23568739 903633561 337209970 266021996 378716973 516820619 456635289 826772920 598159216 815479319 668590194 802201651 321394651 707732612 724778569 2701678 257691807 28463625 996183556 832976621 456568986 557442218 872521441 672603958 102468325 580467510 254366227 237210994 502346488 486545432 881745821 994923476 625386494 778202503 471309629 233886314 108814402 156854846 985625946 50236370 582508417 680352090 477057480 918944099 52127269 119062295 62898162 123023918 939297330 341412306 889307611 764737537 365765742 807179356 235293260 698631379 396305330 62924282 262016399 645872949 957375171 465217373 454259379 655248964 987812418 295082937 852770596 826303333 979222952 225851883 909513741 722144495 790902627 958509158 412467615 536030612 38402429 961466459 104252565 397281780 167982011 367236245 911859659 337176404 284305264 473677236 706892042 733957700 823213915 413875739 882760079 776270980 770148377 581249000 4655155 552846018 721174433 370380185 189490054 123034885 419465406 685651337 356002294 205756715 427723753 194941828 851956366 173665633 264733523 682250980 54966685 772233854 128935270 725747665 502422428 648575428 20008949 149751646 928302657 158375740 11832782 506769307 413028956 434452920 820129163 535361476 118864021 738938097 250957680 379115328 237480800 125360797 488807128 470878183 139064601 623861376 184882998 213532737 514592 148646101 121829622 933316152 802474496 432952208 68881969 609823044 536930459 783144963 736189126 704349585 575213664 564885843 93824351 770949666 727633169 683272815 112694696 584122207 830560088 533174263 882666794 167821336 135597345 797850884 667612659 41258966 115145725 209981048 11842811 537408654 614951950 795871390 634505561 467363231 632278621 999338109 988596187 687807945 510353444 56876920 345341697 758790308 15679522 956198509 849710373 69285147 236037090 391095116 164619306 133082133 716796733 88866581 481050373 287472638 238952258 142432390 405532449 263244543 610075628 600467462 25021161 886175500 168284849 506631418 45261802 977080965 545665724 758625270 114183831 787394102 343717748 625373040 413129447 715206984 177710080 729849418 43357729 286965371 576424001 739708307 428450644 9734937 175967793 258465037 202499876 167509494 976745386 288085709 772072493 115600630 667058565 924256834 511115708 490445022 876454610 723497938 24483876 729954036 446095142 115843564 61002153 132990063 23453019 781500276 27204283 67490856 705090415 931116538 214104129 263723990 472849436 489457566 51863286 841522185 73523485 963680198 949033567 57410150 648138802 324676720 409487558 826719856 517557878 101929014 267886153 72693065 229942742 304719754 142654450 135020841 453230304 229851512 281988440 913638939 95235618 436047839 313083280 441241244 956870321 58366666 830822220 939850438 455713621 258304146 798592806 171707009 676936967 778709646 913567293 114127352 337383065 953744559 73442262 259762108 352769854 122524532 469258169 500452484 659368483 70981827 427616066 770159817 585577780 560402423 715059595 175910536 772822653 383002772 691739492 786885293 274345629 732914476 172526551 76443999 275890849 995964068 508963900 214851911 74963627 751680347 744531097 736141582 106165044 692908074 8599333 549346907 568654445 792237576 450599066 369014878 859010659 32521568 903571628 989204739 60806687 733032394 897714779 368869571 518217276 121550126 557949319 354613628 632933694 485051478 421796559 15301774 718203653 57728917 249362959 4576309 32967711 542117930 365299049 57404020 131542697 310881937 619041097 574399620 552758375 832730047 328431248 454211285 47138082 305068881 940072817 348486065 734843641 552853029 197045326 190755256 835545627 514985157 660173045 462894365 515165201 462702834 461771421 508608961 621199314 291800947 34843766 265500236 978112860 183520916 852233739 697238734 514847545 35069824 142339529 672692577 273435347 391157615 137166380 388959731 469235168 979274783 723125383 388762705 642976545 476923107 540165211 72528888 817094625 3695917 159668670 828109927 714820782 167286079 884755985 124128209 49886901 683191405 790656983 59671961 233530833 151624271 934072538 875098150 661627691 941181077 244785343 145993130 476436692 301716274 456682662 393977326 174103677 810067714 682333161 753281622 844760789 34781811 961138218 692716888 35656946 453256429 491372543 459368178 859096657 209850240 365703977 23967063 751955904 737331734 998713552 639524519 322537801 372338079 855042789 24350427 342144259 920271394 389815383 765835055 939499600 51891377 330017595 330352468 663040432 464673034 589827857 147279654 414378427 977513619 294549362 312438465 425074487 716737220 769760170 564242742 260313337 810855883 555799842 398313036 922305708 529658928 679172845 661351976 276764373 574870045 17883611 211822906 512956594 116290718 956343175 587425565 104155853 706724270 830386846 622551354 71330701 757120027 151705023 895733758 523512227 499594855 256578638 463244732 320408680 461252842 951328150 4584860 343614242 266441309 378730485 179928440 934273729 418641248 473892612 320694829 510137160 443059058 227224351 680468718 858508813 509277520 132767787 843326750 662703709 519914935 596360150 806634491 574396453 821974444 267247249 176035234 515147137 921965906 454259141 480201395 711284404 373485655 794275193 377477613 811934366 976200278 930995257 506795519 842670770 528626252 148308856 82653585 299748535 308071951 929304667 120822724 504126721 743007624 274547401 459105739 589136763 672672692 136249735 808020456 527286189 179251318 452160683 299468394 358493347 162756906 232969276 774195936 448807978 882815831 727825426 181172025 86361210 199689646 597344560 991742309 596596293 694186092 282989752 955707044 208054224 639265161 434267120 213802207 611913446 889275508 604349770 899471038 937542228 143523482 598596421 182868567 268797943 995048457 476546094 217538243 811443821 180657449 986278269 678724614 950256832 344633209 264499823 385700563 653214693 163185801 931869346 982232864 656497749 310625785 64741347 33666183 30472219 773303543 377168898 129440610 659235726 404385307 189930344 161983881 27138389 270292348 317262862 389489631 401291128 908180538 513286155 960715276 749449288 891279772 855078292 732235407 958842236 201189641 635706732 40479809 417402959 59831964 12550878 939594716 274821837 915619255 883441386 791457060 257412363 164816453 430065294 480722660 4652320 223052488 452402894 818104198 303206171 623894067 697167595 45421312 779148875 2141235 265280080 455743124 142527081 279299277 496156648 68193764 226692523 63360170 984928384 197891707 915365294 447228400 582793281 376481653 903857582 288446502 436198417 739917824 329802285 625721797 282321342 163913787 364866644 32388332 488868069 210572571 359981133 221445013 103532903 117105631 477487838 655426796 400246244 182625240 564113133 767179904 815788043 777139081 872813047 730948674 873236719 589466952 346009931 115446242 342004277 818459534 759130523 687242427 70162669 670698153 485769323 353993875 380873791 963757205 266344128 556699126 915311841 854588648 443275867 104473439 989515116 479859724 769953584 979502645 701004611 260130030 453059482 614733654 282350898 605389259 658663535 519448603 855058776 179421688 654284138 879940583 346195086 786192558 806078458 166277438 754237245 848534933 440053894 166182754 560659673 522064669 199027855 700137706 623060967 285554578 435822487 558798771 407402339 853319690 528546784 591359524 354101187 469637454 610551449 46272304 658313000 300903307 86901582 118078281 595655300 900648066 4131391 483264089 863458069 603830411 497292926 540165014 626406776 213857750 466294404 348249575 721493454 168088641 413317059 708374987 467414658 857985677 533201431 50190588 958303301 730881749 551168549 96268242 946091639 506519188 445998136 462521051 748556679 985327568 135612376 637258368 962767279 434574215 965100375 510405712 137635274 333686044 350808735 917165650 597009392 888653335 326282350 420731826 884630533 981211583 287028247 773714617 415135868 69083072 347007088 744522385 616909539 951998753 587743145 707864996 869387997 648861370 956971862 444247752 243860696 44737684 581771957 436923103 990180662 433731355 904656234 202878412 935615327 496441904 831556248 362345578 655679840 438781637 633467228 605035003 974722574 197852072 969920655 367433322 589329578 719403658 90252501 460738218 290136885 79621517 229936558 373720193 27646482 653247355 546306607 938908278 338399725 585774819 720954673 164857903 948566061 669915427 413903928 209067061 767300731 307070810 763773786 852355875 672355870 559532969 403221034 528050261 637762346 903762342 984202288 595323828 947767308 524567140 65517903 818226764 210431970 185420940 319944035 429473801 889084096 335715061 732096245 411112695 902761816 895557483 582134499 920657479 132140554 252855631 122126590 16832577 46519148 691746598 149370959 415444276 224743172 661968749 188838053 748464766 656370156 503403058 973502798 589405420 384978308 642399803 119453301 200154466 235894251 74905510 259603900 930879835 326938428 404381943 408644714 935501474 232316227 852843261 104820510 934954255 213332314 754522261 630359709 728413699 211782662 178239665 672198560 416902922 426886511 88460709 351364344 731280875 200272753 27609063 102397696 589727502 13490415 432658385 775425163 793518072 302401069 987193933 180464278 804241243 602138903 288233376 502191577 855082899 619060589 865422475 566354371 209245508 820531683 476689705 779306105 536048083 965729998 570889493 456487434 420656039 782388795 658426886 461598044 395564954 426219028 980307686 486533781 336353267 108327264 621064681 125924690 566740354 751423885 939145665 109602501 57069231 571226468 6667292 618636843 233132334 887798005 577659257 32388308 919458448 214063237 997140217 589014919 15545046 837247038 856807147 550604591 506717396 136508489 443295822 286268648 222256912 998915032 263175058 664776950 601123365 583540742 461960839 300122764 934606788 928890605 343266550 902066691 182828679 527753405 574709034 563428843 111775133 248922976 884323284 49975497 280806366 984606681 982921877 397594920 979228204 326720291 683199192 282969777 218526467 45222896 466611152 676531008 605078539 709195694 431595381 636546507 192397558 451966395 553391156 510138258 204409347 953290218 341751904 663549530 979232315 705315393 450115639 63341536 573491084 356038302 678912244 684461541 38618036 22425840 628193973 680369730 882860113 651811044 748389844 377229097 40123969 785520270 438065938 384632999 677972715 585850517 301927706 407354064 542528681 480392461 335043869 985150800 456313191 740249388 560200622 650675810 706284530 69823753 34952836 265036420 274457263 912661500 733163110 136186377 706824739 265729113 38238828 472026967 35973753 138547541 979341123 973826815 688129643 80927339 609812132 599534568 592020109 952158652 824697108 246621146 838903178 326033164 570771400 873564693 180580533 921824872 399158560 647760908 404577996 626306138 416477983 565178824 338610128 433206371 928850004 983630992 107934352 260146981 177978804 789180625 954071377 89546162 651808402 66631033 328350373 315084318 659977155 266945180 302974833 22572401 220427073 511164872 127464281 267091440 198143679 972703302 229790196 652075234 676324057 900460370 49040309 746527831 121215570 364301118 106109072 880191016 655791072 561458815 483347615 416442833 257168593 629180804 976895727 634608670 734089660 359270687 239607642 38117454 532096392 149152469 827021296 421877660 996929057 522346437 989136548 327862492 913393451 832252443 717418298 613932841 365812375 547618130 370183222 510327678 956568234 648352503 110777486 694777519 736610749 118310862 644433446 175227016 991100885 407957179 835407209 509890224 971801830 510047928 131141344 397471999 717112787 269287754 137706412 795729594 521288370 684389472 186148579 709877314 838009407 320942558 759675051 818309293 158044716 384976123 820073117 315096418 298358592 161927191 795962358 106521579 439366597 686940441 464713878 759673633 968819271 488081217 391645831 682036870 823129995 324693887 132685135 367071571 887907726 397157984 393599207 358813916 882994012 80983833 695032209 217263103 6616413 493544351 53566251 317456840 731174365 585085063 812539557 517595662 548093125 491856599 592331935 956317825 977476916 277000348 745349854 963846935 766389789 358766868 514844658 606078480 979692884 598620398 482606722 996027967 980095006 58461645 112314101 532527848 635911173 646847685 870861662 843086309 135770018 241720500 215190299 116180037 221696500 282485973 393622327 80332832 57975099 37546737 293714135 713560110 399455639 31475279 158271707 744662724 549507469 550182076 437266335 261618799 436226413 217692823 196106087 943615095 567433635 896611976 643321037 702153639 596829318 333135357 350263709 619266586 622632531 765503852 775615669 948158227 247354661 703109999 36861597 636880501 134569016 435664897 916396332 578472020 141962926 434862710 158983880 161037138 445119716 791206844 7450820 428367752 430936072 494049373 781756968 77420748 473456042 997536175 755075416 418180872 161573993 416469231 979038228 6755924 327507616 367160159 22135436 286107442 133977422 904260478 803154112 258836152 623957916 534542996 366018230 261171727 939407327 342846027 996724467 376306996 523063245 534814199 731731159 258008945 110486051 575682093 750324956 832958676 602899665 167651602 894789619 235246895 820291209 549359561 75711914 559523653 658211311 941944046 651832839 701917854 586493935 453103192 269231938 684877594 647547542 620403369 702770168 340514219 433812107 997465703 279675401 792486325 428033016 596154612 845653301 588381742 987548122 692625713 515293635 18480708 209743026 539008757 562675575 639890360 606272730 913542567 833145498 135148530 452759598 499296539 150945469 858696987 187556099 540055906 559292159 838081740 287050610 974888564 206395334 161006409 548049475 877239812 35316596 192308560 983372818 160516162 938026427 376199532 814142898 712072695 772661680 495011843 824516517 31828068 25099243 621585463 709537143 529899952 6605368 377001796 955486072 483197322 60638098 550579559 3539018 964003497 356167349 839295588 5185696 703939819 78798567 453104255 844871515 330297294 421719625 993442331 530042789 25245890 72536665 55990257 808921950 814592799 672632237 990265697 354194964 92200087 615848267 6111087 873237753 739243473 697080863 123751989 18549702 47792393 259500490 578866908 150793541 111870348 673131557 102043349 798188654 837621044 957171770 391495141 381030326 407140588 499432271 536358574 111340765 16792711 257676897 131878157 896366014 430465061 57332599 258396950 608770376 360126278 801613819 223301998 895699556 961694003 190197693 69953310 433665029 833049641 508326511 276702508 640464995 235860512 823626862 861799288 182349801 925305666 232932807 873287581 824015477 354864428 373461714 543911832 599010039 143124388 632886110 182816535 476337968 411635678 861549743 236627545 289557938 774981943 827701269 112629568 96321588 742151345 467248132 608426183 952661715 103819166 34383657 489010833 707529126 357629239 752405455 332023445 981732730 721339587 713779587 915638645 854881170 406525030 315778848 337211283 277430026 327334610 294032800 794713591 576413185 975633087 366740856 118822791 569821361 521642267 155779554 794406072 966606828 39359946 671168636 29091038 729691360 988022010 662953723 575571875 902756818 57564713 703829268 538523041 448124314 729531508 381530355 44635459 965688650 260573692 423440411 879791791 493260393 160008179 934932038 476491160 417259537 815617581 103416022 11371508 668771584 902005239 846357677 690079182 383447499 690795559 928221524 16679341 857467995 424104654 422188469 306339902 123692091 737389747 971962952 338628455 316716881 307373035 765660942 125800681 151751747 522169562 13985040 549928453 393289203 336252713 493162967 283098408 78392054 179132232 828211743 598891535 576094696 375194193 504901307 443418372 974281956 859513736 294745130 556336890 366230576 904601654 806246903 527853859 685685516 93399372 142207350 679019120 691803727 908686138 297788585 239050355 65009674 221024884 263492584 977725287 505252347 790441674 272007369 765573842 549029281 210637613 436437701 829307083 478736113 690653496 480895813 852839470 713776367 113886811 544409736 77868880 901684171 860627143 108649293 750612508 808922559 138181465 295971310 130125896 891609960 500534700 503999378 241396709 837914494 294207120 696710983 73991368 684501090 405922324 584726912 468560680 441173174 771937503 843160202 750773631 408697572 519670568 844729612 31041291 469267467 697243870 6604527 322973057 319966510 307416446 351026250 749504263 885653135 585425644 665294412 31003932 484708171 69952993 805971965 830619816 40042476 248873407 923580534 405720556 115904862 124132323 949991314 401447193 476783368 589542564 416786993 563199457 706024152 869200949 32536774 55485196 118346852 626233673 765096127 578651082 680000831 445678193 290401480 254547266 662884655 275407460 114402889 604086925 638842875 128942793 241912490 388275918 962580953 62633234 238697833 596670582 172931958 316151948 743413150 353192670 868019368 226269604 256671683 535584403 221500113 741389069 675787840 893544560 381069225 89451091 387536618 661080876 646243871 68379905 356352304 191149386 339190726 693448225 545422999 884726761 950059479 99019515 601494644 971882006 618176668 726716365 420351839 193179206 119640856 460259156 930739409 863683241 815803636 757161600 347942043 381842822 604335251 766491382 456789981 78192833 63542370 738762908 221259886 617156679 386718276 959875425 152214687 892364381 486196611 448347224 354195204 246224707 225118929 536333587 107883633 531172914 62640453 738732943 502996952 240237712 17568234 708163068 274889491 49708893 568479391 148396449 227533371 155316585 413208744 422755337 350210970 571908558 573711073 860732505 55656101 54025565 791727705 200370827 803922854 436471445 64512163 616322422 847990537 747522752 23303139 75993092 573931168 849308776 40076140 181554223 527542225 48473908 806042927 962568439 577877916 47864453 859912347 768056859 596197772 97044769 134559129 860845643 425967622 327542645 122816075 989565646 963997908 303630213 677221902 506504784 311876989 905371809 736815118 215970643 57364924 342428561 692017582 596077496 175477942 765637106 315233861 108618808 604116247 989055774 243860881 791055046 751907036 339318239 704753195 218439857 210484415 910414536 809329190 253891515 441191197 107583022 338079122 652714123 437118320 108710536 1104792 46816043 428223989 470096335 792039195 922021941 740846335 700694257 303296801 445398324 277909865 870878624 296298643 811271414 542919449 469104467 557296584 8968339 753038674 618106408 594368291 450109320 720820477 466541589 651904115 344356031 658216891 132389399 782682819 951580627 339596986 530932233 642025001 17813786 430246452 888967621 691916949 696018835 51615950 805639174 167405980 786902559 64557976 698974843 771996677 573739959 791570451 717113295 952472167 957545205 830482766 402529737 905019353 467110034 934893284 160832796 145695601 208198806 257491198 781674998 111008312 95910478 756647745 828284068 861688187 833902594 819768209 620689201 519682697 870639237 499304571 583552276 757357951 77034482 933739213 2918796 746983025 946413589 118210025 346420424 553211738 430428990 992369508 993708150 567712983 514674267 756419763 377789708 813313714 617240217 895208714 288467007 159709712 952622909 517502834 993388936 60894823 369722780 598701912 426625004 300536146 649825984 722635758 284871122 408484452 895270121 209013663 195106295 264223888 503160959 934318278 694346287 246922333 866348549 758653648 707462938 230042837 530192016 154039288 778759584 419954523 918376839 514366293 454738435 856809752 796101008 337144299 376429441 249252666 955919079 680805539 518296760 713152120 163375915 520221806 301270471 184952033 330421932 866353550 10415180 753724308 692056397 457708419 227435468 148600909 543352015 380436222 955965907 124366679 194860833 908810180 893531273 449661920 607137887 798847300 781401970 856242244 598230160 696524792 392515807 132074530 437040641 67762461 239782263 634530870 783407843 856428004 185535559 271874409 538899236 154472036 202571493 754706386 472569311 878815191 28071296 759419490 91404097 472355310 207249633 735282257 331774381 926873713 88901530 477428973 755310116 434327568 688092301 462889251 547410160 12909025 333978474 553681841 431050775 565692820 519718646 162652217 753855317 702517623 337034943 684361769 316703178 538174453 726380702 165491508 387829288 118941975 935608139 730374579 201132555 625231040 208813740 468395614 357965695 695306751 460616645 780711483 518955169 829942824 660968145 446029976 520024770 107305022 777490590 898603599 988261668 666138133 760718825 834116690 151900541 141323808 787380022 158924709 345627310 342810530 355108620 289156467 467879740 511965944 441072598 667066541 360977363 542175722 398920178 634856336 836869356 425930238 70424467 606622329 668872962 207440030 101927989 289808474 585850754 414228930 392963662 998518422 262748188 330195553 36927037 495223834 797217914 276555150 905168440 703734521 985134534 632091246 518373665 484777070 296551395 94881218 239104279 235281840 222406963 923718449 713671983 634118372 969556788 582604669 93086716 236643229 557366666 791979263 478291384 700856506 695208448 170719953 20751061 128547776 351808026 996536162 422960049 844226262 606735792 529482046 33393604 459734822 462067053 357259867 501306085 490190469 295230318 196514996 152191057 986466675 92811307 464866827 860961684 230121502 657063995 703089971 475284015 20971974