18869
961672100 31746273 418712988 687885924 336320089 695509351 998771583 930322729 171640129 103234019 984751407 8217618 630216659 238338554 850200526 326969260 889829759 236328008 51813390 535607169 942522099 133615771 866235524 393670169 790151511 21724857 518766593 208574192 521510836 482751066 348250265 977113351 143508031 993678143 622210177 72353526 545133828 655274082 381957090 301556055 688394585 507801936 887118729 35622656 775389346 429545386 475524937 268399728 407004244 555217646 103648902 896127066 283557962 867737964 121781229 888799370 224941882 275993373 342350590 117022748 458483579 518867272 874301708 975630947 196028056 488799024 696008468 103465350 222067389 469747358 662420209 147156936 329536117 765009953 442741900 756790364 474714756 975587917 695392506 982753313 834223830 157437068 851121122 189037721 29592136 275777351 407388749 485739818 108604205 145506774 351167369 675045738 31806359 273455188 726035448 837464820 50694417 400704460 894819307 240605106 394470395 705081667 802815687 125563309 68448494 931821219 750732667 271696581 707869434 574183650 232057145 567676268 395598313 517351459 37808349 128306329 796472919 797857008 251427856 8840276 871786227 584157123 855061241 566851620 299874987 957686984 298300141 922376653 338902921 86166945 493096693 771750666 40519259 187041921 7763357 472162903 16600359 589896411 854446188 194075344 253977943 815046789 952873040 448394535 395158627 861951160 314310198 160390482 767248841 392522224 355368974 873525946 214462389 661678773 625647313 320963964 237133246 588595023 981139941 545172936 762394437 51313968 2950271 636707664 337557591 278363475 792655480 395600168 635331541 934825969 491581558 704591844 597099836 53139989 277834015 315585907 875782926 321419214 423755660 15332295 230794343 933155800 966432456 674482251 170413578 129974373 853115513 652175338 317197040 88744195 188957012 730406413 730883105 969454287 310308451 811108350 339757711 718176635 287199846 102519725 797315262 779141055 487907766 13975629 650774351 813589304 576798170 754963550 101826310 174490136 214634124 867671128 907914045 746646965 432588786 999231211 238635923 741937100 548015524 857348629 578837129 995181176 897029733 138894749 131220803 819183220 332016282 76678612 419037624 954718767 599720505 767464002 407868692 138813910 933858207 337587044 826841892 337299844 199518928 283554479 55278576 55582086 432159483 13634053 390931482 555327088 97270947 421714366 494268026 887616715 418897766 54653509 306436230 370140383 934969035 194151844 896555695 622771865 97893236 662511018 718445406 264202790 84231565 316306406 459124737 164092121 475533455 938797016 373068095 515057074 990632566 213526638 742267114 833075273 936141275 392568151 72142217 916776307 534743009 904761871 224502490 520569631 187632836 821004838 554711117 565281466 920056381 816306159 116781945 508584204 768182733 501750400 28336566 246101700 730407589 871710111 337329924 381592788 463489219 327262431 34798349 622629185 461312969 365450193 886416633 231547067 244381520 336010104 728872505 810851804 557226024 649082936 316719364 822839955 932597170 747053328 401767659 345691649 295501595 476619846 389190310 882473161 484157631 970685308 373568081 255757519 721062803 228647417 422571034 173267605 799823811 355631246 78978879 163716302 225453351 235954395 686279010 207233222 851377544 863947311 648246764 37242186 311656541 865194448 149978754 576928502 353884876 952795486 30356289 820146365 449427072 399513875 578377494 679162199 368453458 645021034 439583363 887538153 378941661 587410932 539411695 197140408 587692771 416859804 896301771 952266440 525700730 930859777 925972767 66231707 40915979 319482998 559683183 432926304 576701135 947420733 830462094 804458685 731983601 812736915 515927056 670270389 198187074 271262709 194573071 529950276 47632075 60971743 150628329 4581813 96050016 95822102 418724503 122897350 530697683 214899987 552572010 679501456 722797269 715221600 380097168 257210246 177650728 751401843 603282919 360232877 998033539 162004246 129738029 861901017 624392780 494985844 868660413 39203720 563027329 748790509 239065539 173381827 173310561 433033938 739385869 532338632 50696257 908311494 760010268 361947514 829006016 937849851 248993019 47233845 501038128 996167326 691537374 241284816 365955475 631235994 423372046 947291795 573088694 195095988 789414053 660290519 832322466 132535904 647449028 668058432 189445899 392163620 195570938 953947343 90396599 407618572 642219969 893597276 598830274 731935889 153177007 661378374 495410437 840548029 148562903 404388415 243830441 843536349 131473906 305497849 418836517 556618698 210881363 142276637 369075011 685221863 658685441 862221198 757424524 904278727 488576275 167252985 170373501 915512610 877110444 15226521 981609865 329146431 536273678 541203770 80684308 516096601 729583267 579315994 568206901 201724218 684899426 427071027 808229483 957259725 139451214 80151748 580787928 706547207 802891984 195013014 11463121 318396803 377561313 600349677 813207020 925261045 745508973 648189835 755325581 225201267 732121146 369030110 204399474 891586029 665167721 926188908 106702970 892197703 811382777 52612391 70682418 456633850 301344259 55259339 963094429 890662962 471516788 797650078 290944744 56031576 416810315 674255739 313491422 676556524 110465464 286447005 795136818 371345821 75227419 487599935 645929093 759673114 915810341 378871367 798257446 424124793 611138106 55071432 521844911 401395684 590084621 283671656 984134674 184794662 560935264 239574267 762401270 748847137 257837519 77070538 81908268 546422879 940379791 319939759 114373850 623590536 866097561 454379249 257859893 159399306 364552838 230026190 960589159 605293721 900166299 103916820 860245919 425457056 865378560 167493874 934542929 566767132 18988691 768328264 957058490 312197456 56398465 540123657 634226696 721451339 781775876 339101055 595697224 338629627 629490759 659911341 533922554 248491912 870582493 878878227 938947074 494671065 249008740 515241069 117450114 629515789 510014744 207030196 852046393 815143415 9291004 465711943 366154746 314992053 530666747 302638791 121761353 670159237 919611950 684369485 457750503 543969616 10684174 140815997 347373769 914743849 500049193 751412506 153355427 341683569 134758368 785731440 910159624 43160640 926637099 266322157 84182154 116769394 372944088 374817895 508636071 211129654 521956281 528346739 818251959 805775174 327857826 739646880 827268403 973022996 172319881 596555647 781495888 557035854 896503769 607119796 498050558 346059799 888416315 393696585 977375311 497914959 30225188 337245863 760692771 863724915 463746654 586838187 133296220 346627028 646435131 143786204 729215699 926293067 757734444 515349599 750829516 462970871 39012087 374228188 259758260 524837024 114385324 326211933 257787931 876057502 482609390 954705991 584797929 114117252 904760974 841220935 347374801 376806006 776181012 179146196 176615859 744999582 250634215 662197220 446618735 208632472 663078050 255970682 86636091 949453731 163814286 37965530 662480407 742361448 396382745 102995802 72509470 371980126 850831353 792688334 847163107 706790090 138630052 815675595 262941945 162690764 873322069 521818521 18976427 965162445 87587620 285371486 950692891 986742619 384538259 329335078 899490555 144654177 857950659 818587100 327780716 399003636 894758724 45667109 609257028 899984262 720689587 167746205 225218513 830571350 792852350 410186918 956058185 177477694 259944649 956689911 122869505 350831655 964368423 86119944 631137862 608622937 399719240 861205582 184297036 214985430 37348387 339510305 72804763 493804482 768105763 156471894 847101944 55933524 53652733 108089262 15689830 682115167 81710928 741298343 821119067 682516523 688674154 342854859 504219183 261859695 337607486 800465957 306913618 505175569 865041438 314364446 971555080 480511836 853797729 16352222 940164821 358170884 578275595 360983359 309858651 192063759 769765076 852992860 861182898 47808947 554128588 922609790 455498265 530509858 69169929 481433701 187585993 22561967 128508293 392378679 929481784 106490899 539720096 832291159 147506831 666923499 36240327 34593905 909187271 889112844 821276943 736010732 643290681 297177271 867257074 526400299 817604666 261726066 476511363 638720381 559584181 93753110 949842707 435285955 304097120 341369772 689013231 141685339 649258513 88720788 94319017 621414845 215222683 925649510 517551201 404645322 172322294 628856739 70167478 386896023 899537607 26475308 312199295 252011554 139806982 24371721 231464265 597179397 768364732 165520457 897545768 80733566 291364174 5581332 848208171 335393056 967183053 503073806 266914625 196978965 714655910 678466386 68677992 590107435 19090298 507693444 720691403 829067740 54153368 92671779 79960732 731491504 688861734 191538852 455901546 373600674 872670248 329972646 341785626 653377494 371816921 289944801 228945907 770257744 497854253 206994881 99466030 172455075 141535018 844093810 363649746 268627656 205182237 123912480 820999458 315445732 792505046 514596553 281951680 832307056 151825119 943306309 470928416 328350208 768811825 644107594 976045767 418485081 349008030 244430537 632087075 9894213 75546059 561443239 416363537 363404670 3689966 83573743 804782361 729743519 401285678 355280630 482624904 931362532 505761529 470936323 397328253 628489627 525386760 126992145 417443402 7679505 648735700 972281434 180312772 569070452 677299761 528078093 53094291 974298781 100741120 434889183 801469313 967416811 489232663 348231401 285316428 699067442 497349166 891624987 463721563 127894382 293176638 164556117 750385790 907167366 807651807 55564884 738668387 111136841 828648265 703137524 916750171 272745040 151335144 434222054 866480036 311587247 210212869 375185633 202223211 349368448 126531326 740496415 411554247 907306500 851377288 653106369 519244571 326762675 756050504 485526307 218345761 72166209 786492346 312763225 300126640 865614381 194050747 766711211 715635379 413439156 382830082 254429947 370049515 184662328 651046368 965571201 131435174 87052842 692398496 18651503 904456376 863802025 989838187 701141844 301488057 337417597 149019083 443217988 420300865 365971402 43415579 886902431 479019493 723531698 712433046 857992784 930262731 661864358 202174637 186282229 128348011 256883446 106826648 475819386 948293304 661207958 832073658 22082699 674668039 69084248 465865629 207254013 974208409 256596791 369366309 436217141 764869047 827592007 723238971 771275547 160820182 643497865 648919006 610450429 683558511 48232606 41797182 332595162 601044421 798967087 774849372 395382119 609169286 258014451 719979085 104079420 418960170 8696816 630317389 51253833 914281065 580733195 480196007 495355380 854237842 527495238 679116058 379697258 806792854 219480489 57330653 345230410 522784489 604945070 920989008 562067478 852286609 620495232 33718374 403789870 140715343 482087752 575111365 279437683 345321751 168857103 621066475 394491784 193015321 804014916 404835963 717178287 415958014 462362394 322651987 941571555 869339404 565091523 501747522 981482534 24653473 807555461 276092595 844166825 424636458 158095956 148902247 303117483 135444026 910950304 880549318 671587484 280324373 729138704 353390598 206221062 143284931 561802160 578805153 242515705 963912107 279154580 872225522 180082750 882866741 196902395 923063422 124042172 864812223 354229493 872662156 232553814 962182388 423224726 851972657 865299933 245682243 144588275 930308154 570824329 724870640 746364581 379437841 530425737 771316327 509423539 134804413 666157545 162460530 186934978 594000349 89249194 245742656 640321008 672748746 542200966 398290145 153090110 663173279 273824758 453852091 225218162 672841303 798843980 153469513 479770060 721489628 984281390 921223815 542667276 241831271 201201857 528849917 430909250 809928848 390007998 284846619 590459089 651799109 212615257 839191645 113750007 771238143 465864508 231484502 106364157 870089936 853084037 19969220 725957251 749803941 972955015 631070455 924094485 59018917 551076440 212926656 53045701 646900489 837368580 928315577 394792878 386615147 17470973 841949325 103744896 587419994 121840614 806482551 515330059 730202252 120851375 294198849 475374884 544413975 852469583 454238430 815149267 151407717 767179557 957310073 115232354 820263535 426602571 724883398 920913983 809116176 327047790 987005240 938187652 162298017 428289692 382785641 102695635 158346611 320643334 525416915 627902279 211204384 455888563 327525884 950412445 234793685 204527973 400426748 440678914 887495625 423427608 995712311 588600222 671482536 83337943 45206785 522366745 821823698 27797944 655111372 141056143 542435763 280076224 758555466 891038945 145316319 687978352 993991855 688659401 773534976 151843820 871670193 552590351 571696190 364466296 685505110 460616051 703517467 129567704 136478226 950344823 279006640 452651974 575044288 992774438 535377608 635189269 92539580 619999823 635812200 227270981 923760069 224378092 245261717 369913557 297103397 629693310 257552874 647006822 885289288 288916262 748852071 528552566 753550016 40731089 305002530 166058586 215518243 664491322 431465618 990763387 355560166 672091956 511577759 324217587 223538370 130543655 542917185 283094263 928841730 647319497 785067113 895548367 179244228 469444056 155363497 487720965 741726727 196380990 374110706 748073470 696596195 665100184 506566300 140227589 94558504 721898840 271310886 688655156 294878050 987070800 887386890 543613516 593478282 485997091 843007338 317301230 916790215 221991155 149770270 232246631 5550420 618023295 316069011 406071794 415901642 506870602 955960025 770621799 268674532 919231624 682885727 896453205 956665181 172745489 870657908 171906962 171407869 590784593 723655871 785193785 967030878 142682689 970803562 149099159 104639341 892296892 958615565 597674512 734368553 821613817 571873239 960903841 992087812 111945632 85216665 966190562 97986557 525288988 103257396 81835768 610337677 263219357 35306622 328923990 650482987 618929999 115025135 378322837 942225637 277686099 512777490 223276646 461732356 520979499 548581715 982255574 33363076 954948722 142952574 625619649 963880085 750596083 121169483 421246182 405790629 318701147 850975712 665364496 318173211 512018799 747200598 77329527 924605812 977844428 359040297 805056900 966447117 541503350 607138538 907477598 558178633 586833061 736264743 888900662 642705025 744098479 768980471 554201713 475334135 567385770 181806424 468834223 675535181 304188644 66462443 916927212 378780627 94503737 76848756 631503223 897859775 389149383 862807809 85950910 834225096 903849475 869969503 65329694 782114319 110981649 756812114 924174861 371009664 949661806 981917222 865199903 369172636 759496137 782732206 703771437 820021972 2227206 532205649 726854435 824159507 34545520 368534331 396895898 318815180 820583815 768853988 142566701 76501597 413063316 730205280 163863918 997809687 701514341 232166106 351385746 773866330 238282178 784430103 666819378 762031324 911146580 404667316 168682229 641735919 964685747 928043404 816183305 748351550 863523262 241013770 568798272 68013085 172490028 139671795 136328901 395703377 61163294 300940212 547859196 326919076 247043474 195211307 622196750 120282295 31345297 876863201 621652218 224938022 452962928 642080920 482283242 857406877 337973374 445008486 432948474 549634438 569529636 337614234 873937700 667960090 319645939 153671775 103476191 25582537 887776670 112289032 751196059 949381479 349664742 547593655 750008527 312553997 918220897 935157618 395152959 245974696 585388499 821771530 141880918 641180593 910235510 708913980 386018094 68601900 241545378 194760220 67519446 996608003 826002467 246555634 98707012 63134955 908042487 928530290 480236396 383637283 732950250 521678492 62451303 651931140 648491872 765893254 103145601 393868875 600099759 96941975 647972216 382680420 829069431 523453157 906345559 78590324 700117033 166735372 607598704 989342175 459742146 119491937 523791888 682493598 133883914 787746294 464568837 437474337 756706861 45542583 188805566 116636979 780925578 630095903 823795480 921105190 124766064 460718505 977973562 222693808 738285486 151056783 339920876 69091490 569448545 89641059 434743359 61868172 816515753 495529625 10325889 802613031 108932384 965776496 687120131 720742633 115273081 791180061 796014400 631754578 706121180 351941774 399591612 183922302 270357046 88768312 633867642 833328618 272976100 356686552 980470814 261535658 907052885 775977390 266793233 656199423 761963943 16035664 522141538 102679012 939451074 140703502 296987960 571913876 993767109 40636855 813548137 587376517 732068368 618112856 173281368 390832976 408833817 696142711 693346413 77698674 626794371 465722629 575359391 548534157 691223452 887156754 621884674 323683739 272081989 872197880 208079116 556206274 520537256 38115531 136349162 517740100 30746027 460713253 887695198 868785992 531614129 240566903 654331914 420569070 95427004 384635181 275002402 168277750 449277946 451495871 847572477 404420200 821910309 829655296 794870116 384078750 837625723 127962153 418629069 966315653 249971141 539918643 867232015 14948026 27978517 399130443 145002503 854610894 553543729 466620418 550048642 186108556 78354750 919908553 741924923 749502439 476945250 885777581 31886884 410751483 575965649 892313534 403768793 317335452 965340764 369630955 629419785 808887539 640801002 358236392 438492057 851013522 512318535 937308576 476401541 94482279 813205887 489481634 744142312 376478863 826464032 40672227 463394944 201641342 303770488 752635916 589126590 811370885 718541940 675940207 865369619 295315149 322729093 65159753 354957563 660391387 95900455 944438338 985683539 815279143 209444478 794318798 367181842 827129056 158937454 83843743 180418987 86013311 932968630 582305794 683215750 713035439 207123577 904392168 923995884 437338972 778700053 985430953 167082655 224251458 601575512 731362091 68377562 49103186 590343222 304381688 75101829 908149513 763248763 434615223 539631429 236537245 559306447 385442620 60539471 308596719 404097005 571609359 283912167 208162473 107732899 554056162 170690390 522239573 901206691 498777628 921919469 268723517 573562329 551218139 810346674 994217529 180863711 710534979 742031516 60124246 440598730 62097317 598285718 837624748 710691078 899237194 269097944 626287362 448161997 955037929 888782515 964113453 153726663 553462500 809702421 512631368 607874175 399183443 864217884 458920808 394330635 292495704 999087992 684447579 221181909 832092329 326075107 182327308 459292911 309463192 822821568 498120394 131066717 844506984 460269245 60287069 643716287 670619999 738229654 230358410 534692163 313721131 883956853 520170966 681147105 929037180 235529770 79843159 913136035 34101911 388590816 193528860 702204619 728023273 736957681 914735338 474436421 869768828 254919661 273180340 940097290 14770331 380239496 994168091 766920285 521870431 930004048 196948276 958879515 958892422 510092360 110083723 390898346 308465782 973711285 691660003 758514415 54042225 732807103 74440590 316420713 686742323 185167336 905436768 372603852 595326149 154245087 718316536 688583387 891669677 428024276 765796930 632436212 933471825 383387470 641294252 733226290 565039346 215404080 358727714 343293630 966714721 869869617 703319379 150170055 530134439 912026590 810262240 708947075 14336239 692385496 491124846 335896229 399209319 104787785 311947053 320455737 901837730 369768920 530986193 457233755 163714406 578453658 438838285 306372886 681298429 841931463 802571792 562897370 185348661 651998812 718385604 443025232 649092902 337318068 883715283 380563825 386713764 240385850 23521918 295347581 625579102 37338645 508798378 290803392 620980283 592138986 836822457 578646478 493158839 432025453 903757935 906964438 135795686 566548561 856199110 791647930 539909731 944182800 174057479 78912808 650022826 558075809 188869596 629781232 571589045 874280394 306118771 284431902 480509216 515831234 103040926 190715947 101289410 669762755 45113308 564971818 390978131 99963814 337521975 656775804 797405294 826491359 414596406 28991267 313876487 521734566 741655837 749265694 212350826 753668892 601383088 137241281 334528179 14134720 424608728 859066772 983742340 860379415 666676779 661887306 236824220 411045001 519889543 247050933 614054928 195378063 891295430 652215742 797069161 993233030 724214337 144126183 506763539 242948182 963703529 827702166 703463331 169909397 184160676 178535559 78032615 21874078 795260811 961135260 508991310 481844799 982140315 115244922 480587743 4265560 514019168 225337142 762724258 185373728 938735341 830591002 652606765 552845784 497248798 207474365 198239414 858841270 330521656 817215191 133608461 157066084 959663659 364905977 132391327 718082984 314555248 973438142 292972853 312674015 395016956 543693570 717887018 240142723 280119188 433286571 294622968 55196860 729393840 285145798 414514235 867561632 473775682 163121231 842534454 142037211 901885767 735250579 620753468 331037481 502897990 394750889 658491107 238026119 431014911 436410446 962195800 332412561 345800028 354918859 802972340 196331098 259892026 250534359 659526847 214223163 244136124 615420122 283930721 885825015 281820184 922282918 361128189 289805136 402384248 485698002 448480976 831223032 998960070 443645452 478490594 81459986 890782891 511629548 444164792 595073902 110085444 387968312 129913907 941840413 199241055 132091854 271269758 3762678 847635950 185393797 578986346 9406630 361724808 392698963 26905447 215479779 947378593 631519756 892110088 344546706 712638068 33397799 936466209 941853385 75849477 955119494 265847513 16415 880198080 177252499 946125270 915941117 10851901 577379470 136307886 690968314 469681505 716323507 817883477 85888851 702840165 21176228 458459394 147898777 572229611 154315820 835036926 243751546 218981875 592943015 916425170 964074815 137724139 624156729 453457677 374838649 808891869 544587786 726061171 843247339 410829342 260387121 556443616 683666913 19488846 328773173 146866448 599578551 853450379 201761424 308602343 280949412 97730018 60361814 188186397 880926424 821492529 620361466 632730855 418576465 491070189 619703073 165354560 210266424 851004449 135963138 552004476 461302211 720887302 471994210 761100795 817663134 160783866 342978227 85222095 402106342 757390929 738304536 787390538 830569754 41508792 206679843 745123356 399665652 969469742 251478407 121448161 10566607 279060845 37323362 119819506 471801124 492662307 442874579 789917918 915522917 966873143 862509796 260219878 118588955 774442210 499383557 86371746 272095130 329724603 389988118 165583571 953985699 742780430 589025131 135346588 668493498 82760432 300443732 430688230 752424071 419989495 630531790 330109321 995376615 873265351 502062623 523125906 525138166 668615521 243243484 275557415 280159597 195825816 135420341 950045292 356295773 786801786 793187648 429682091 143215083 790325478 523017376 619122666 468918267 772056414 665450436 292331588 462952514 306818204 790897738 180038717 918373403 386416084 978806264 196087734 743081255 989398880 646993742 322560267 603124516 709030058 991638621 428711911 892515444 634052677 908741029 247741269 589765310 385941369 126495804 630346173 809527448 182306871 472190958 518311803 611513328 392273264 356535236 378655116 505901816 885132025 416825651 307758006 884248548 386450342 898783368 823628296 166649782 984160780 697886802 599526033 679523626 847359280 535916298 360029301 22315737 218023425 166438900 882172107 121121038 512715489 55986552 704042215 931721679 416774653 402561531 605434115 762852397 748549077 120394542 737949402 580116471 368048067 136554120 850583411 987853474 959746721 780981411 955012507 809176464 412379500 237098667 889181133 735301838 919864291 558770861 769919778 969500569 953692641 619950948 518626994 927516284 758636011 407984043 191567100 809896739 706031070 41916638 327677739 197963119 20617195 8793656 88515794 568007847 762133295 240465029 470440933 168431980 109626496 59159754 165519197 756827750 828161631 204917660 406309808 119498224 160356339 49686546 761088829 531092453 636843722 420871767 263942004 451736816 522185545 733265640 362285105 39659000 97935651 519564005 627828611 397322242 175980910 68963507 753378507 541285858 900816481 66100170 944933074 688425402 968044419 394573765 735716521 636197565 144142009 685766066 504283760 354933192 212346291 490931030 408768280 350210946 700565673 964547586 832804023 793698742 377766464 451226265 931487297 109703305 976995570 32459826 986176162 643424528 772519666 506555109 927325704 750966629 359817269 591721865 734649155 420025571 50408242 294532248 105881073 879170949 518711982 4435676 950373469 71214033 110897263 727912103 721742219 44634112 808098362 36312525 650500481 370389153 276209852 461920481 95287388 325654050 325884973 315519619 157265345 75554454 959421704 253332157 497521925 205357503 808082197 575650321 856548325 18112665 932110828 565950534 54507531 648118955 756966552 583222288 898505984 240642825 35140231 900966242 47062384 393468611 613673188 304417658 863390141 70336645 276145422 523754890 675769302 492363746 665666298 668406078 96080795 158928364 910517487 425923155 758664574 795389777 872146635 989948818 735190786 795437143 63621450 780516277 233515690 347503022 546206681 651754962 575536273 354017980 296201052 75810269 384264090 92668779 29825952 917016237 264011291 45483629 393297557 557959941 921927935 739022194 954957332 465073808 23747767 73130118 460413210 31693115 915459646 87063032 658640640 943880602 597725085 241635684 56461625 426842937 879735770 103321394 340282115 426545883 76474586 14084822 800310326 183304383 330838434 804848135 158082115 731359283 90958110 434254155 216618016 724418648 387576023 237382342 753115724 466414146 684643080 785703491 771557500 34394988 969858599 28936701 394822098 73612805 358977702 411961948 631966461 707168825 369365498 942558166 898480203 585044686 393497223 276419776 4225252 926832493 329718194 266591860 868440779 449905534 710988309 94540906 62468043 62884507 397799419 865254437 454920732 205078314 694301220 544545467 433571591 754765889 671978364 969278414 251941990 577167081 981733145 499751391 115038477 769688844 761857123 722398365 715272298 346216389 698855449 314973437 106679756 295538231 396268732 303944922 887801826 504249638 324546039 73533413 246549618 640776175 518343553 339868789 498333441 637736262 971940035 952205271 287199486 228149037 429970381 812575384 435029762 784640398 177897082 31859698 484608696 993789968 896338066 72307294 313552301 381649227 286367711 271746128 888509556 384326459 999400104 16329967 14511795 623089923 868963694 509791218 387448328 579613241 781488889 799764986 685936053 850273658 848288047 778917994 479816682 988644092 998676381 592123461 977367917 383148319 686351676 187398546 396499064 598376110 236496264 255502878 880645309 628571910 549678533 166851747 897686066 395491297 68187004 649608749 268591534 586481636 61518611 268208562 173632429 239262163 440798413 260624484 864024843 644326073 976644931 346418538 120487746 937894665 306345946 911140486 539827395 722143242 339714081 564657614 279985812 797030496 227802013 230402172 844909090 307822514 211786022 547219602 676895253 842510646 929309980 626722824 784947728 905262973 949852665 615001138 55360962 535328737 498880207 944111748 565705117 877105671 856800808 390365149 682411782 188361957 901343871 55592869 562457660 482719508 607675270 226547534 707334573 149463669 569451532 599287624 255783302 546742220 245620091 335649450 879473457 836518913 358341841 171886012 747991633 485774190 883800232 669121580 550922699 808729775 161006789 399866899 104813101 214328337 85230804 531497053 607117418 874188509 951739623 365012845 142652291 380060745 867405501 610537534 599065557 544688588 404406291 770387616 951555331 84643051 255397561 598020094 50503401 952040808 15110970 678946739 409184876 620504249 61764370 268450799 521994111 594831003 915650251 437937375 65957214 634760795 191423838 760782613 785428227 337533384 76997225 236830293 571949862 868394616 633585849 989653111 676971235 991762006 928046777 297007129 728179677 846772412 13672847 834653608 975967353 547895559 721409502 448549692 371979814 196352294 305506041 841633515 43459867 516649360 553637966 698854542 179093603 681084923 734891988 48735316 485734769 443509366 259112350 602529340 661287580 603974524 984058781 732635860 464773208 382501 565056345 373213799 184474210 674245601 348545804 199579532 440835125 491930326 890535208 779396373 636690002 493883726 956918369 205828114 619306519 105509814 341951264 730830110 869409934 450247752 838524372 926619745 791387091 718327749 500579072 857578084 322993874 39793223 957317979 181159896 183528522 381049021 739854428 491030596 740415269 547294225 921944843 916692574 451325062 465967077 481042264 314261046 404503057 16059304 997214131 404564109 56148312 773857863 869290235 181443388 61536636 41931116 31100959 901443645 248728329 682545748 361775267 371295121 670326744 178361345 850180858 821646450 659316365 164650487 889347309 762926346 145045755 903506978 168507278 367366135 910320508 111636651 91933193 537817446 37626482 859215389 633546972 84686171 814756869 792292375 656691598 197624178 116882322 947727813 897481438 353271647 364752757 273485775 752880085 124773025 7174846 699537590 458352642 994907318 970685991 431954 57010195 491693081 6164267 79032458 782901721 171082337 556183482 355103271 896602372 771640845 464058040 965281760 929466329 487911221 400254762 880085156 928676378 213283807 921895236 253409805 338268210 538402563 834120292 150942484 928034417 790423501 856191556 259898136 465481273 730342175 296903436 827693837 449220626 290604365 241045058 870847223 895718983 428285040 585995859 588536115 456234214 585305116 462990518 517628348 228801614 694285946 90035476 763197786 412093138 628619181 852299643 394928107 885026649 878400418 209812262 533772183 469486192 40111221 484718193 77169490 213463986 978102500 162665634 189632376 262467771 992564607 59099170 309231689 759489512 446177001 28252172 365168517 337376807 380135464 504360210 322370410 542035428 238317566 107677099 965203867 983171766 723643898 389823390 529055943 567784184 796566025 976213603 763400807 562655900 380064988 180976044 279055137 451567245 665254383 95349666 306761532 28839938 567929320 220995309 584537124 701831652 101167355 921874028 307734367 584060265 239028612 371246610 873253192 135105098 469646421 498372430 978365684 906352444 109389592 75982395 32020628 952383731 513951709 405583400 400913477 999527055 922381383 412039197 406621100 882853358 858456780 245482335 377103074 26102404 6757647 740691892 344145627 224584399 735643464 260054740 289785727 298027544 793937180 777587526 853980829 756726003 751803312 549333221 783716472 431807211 283926580 302886771 719219883 672115660 781054108 661848125 935120750 107702291 746892766 390310708 951393316 51375925 423489780 8597551 507393643 78729346 457006033 339889153 272278177 660352832 642747771 705570440 590056144 969449562 191304890 685734684 264565682 879021473 405898627 777702706 731868243 331036824 946504189 413611643 507872494 252600989 46644316 573677502 813482828 829456652 371248542 300356262 367698319 728997492 393942190 543359851 992884343 75718013 493961485 946440254 501726240 428674039 426863955 640315927 940402589 745991815 544508221 221407175 233242789 559883313 498050929 779772559 662433395 598157149 345782228 923050926 985827292 228967540 308900034 412627990 211188856 979078825 950486650 59310163 184475274 743434542 993279522 871329870 642314026 412892896 559785244 765269391 705009055 1407357 779372037 495404417 229669772 826836668 24688253 937348451 189421629 789773284 929830592 387653346 233790973 202660384 410874546 391872919 319976385 894435970 56078991 285600221 611787223 64276078 685048624 834789853 511931050 182469414 620931875 864176180 355272399 319754712 723993064 252273352 76231360 966601275 92732965 250758661 780787347 243342268 779078283 967253111 521579856 511705005 188999258 948994888 259641180 767226457 675895492 269510059 293166546 665147425 259493219 566879665 385806778 960984868 732283400 135933907 253825189 701396767 225102761 707226674 436770772 292768882 719013326 744555040 121572626 121364867 742346871 248242087 605629437 143401520 326104032 132292480 345850543 480341617 486150667 440714895 334570894 556682644 135096563 580505381 531083473 967995420 315320021 388647042 787031147 382126268 806599556 884054610 668009740 661492197 869997856 164139421 792112114 743540003 473586062 750661287 931400600 373455613 49062557 43901314 84140990 301109392 184477687 12202814 981259074 992862668 742287714 197383679 626289791 97793320 477457325 943856488 96417503 549601919 922871235 614666362 41365323 598072543 198975445 487664021 799735846 241162845 133180541 215432261 626485413 325574785 785185656 283573236 406412293 432954746 76492687 723757039 47873922 908937484 78102305 595770502 52801216 590827059 997228329 407406436 180706256 931816777 668709308 930024312 240436369 121885141 283611127 454277837 67814298 687041128 653581322 806813375 832095711 634027147 844518104 811530885 962532490 113211808 444911416 196393726 863559310 928073276 340704069 128174640 762299692 533529790 491908894 284492935 104825087 535895369 776019800 431249419 95206896 471711401 177709664 65169190 129921524 142945041 715010659 589816233 397672053 608368986 801174526 884108945 887448474 208434153 321189033 773029400 23967602 519493176 993802614 943010205 325567750 38514377 700303742 5821128 127130237 163090641 853481209 455873417 357959164 663707764 348940784 622876533 60310374 545732048 426106671 580187436 625637112 109637799 558246649 913092754 326214202 54885080 889587103 78402358 416339523 163298224 844877961 270828978 469897952 23695261 230107184 142734512 543737723 946988102 267138377 982507708 192669173 325040007 94073818 787389248 877901041 427900211 903074922 72846546 598769503 966672676 448847526 635811494 237933901 457878452 905116483 127274512 54095563 644368512 526451786 627366660 888346355 855157897 524850597 654696025 442405735 67911687 907047769 107838565 295218600 5274570 385521071 72483719 989935598 886799218 121808951 707628598 11902996 88046650 391752743 321494360 258793321 957247820 908340990 534838585 69618905 283366275 505713122 350662283 711586915 600583396 942075447 639477658 262266289 763162069 660165067 412138390 608036511 62151262 121764160 800320146 726290638 777902101 590484689 532582587 985567704 238954730 129044485 435602012 863699917 278438831 160253616 309306177 393785088 882026867 969216881 684915129 220306869 563741976 824741846 599081327 591010676 851455849 373130979 591102328 300308304 735096708 414983767 149013174 355629997 148420612 398158579 910078097 246326404 510224722 261547505 285667366 454765747 59300125 546191492 379432249 317470566 139123545 524611839 262419281 281407776 17967206 153625976 430331686 580577614 646095093 336250241 346099699 971500345 468479399 390107051 62822117 184134961 878535771 620998445 769773903 408769298 802406154 857570833 870486156 923266912 209900860 674785114 370820263 616151930 551215951 400590674 641132622 552344557 451138854 125070870 361380802 905563898 866929041 634988264 276396841 139208489 236285233 391377511 982643521 236980885 806822425 518321020 536511842 883773114 564658989 94093232 907317044 850566048 516833745 309598741 911196755 221696266 30420390 316105998 208876023 762040194 636087458 462596156 854905186 563832983 900643066 968906858 814633625 506336856 307131382 676360363 366893255 976105433 68977638 341808018 986474097 252058142 77303660 686673058 46533687 728258429 299907924 642918008 482124377 891402593 528260932 148158307 818626267 395980576 863783305 403233493 719391902 986096689 268740594 531455004 112312103 493803383 863543715 533361736 22145224 13212222 983533727 828070722 731734510 565624210 889861662 449614806 968144194 111104154 387821142 279165958 538602379 166736192 619807503 493918903 887594750 876275261 844196114 770253554 221159972 576463148 483407398 902685310 773563747 95164362 951835297 718261036 358430641 526659376 3993619 396799862 645081546 631306308 50383107 986965657 283616891 156975866 159823831 319425352 374635685 344539432 803937854 827572919 616610099 256541835 837535792 531192648 215248414 26982140 378710074 1908875 384035279 369094199 547602604 451481370 123541511 481091294 392753948 891555668 717062325 163436697 762032872 275552093 972736751 911440379 920642540 262415389 464801555 401724876 452055763 518978246 860048206 854432475 983093781 255792629 292726138 438702289 835843402 220227997 833814067 350822596 165162477 420066539 832805060 153077056 855754366 445863875 51740850 466230029 211758702 368418159 33642610 719061460 186601020 439332380 746698100 816012131 764045664 92014549 995341313 52469884 764803824 490179336 842447217 863270939 321807837 12355524 966489300 895570278 25589043 814551021 795331519 842898020 104525182 332791812 478153042 723962177 146624481 851192388 123660086 100771199 289899620 250526959 587961256 391556697 638598087 997956442 783825514 476773449 919164848 11377299 16662351 471174137 41883860 922533961 847846767 322102913 931982380 172200611 157662312 123902213 780741965 830549680 984808217 17765196 165579327 222889980 340394567 31210343 933672831 221400748 628337996 897975617 289004685 705179906 469528458 825312355 675208305 374683262 435075008 309487872 627626630 206206503 995035253 933447861 211212774 709877671 453508534 575075179 803907220 633481222 158821934 274917141 253879902 579836775 50640880 689614015 233346925 118003231 541618412 564998549 519053925 18039281 13778558 33170808 51225463 913824995 236787636 118702853 187124838 430743289 865623889 82623907 202275890 120999584 832101227 718005060 981939333 991426057 440651884 355763900 794609459 917353156 669377839 323313870 90726071 605492836 563628326 238022192 572806752 767833924 3308303 437858907 752956380 593306999 787468819 405879375 61108228 763382952 687515713 832450268 554835321 635500712 461462053 507233948 352569623 856739636 122938805 440098856 551791909 759003465 774428381 831068889 575428169 614017936 997815958 753830195 279633804 917586039 623392051 394927258 318166044 870578927 191911380 230272017 925380826 311433136 538823163 14064390 774584241 832169178 370711053 365992384 298104247 292353550 307799675 478890431 789274269 151600833 627890225 196041106 201150350 159776338 49882192 900696364 1884474 315808805 765383432 597674532 800196873 216891523 430063247 48124384 914886611 269907967 80200795 578674465 941248051 960182896 242469467 659100844 322310834 838233612 951790169 790316265 755830936 428251192 877466861 537738718 351772102 980865089 308454925 172194433 53882789 12579757 124761610 627823399 364956192 868035432 422638994 931942572 153353809 885604376 168284293 685600120 782492005 12066293 316112603 196807904 982681547 912064267 725519374 16263591 862959732 227591074 356549932 465100323 33801191 158676626 773157090 857357072 85902211 176195107 746640794 197359882 426709559 594829176 302540015 215812724 569073519 294680854 714286864 984652370 633580122 342771135 716951025 572350211 473451609 365255312 91609960 853355547 524647619 715414521 89172235 124801115 835552724 629090009 911752866 761954802 319926670 360525164 852883032 208239786 836625665 458856474 41077853 88010922 763039056 508624073 6820217 904440656 587150510 863733556 256876144 426580535 482854527 664558997 664050039 387017604 163038525 15578239 601576579 587954858 172558148 646797037 134709497 871249923 3418728 794271952 155693128 639383471 173273410 563205217 579769920 62276901 816859415 10116759 976520298 286822724 813415038 536398242 903762466 923014878 230542766 986221364 890018029 895620782 207539685 295355954 631402586 812101510 911009910 819419418 215137545 966483407 290930086 47816803 361111665 49901332 668325898 704180037 18540565 452759230 117328562 628663939 173946482 548261590 957013963 505162132 614462226 983252334 615809365 89951926 840149296 42461086 515398780 557636551 952046818 933984527 289652523 274323395 181119664 240030310 715750429 119948977 394241725 795435522 297589352 576318818 221854918 484975030 832702826 4357249 3274377 241131343 496979041 224663115 259558626 640640807 523733114 708652144 984442740 496469120 11323030 370323908 93615738 670272568 183198539 630504363 504691467 623487068 821716408 390236917 222523130 571159567 269301673 267179829 538654621 395135891 775462023 903006302 960070823 831564375 133696685 93169972 424123453 707089862 274662289 790460975 691368372 720033344 924846471 498948572 531388589 418645374 751745434 365939265 8476745 301713565 496163228 963583105 120755697 708354942 308490794 58275357 991327499 34684392 140687477 908476460 603653483 896045004 34119713 488701380 34607984 682036721 129958758 282307881 886481184 174564647 492500038 304964731 190883399 314401786 732628239 525407322 433569554 56810188 296823503 34701822 167512475 91690035 848065710 771257001 524297340 634146746 206614199 79770161 818347159 247532128 265302543 354566969 769642671 649541837 324054598 111845416 252565411 353478798 235806689 517146537 905686090 279526544 427359167 517775983 214423569 60639405 798575046 724580235 419166195 188534526 971333344 788642878 960279160 784452138 577619513 497738121 468760213 680218067 20450589 586894433 768315001 12118574 929410393 708330712 825817914 341032577 760704279 388696872 161269988 357791078 603356530 534608001 627757502 778703265 573623472 324518704 897624663 971580868 537587919 440865846 935817794 920639588 723428286 848966126 833162257 28712908 797125497 949484321 104756796 943831916 152241418 10051267 34942625 35993020 740809028 25121601 271502660 540609777 661425282 380521841 143347755 271816315 262550926 927183304 740040788 290249926 167635850 666004564 904647890 954897066 529169067 422668662 249725204 470423305 495704999 688692848 412636343 287928481 479121647 467344047 183203604 628286442 595836803 603464600 475662282 45065806 336930641 955829830 363546129 842199339 238168894 975494812 124094844 349411732 15544060 498912897 81492982 281133941 248394814 634194999 559990049 746093049 611595841 232377369 258759974 473544153 683378086 496010139 503129687 820189171 503264614 42640681 326641549 721408757 423732499 352639505 544394669 300879485 822906051 497734933 373021985 141123742 901575322 893080098 121940318 600231872 195132265 807592887 953474885 794536478 585158241 943633540 314131664 39215892 987224630 294779106 869485992 826211450 748635698 151208568 766064851 26914626 353917059 235762867 486145736 741398015 606319919 199506357 193877439 778162266 609006003 570922958 139981944 897014481 284754982 919476081 202076393 431631125 312355326 875920149 408644903 18374898 813092476 84724356 190551675 484724960 683365355 350312754 199760262 546166887 954072753 394802072 566339718 998257861 481182936 23162036 706752798 376717526 501771705 235703242 625158727 133437328 417082773 56774135 529725244 403678737 587751641 535118284 996147337 369639505 95613619 812657318 676543870 17497905 181932975 491171453 728433235 496156625 141291098 871719715 976690431 27380732 45914228 66137206 659939438 96143604 513523880 372393086 679695963 499457367 848002527 872507696 655670911 290980830 447164924 932346709 738580296 189353478 489411530 920846264 7476005 95550653 402725330 594013832 497469467 256244809 292527256 929284026 464857044 369601390 558182324 880041450 888706301 681383297 701670738 513998885 337306002 678854136 422734050 99764785 167034570 361871649 259578488 128800774 151070535 874043277 900318621 707002063 850060998 372630998 269581842 822999017 467121863 440407566 907621078 72395285 313115038 206875054 235683183 638982623 607110064 725581494 731236848 212481700 994300853 856969643 158553704 105628583 595912654 741922114 978716267 320298807 158537979 903980654 612619285 60831068 312632422 271863749 561299186 853472005 593209634 166980021 831070577 207611719 188400019 271280281 936315463 934582386 129036730 339367849 208674847 350515662 48126053 706066360 113215122 216428480 842657177 968252091 64263580 564757130 941430023 75289635 163388744 586248898 405885253 201415986 815364177 989941398 715682004 161307914 701061091 262888604 231166678 848660082 610079764 130292854 110560208 704801508 303718945 721686900 749701475 468895721 293390310 568229464 480860426 80938735 133390761 621508192 262310085 295391261 62744979 636855692 817987477 923275816 904717729 326064586 89875474 943412411 685735079 352478421 937523498 502561158 70970473 478217883 602676343 112385106 657949593 243622372 324903433 989897628 784743957 162268480 831597303 596224920 195848 646455076 74168978 171888471 745653947 295335337 713252639 414869573 684350337 183517083 707805264 873634242 907470829 627175332 756472952 477182625 335361464 202140614 241665894 798287686 679952901 879919687 896423597 330497307 388714591 949449987 307767203 341189478 53216627 313091877 865855007 926411904 272015769 80239817 192635970 152097900 447728596 472416758 176745674 879557431 102555 400916319 847686414 381925955 45010350 607819583 451140045 400648792 485588954 700507627 162953864 606379487 106086325 168055806 482656545 129971405 115708421 834572458 314658418 428109160 936464042 381138414 90774364 894915472 665590348 265314161 721870280 487693429 987905162 197417893 860071204 85011233 334252821 653549575 978914484 250732031 47929069 559408280 76369840 72200892 93536048 941915303 175911413 68049987 648023686 586402105 914313815 198112894 807517123 754730269 288523135 538257149 394987431 896549488 559783097 724619044 121888961 421919073 118014285 634167138 305299663 548956060 72145354 373677819 70702613 177338146 780905758 147409083 417218137 701641346 461453890 901770735 825535136 69657793 901531800 692509952 574825430 338291572 833709093 757450205 745415759 568968131 350722450 317209635 12525508 603964898 465083130 713958390 455320604 583616705 174482624 698569635 524593336 909951068 186108305 112031211 473646026 103232242 984820268 891706546 526838617 596006026 172798054 549930306 883885255 159753462 930774068 232717906 467519991 872304395 455422479 791955417 978037174 813259415 448407009 482521447 487298583 245084784 658608818 248145816 238913961 665782502 867320074 531477141 422002894 57591428 574287164 271277534 214817406 683071367 315393955 857101288 72238715 848977428 15899794 497052611 688865062 376328071 503526827 541545078 698926169 200660226 854166834 242072938 315352916 82862147 391080109 952575586 719896508 63589252 786135483 402892617 777299114 307904161 868623855 885111976 460874352 33544318 421187952 971505667 377143046 276209299 78841823 832031201 232836460 631336670 293902921 229289939 739458164 478479176 521646478 768216834 2073184 994748061 486381416 385840060 303927972 887557154 193616720 912123230 557395820 764774259 367677564 397461780 878604696 331949380 30146062 943953064 867239247 732468656 12886776 691918952 46937341 530838480 98708450 823684810 378219958 663663048 533952294 448027090 285377262 292149738 994177606 501931358 181649797 563028381 984045880 102490120 846077033 866106436 215549880 470439539 782434192 750702399 688097827 278345520 851706745 631532073 879820841 199224613 318667283 201066295 905328805 489040503 212684200 149148558 116994347 967052999 423070475 229828365 876932337 997929379 657841655 400800694 268722040 701096725 473126607 714633817 247132489 837998217 638588069 363273933 26385105 264569886 999005634 699715752 424314288 557040914 51642222 260607791 11449576 215763307 615285864 582345972 227724806 92564435 807088192 820608181 800450802 857631827 43413759 320652014 987253004 255105712 127121970 129695289 178937217 982038621 270728594 101287084 35514112 768677086 763889314 702322208 154646314 903837562 6073566 849063890 445028750 281425929 541180219 813900003 221156858 535615943 956008763 615344325 475881270 820257185 442383920 366210184 653575424 160182932 137365978 258532139 861701013 56283416 923594419 153523687 972254664 987980683 633679011 60411181 190245541 113216927 183832307 287351552 763793164 847194532 897307904 589148864 783241163 817452103 582603582 999411098 470013517 318893993 366187560 400337722 415678628 973298738 689607216 184317147 196952688 342688042 230208844 627702476 259994221 998214347 71363588 647403425 576633367 99772672 576363339 173764143 909769414 899924141 812063837 756239329 971946935 702778795 984909637 327526885 582762623 243398004 732205891 773536165 203450163 99499643 227132902 7141435 544841696 784150049 584600005 830667985 472325384 492215865 772321344 718068777 153270240 859088294 650874644 606195535 997754156 847070976 164184874 985041282 988048114 733864956 376860511 697546454 395384765 316473767 316507072 100785983 531315304 790594556 227731622 836292091 238131380 515095076 220484346 491184380 768360345 372262834 892708178 776979993 714982752 986277465 743404537 325313488 146936688 836554436 434818258 403763440 133708802 639806207 181556535 151837286 257686743 679113879 54260707 720064780 990223522 733752226 995451724 153136274 137724656 993975736 801387122 7236484 354730853 713939257 749113117 876201407 858620342 967253943 967566152 507499243 152190121 467961946 195741855 853132020 536182811 364210340 845407045 58341050 98956153 400650137 971581993 902057993 940167317 984866045 250817962 610391087 905086878 544448939 254450312 838511780 807346445 730437873 721351917 39429935 462941701 782396770 227307455 960383593 327432542 812035574 567108006 209994089 215058025 95900028 428883872 710845263 631613973 904141851 536347778 228560668 235824043 565088708 575207261 872984711 700617278 964029819 166664400 379631964 50512552 266314036 619413894 753222865 746198868 812858633 54436366 228162722 567379433 8742105 336090626 463583634 881915451 436479909 97094144 566458661 645845745 167799836 540069406 961124129 189633183 202045408 23934584 848021263 982425523 289295064 895888986 658345081 411977022 812988763 20308060 841764830 115878670 522301353 544668482 896163005 728277194 69542933 171268353 643130586 604990688 556203429 2972537 496849606 570578273 622393864 563603363 922177382 641504016 149054460 340001586 585214325 968000048 891715482 86005348 320206306 351292543 217758669 157456947 851585797 618165614 123960134 807547896 541763341 542062235 74443205 633167527 438177392 727089972 854408251 505451529 290784918 421611225 890245643 573424686 233849614 873524733 538627490 728426663 372697671 193353069 346070571 696006277 472461358 55497572 366261318 547058749 309717554 814008192 633770124 864733612 704818863 647242016 508071241 873115363 89105130 871573183 422007079 941531011 982253936 872833793 627478339 851892975 598467781 247515529 205695254 221078287 995278018 623971143 402371867 142561894 884917015 431230654 724871397 252763004 611485120 654951543 728649413 566135375 547419841 70961464 53792763 717218436 148908663 823164285 258390768 130634827 642435404 887972055 86369424 17956832 56394709 940626134 288144701 321988404 746235389 12900803 848169219 224346456 320073975 538343787 858297881 76709142 887029102 370795932 195362789 781400930 681498155 416221493 478089800 867762710 511917514 739242675 900840604 928498015 976997872 840227540 10726442 753780301 320920046 401676876 410912927 204588164 809877027 149025236 641016169 161911678 458881824 673257990 914416454 983040850 59478181 445892844 128122316 920623063 281317094 534322972 163384609 622328201 82334391 819326836 651567038 203715131 696272374 338246274 725546222 499365678 477374663 168424283 843008622 798981848 325551161 323412421 201030022 133278559 426840977 390719577 926220010 491962948 822815515 997927316 752132354 180386791 50918687 87141355 451329777 183442096 821956920 567775960 489424547 805651929 39881483 858794559 434556307 406819844 398737927 156210077 872737843 181092748 465871560 421354669 344820764 946302670 388674264 992124846 692793461 36325238 552881324 1932145 950749939 359143332 186850984 742044419 645711473 108785227 918450556 965848981 592314508 76048463 882194493 490481058 161433049 800710367 589396320 81101556 468580509 898719396 170380191 631392332 800366294 403160771 573351025 864522222 359418133 48121345 959997885 449045419 181572030 643378446 119934077 14503500 686544541 947558590 152013164 600860154 970834102 36280679 297804970 826984440 296633111 893645394 339516292 653419238 283259451 367877534 809670571 857714950 696341625 123448687 990537849 915368729 171567417 641251560 996859242 764715086 981505136 47126415 524143722 790107749 791228119 311958835 236415715 261196786 954425378 303972534 567901613 843085459 442700504 56805279 403762438 388981097 384807234 547830486 32120274 13311119 370283106 76080314 317323798 550841651 234077937 366979804 557285973 189841700 791303556 873510626 101544114 815530610 26583860 668218643 501846850 780985194 391485414 715730507 104699125 507253115 16494646 28309181 231011247 683250571 43262938 1563823 132167704 227095942 946546481 417869751 850064832 42593294 385906193 229418379 841968868 571481302 235077074 831962557 942830797 906189399 536646614 645534975 74911375 364851041 729715700 979856654 111844841 49923456 264881793 516126926 582760892 424794207 69627379 563193059 975683733 316959671 516180485 798902399 806447180 409850120 108483750 797043594 301506399 431067704 921599489 697521877 149115151 149415967 7635244 770797473 261810599 291458190 543498884 689225821 440855378 521949671 643086355 611989661 426599639 145640302 370613176 522759729 445713665 461257883 90270465 674410759 251465329 780139758 221219752 708089177 48282649 865492768 483416867 973232671 329970604 462064788 439548673 31227673 283583554 331635214 972704735 553887224 230255561 364669427 177830504 253222466 431086577 270229817 89687898 359052567 874313562 516579242 298788570 705212700 458606130 587728826 503708293 197880697 31598652 134481720 541142341 243799765 894577494 292664895 272020645 195354340 903605164 456185554 909530890 78559670 855882141 679891418 306082513 548666650 382281001 810377820 107150507 85911406 910759333 333095265 16053726 848563548 990853239 231790012 377860270 729204793 699401512 622687830 101620581 447597794 3048477 52895376 933392556 965705146 718564322 380463276 121701335 588103674 584866295 837552758 679823911 700221134 739214795 317886073 170598687 127871885 89806676 64378556 49386508 584048147 489943515 237879613 681474397 648825453 668333863 527085830 915599513 847187132 210367311 457191486 493255276 531391943 110940764 845676899 805078560 756868074 119448505 526518966 957515725 388026701 799780402 69742279 767128810 83004214 755451539 556408979 525930021 468591888 539620947 72750629 959367324 656982357 644352319 782138993 397565792 34293714 514746528 6942846 744206551 57620580 322627551 944765013 635524896 496390557 577964551 849437903 422751995 301103712 899997699 381019288 630121165 115607983 577898667 729861095 860287239 935893223 826614294 146553828 2194783 728715913 599973923 868988090 133262403 857195555 969448191 613054904 772157592 84381229 595967678 285933875 801287642 735785776 830720090 969541226 826843981 790908905 825217964 628549053 334742292 10907920 167997698 861051351 701735524 319013029 299831081 8023873 266846984 901752776 436638546 41784080 662725803 196426509 923672302 478237054 135053365 678415749 789186691 35327617 7590216 270313098 345748876 848017489 34349534 62625713 915184457 279630309 439040719 40186766 584255830 511442788 77896953 180601448 55303786 509895332 317158324 294522835 706526916 632366108 815241215 358781661 181669366 6604967 512213573 324497045 945471977 756732047 619372076 713625133 584302455 321781471 887372884 762480974 721574244 141740048 630222860 199266919 906378919 558024403 978455626 457398608 596534956 311453689 991095457 101218647 97749869 817117269 995426708 134588710 32454757 706390439 366940926 969612975 819942635 391257625 623628120 850839672 46578618 361005716 389259971 104739066 144166062 362330139 890649323 257209709 36726248 702193791 824780002 609810313 410983468 890889123 560770518 852030524 98995384 991726692 750840878 695303889 459093224 127297243 157631271 375557300 648958481 606434594 436302773 941277378 120174369 601763007 389521847 177198209 833756947 365038884 462449585 738058349 901324462 728395918 985136893 217127592 849139308 703220037 178533083 874609238 549572940 904688562 924779356 751454327 806859874 958546008 336367094 440313927 137861600 131382509 395890683 766279359 313176836 460977006 638646020 488259427 974183216 124934756 203330547 479957703 141954131 880996079 235284637 664722342 96750527 390503864 227363635 657291517 191958385 282562259 51830520 249078328 806728610 557858347 169755387 243519408 855422968 534770046 703200386 803788716 572635800 937552206 110508599 957963256 973334865 657508906 85041014 573233905 857114416 89273472 806942830 581679826 294092582 600706108 893700920 384810288 850523675 909133923 340841947 871947410 233820526 1170576 455730362 689343209 498842771 913104686 338136741 915065368 713179730 79087443 730852825 105729174 429462464 84167976 60584939 869584762 100963070 607667330 956413937 806417426 836017753 773387030 750486800 711910485 178164346 219763978 999691393 349817516 842677450 627681876 776007818 555509600 229404719 990900781 532917790 591089206 307557265 786647838 982518969 189532326 866595055 335280195 748305217 694411733 673528223 533530487 864347961 557115155 550692385 807494311 215196692 480060795 557589484 241481633 882832565 16937883 524758365 418225983 280893497 932203404 279611564 528043034 87554634 765857056 152046393 11667042 61667152 141959741 476942030 363885477 494432802 477825084 873909407 604826475 578940562 527315964 967501045 262013262 195792224 914876450 741732545 273581109 766330401 48507092 812942309 851226262 892016690 386985579 718512444 305014830 272979952 78946043 845061313 641636138 946084747 139425870 795997577 975633763 482467251 119313601 461274663 766888932 12796207 100668848 40664613 792119168 271101183 575289618 936842883 782704748 211651357 450875469 450311869 965491528 267854952 714191346 334370198 676531207 628059909 124761823 1617920 287400455 817576492 914529646 129457113 313644248 477796612 766062526 649026618 823997375 518021371 509547036 110860560 276623612 334262083 872485405 997321948 644737833 392434703 939473068 500685140 973155124 612941257 45121787 59742952 933003691 475407216 521092652 15616616 441417920 636311338 582025839 422729558 487272336 110654392 812923409 700042485 283726864 228153965 639841210 687767599 792079808 167945584 15604451 178185608 543188671 188066914 140902124 476357197 670947551 37359343 947077599 181039225 280255085 395746631 786879079 529137321 674338359 606024113 915081617 610988263 929268454 206511580 439151312 270239701 977649261 71426097 209308363 593425029 738422282 116525856 344495777 311127608 437435642 934876323 878161384 865098056 45623074 904139303 763372653 487750883 730838177 976526096 387308611 867639056 9840781 929791748 652604954 996679966 287295566 514517915 624648016 110044281 675996409 2502564 846088417 964179232 874989663 701949976 217524013 405463793 419305738 869208836 268383192 167897130 428596523 992736054 522011139 595746021 389532862 495526642 107884972 210818314 314699031 45187594 513339152 224230206 396973227 520735706 334370020 611326351 310457699 120335765 207746731 818535510 41533183 227567264 486564481 152229903 573205692 295590122 216543453 311206365 495805222 649179657 52686322 605569583 155867553 444064409 946775540 13003571 275116896 895058955 508148778 137650318 909223536 647711675 672064734 880863734 474467212 129168920 637135900 990548337 684013939 640092650 565135949 811397257 594118189 230365833 744435668 34182337 803564890 698871271 386771441 850834828 611132037 58033954 622588662 647446968 485942184 454832914 34339341 260095919 156214067 510056348 526698260 144569794 111493504 93197036 320867499 590616148 282047300 771752246 6789086 179929020 540139596 823815183 553584675 216775592 316852930 24196484 321327179 13605295 723516528 989274957 395746867 858408009 362874880 551405315 639550430 288608450 324048203 952095845 274762012 386357251 466525847 287938062 682237988 522620540 7423978 707086319 808959512 910889348 533189847 227555386 140042877 148563704 156790094 338640359 600936825 161617636 572343260 863169315 408056992 324418187 728071903 78879345 811073 768589287 109028768 170076369 313937770 620892624 2954966 195096474 154397183 703384780 839460274 484474999 157891508 326183485 127505330 252434609 384410671 809325809 602181347 271299883 954956072 767070967 911635367 424478086 548540663 983981237 846206210 873651478 640097069 184677130 402013258 788089429 734808868 77427740 1351086 157173380 400658326 286526227 339007815 583233929 108030172 880567223 36985436 54560639 229631120 383940602 80328989 482043221 605729969 441029428 679875378 900183215 875657909 136241067 902749234 710483365 214777990 10284155 145522633 539284225 208975732 898104957 672252271 353210637 93244231 722396891 477624180 159352393 286485360 299678724 849523074 58423905 685553277 992974781 553149281 278209656 268893612 540863670 447378910 124035438 182610241 32962228 192464319 472093727 351663421 327003763 645205675 771374927 261856859 973112547 928441278 122890858 267384190 157908061 969495268 386561386 632047600 755914671 145123826 788280907 718161904 989549928 159651634 168894082 517339299 254913442 683780260 581579099 506001664 606495055 126568515 571194238 176080736 664060088 235135977 638553993 354458217 825289169 490579735 403080109 74976007 346862920 361243557 29588876 159945725 122500343 143298851 312031176 942218602 937514951 430302904 374342145 531264792 968480426 264380826 396455105 508404516 851297133 265084761 438934243 239600465 686341203 701995107 726824777 4042165 143325881 532635749 164468904 80940617 846969667 973004905 660028135 525850645 325010014 835129270 877717301 629184568 765755030 429948404 220831120 315263414 205572951 267942086 473237521 830032871 392859400 44770438 114895693 227565577 847618596 743178886 685399540 924745656 142102187 239311428 875381554 842799375 993177907 126228044 680749369 637093409 214732376 959514054 81540835 534603995 275630865 769195974 975514232 372010180 957050785 957573413 588337338 51404847 583155109 741028571 172942129 52631972 389401272 180079116 868247736 20114756 876381 964100073 271087835 831718223 241569762 92280865 182270674 525303491 159309595 168226951 391612700 863699471 749644512 399821936 751238010 936077570 197431032 844546626 300207382 84574040 318092960 606917925 976179701 289360094 396404485 771642415 745138071 878051908 511682513 337446980 326879550 540308717 949942288 546454753 529998241 88955193 205384672 709508529 235624371 427936449 331149649 128731435 228479279 663240919 345339603 164728766 321655865 206506439 948245064 792177182 812689732 643436604 340815836 354093277 108600441 642329223 903225159 523221492 986157994 364784896 876606090 107940737 284672522 229688146 577533183 82341069 153733556 107653736 624388335 440228777 720165773 734602893 443656080 536918149 648138674 460949575 604316880 830824235 299898769 556853449 401182063 163086097 397345924 365504298 739641852 707841009 447991744 749637657 219331049 536405010 145987988 69209221 884229005 858136128 803781322 365834081 872167296 907747719 934132991 656922542 657031774 451374023 968484 18832790 148486630 868236011 818937822 192396162 949378411 186694357 218350229 118143068 73096395 124090440 629384816 883503233 125569040 497269155 923121714 72705228 165380649 590974766 106824100 654233193 172511291 755277029 951219832 99648645 440141522 585041501 249365602 73937075 444465659 484974702 796220684 628372941 104038587 277819413 465714693 282845194 221293763 263774940 904398236 650135140 719396815 108666254 863011915 4437161 701381353 293474746 521177924 728735579 379141962 233699194 968538322 933377007 180071153 295709312 363192671 242503863 647874590 666047183 507999132 684139486 981460599 165032409 370600488 386891345 900879108 466982414 908373757 757413334 982465269 880298052 431997493 993655570 187058857 650312573 402473306 51563721 652327133 393174260 472164738 78237915 366332576 319055546 847715299 56833330 347130463 317522721 640861019 50739113 620900533 684573796 30719148 451622318 521689130 132718853 986998355 402352678 932015729 939516835 794018250 87319182 355493438 147355931 752500909 700655630 66123254 188082727 922970731 922780200 556871425 893205698 969314611 972840131 850330853 931800346 114153369 544260632 822133226 577344643 613434991 516090168 954408741 923180376 203661828 715729352 101761413 32081986 970458158 776187525 993208559 474928069 927062758 313103315 817173765 858114364 848633402 985088166 173554733 606847111 337878741 373067591 64197208 964876867 322521369 273387924 667203825 941363173 768335544 536939872 934949353 349005673 68606142 51723172 439743770 4458032 877343336 127862628 609467315 819156162 622166359 861923145 612450371 350388018 262361941 121263615 437293356 955465139 552881837 818648999 173264491 14548400 10165876 69505598 980934199 561217340 718327596 63603919 485766265 131595741 294785056 108308520 747757998 252872439 604592359 315609185 767297888 710810516 47347298 526757942 434488443 751934889 657780036 762243949 739449954 566383571 400222818 94081662 852358831 559747688 663431343 576997827 596726278 603432584 354180386 729797759 935098187 181379285 599476813 381634592 195818732 711491006 204085404 113173780 419969684 948982987 39183895 63500240 706410616 370171476 316719546 507728645 413906713 738049373 523629396 319023166 841066116 270288351 455490520 510417705 430168429 873965862 283528161 449598582 50017428 727582799 120865087 29051402 930616073 285360161 391984098 843628870 709194897 108269873 304756630 775099261 545601615 29890192 905954951 662745484 117172720 372385471 563739397 484723466 580451793 320669832 879450841 187365020 872368847 337215043 782974021 954793662 390035871 443175594 492533883 799484274 450285799 324955497 405369592 464400200 231576503 995172704 628806811 436340698 152759238 37936336 486422834 983140421 180824022 92951626 362316411 919634254 626534783 44800606 577060938 958600400 388144481 641498864 98461423 443174397 33011805 876853879 743969047 145911338 804285601 177270734 880887880 136131481 450154566 202975376 861742298 659295186 37885920 287732562 893154387 193135038 383525268 672780468 74417147 600277973 301998854 333463723 404050890 50007371 43565563 185306802 926208204 988277902 382591680 370108391 120101849 525294768 31359751 700286934 122643602 757529086 271811037 589018384 258358203 931601531 658474540 55916199 826382512 726100109 574322749 122162114 388060716 413848744 766688611 858365697 634607860 175066924 395748082 36567702 557794023 124623841 542243800 708154629 663692847 912983763 190089499 612223217 899488578 914369078 886541802 446642074 68178194 599293841 669114019 460683521 243580200 180949675 875197589 164753291 357007885 767848249 103502985 815321627 812102953 838075332 944634668 491545053 504019355 988391016 475128199 392061686 336676421 502081697 535695874 557041232 885554295 617084486 815069742 547815851 669499257 775735159 681329775 441940059 226871092 197438707 319979086 20152269 952009490 398637582 303227143 253552336 340613636 561735691 907428841 211277563 428550101 825109909 571004350 965737371 919537316 408848979 60338069 695719154 381506223 849451641 329926746 400494869 605518887 842493241 197105868 244520466 767166018 414893182 400781245 606882575 249109676 84022906 336039722 881719613 404974989 811736343 356789582 506787516 261419842 617262535 923445100 10500854 143677028 313396139 75028630 797896462 99718700 412012284 940316204 283248109 430957599 631693630 27074427 320118748 416816634 997010517 890067584 826909486 215366856 797957117 853458222 50995378 342033165 560863953 859987528 772924957 844461684 916876397 758461793 774864871 98922560 345943286 375676969 98542263 953845261 408217325 700339799 669664523 16091884 837191104 49721035 307593911 48695878 293384248 392780938 927443119 276495520 940965224 739381194 539440565 906081950 837841495 634985441 704844475 554979887 483288545 580882440 303303118 960113819 588128691 316111381 673552916 317096340 498526769 216654363 312669951 514604369 510806696 235382259 290035943 918936053 144716123 400855291 595805530 340076922 513672952 1201418 338224275 83321632 18606795 533244584 484885886 657778376 481948144 760118035 89065309 644686179 556882354 302735495 48754348 301132001 865148526 309044225 480083464 690034824 483079904 533095801 618154438 424147119 387429852 109332258 710389010 56497244 419553840 459472230 197377573 899857189 371947590 982472884 993760556 905831161 264621744 24373709 473738359 815280439 85083989 430229768 214702016 292644345 170501317 709113881 479937651 263406536 150125420 114695190 83575310 534535418 79388597 48099878 774608608 305886743 297978185 660479764 179531878 820575626 31612414 134486861 821032345 788736209 18176156 187440008 12601330 917119433 767115710 335624385 202757436 579264191 388818141 406898559 659571261 350735661 187784107 127824908 332344833 748218024 885921758 236866969 71245050 492526066 905046881 198700146 32005523 442987885 507120378 619442434 355243031 955723106 341207671 584458000 455996803 320669290 297503133 442786676 731376627 855697863 980147054 67345054 479916957 769966971 479372631 581599095 576111919 168337016 802667532 16978687 202963317 212454492 365230803 657335930 781835171 826608251 745817996 376560439 181676196 877230091 50947178 907249982 540624779 90482274 262181688 754831970 721475868 874476661 393093063 169153199 954666268 980644579 249808675 196232538 490286808 551009098 502040078 93688300 635076886 862809969 530608855 97793090 810828005 148518711 951578105 579419848 71316755 752435977 840623790 693916545 443147353 586073891 652089469 922437773 533355706 476070004 458244229 501371915 333868559 457960550 775091879 348079772 643342552 945725566 82834508 113017335 769188450 336909233 763582598 24584903 931332077 656179585 200928218 515673470 4608899 254483291 694195028 739038713 232305708 612465433 677268986 454677746 394896988 342225033 99152513 222086007 116872429 390057282 881796391 704776019 167342106 676658093 158794181 253652552 391534471 998223120 801813268 466817342 956166664 465888365 508089285 541111496 384551889 68318030 716091035 644800784 68477925 610098255 782533171 361545650 875720877 989658787 104499679 505830206 39042587 254451134 236959677 437286056 229679171 216803259 339035181 11248891 301903767 515726653 846916149 378517605 962426264 607713450 186972068 442617950 580004568 662654226 401798846 879233467 132937088 200997049 625596500 599057058 778227690 534619831 40160933 201333876 994497698 617387366 704351484 776197366 757049260 995313283 183375836 942257724 137921163 679896417 476677179 985359222 832793156 184521147 834823196 826349496 300414714 407482537 69784471 787004644 929837187 339486925 461186406 150166503 290716458 81613876 825296811 323086025 977790040 486703257 263287659 553088250 919677457 123393674 885524067 309664600 740318612 262990976 963225970 873895605 578426846 386468526 251302775 808181758 368381153 265964940 649139276 166440786 125157846 477511659 415566248 217422350 936401477 74877825 19753982 556823969 505007697 267147982 355679145 735466553 57948133 472875818 554242079 99566863 283072885 10286293 996724281 556939329 212862157 497644265 251105201 100061823 920115733 951904373 758619798 839602241 556319674 921806123 477736223 603191132 226963179 182281796 877102470 762653846 327883380 181599713 532091229 10848405 42001620 766432503 24649521 772488905 51825301 616622919 12609960 97297524 30720782 989017733 173035867 393101338 881447699 645367186 760437560 624595313 667541548 584845444 971264465 289467379 889533668 681904446 161299009 46714960 857094541 714574392 921601085 687747069 663618761 712485884 139478036 378949366 905634255 64306025 728723625 311683304 190506931 183046524 930946922 293322787 544422661 392205152 465274115 51126987 795832273 276211658 802444116 654018806 410405926 810593182 558443055 510565819 462435258 5640868 29201779 627440446 642134641 372121953 838818473 654918354 126452513 831332793 481080480 493095831 38787805 292328754 100779999 484221488 859866017 701182334 28343452 965612158 125403392 518924937 799023703 201413485 770082635 908852498 529847078 426440432 676756217 94462045 27735202 917988794 819449820 309970724 870567465 494752893 730194468 490769588 975722608 524429982 79370709 640767929 900157916 984281928 900908085 53110840 747117402 510948620 911054448 310724116 495391108 218648477 394840962 695151942 59500455 369474836 755064063 798393359 823367730 441602991 594608850 553175776 62934478 761568851 581970122 353773784 878694138 973165834 133781948 869550839 599275950 896986898 274829417 826022832 227596107 888193988 775242142 605909941 622379134 704963967 957029166 253183575 527988818 9648184 285338562 573485815 742315293 393646319 112214247 691332026 35488233 26094178 192496759 675100380 660156597 609784915 705839783 935888158 894739935 775033081 938378191 171411841 411679763 442478253 588473512 707700969 176558276 8379627 327432081 459873414 956552807 265414846 392805938 479332693 917712481 425093871 713146672 171647337 177710045 834582665 984791859 90859927 668863836 345988100 15620931 363703803 969061584 804764216 878599647 268838611 275665186 736195503 185070393 405878897 866316272 595238824 169794748 665311881 398785435 19193450 803311111 656500579 531174122 640918052 857229694 118072501 157554828 974797521 481497550 49972375 745285431 702936134 590491301 540778977 224186944 226055292 283307258 333197231 539330528 223065246 963658816 628440336 422510180 625877201 325867795 200653097 561382486 171849953 698157534 444398692 407673058 44953038 716333980 868642598 845745834 675732642 365985609 77101546 485776278 561911472 529363504 131094011 392768178 469291934 507843556 749955416 672455102 827503936 596824669 5833119 869871750 230779531 958628361 995945110 767886378 352929083 816456619 969475170 50722274 547691266 425399356 941118331 700623589 576420985 2464852 957915045 739449241 263054236 689011003 357812120 409015646 9561627 859019847 928132752 551145822 777684168 273584046 105880771 681884207 555355104 877461752 451354668 6633933 492552207 127112537 477274963 482530406 287487682 259264219 386578692 747043513 757902675 468825508 486552189 792039521 755272608 863896733 947411219 170819193 498290930 171544309 670106302 57615712 122665716 563740451 705682986 21118490 340013400 325832563 53908851 279650639 907186031 639079267 396976250 215074507 116628734 293186087 258932771 405526427 671225621 732968397 160440081 164100662 103413683 601652714 833653779 66992200 77521074 839955000 647835441 904655124 575071379 952157049 574580831 574124325 160986980 969990660 392504642 762055401 781488717 186385148 877411760 620212536 474141417 896118649 422282086 429354794 176794135 923565722 478375783 852951435 193699694 670004711 193122649 55746437 529604772 568074112 21455482 773346509 257612699 334845576 90453478 736421688 552477348 531741051 522741506 647867562 717625561 986976642 911991966 728770709 714929069 170094971 510412314 902442495 900706799 479751482 627571261 421561641 552924282 181219548 669951766 619390443 174308854 744765349 308739138 433524594 110605492 402735792 808374047 428955108 884013461 327560855 93856450 546708958 13675654 906292528 928314452 98757521 239267873 373714520 298951323 847759103 944464725 994887385 259772863 3511978 158717711 667034851 545181985 728809383 402053252 684742898 123033123 346715390 931276456 947350049 479587284 609818002 415239025 317540823 297019013 987844220 874569637 235988184 465877663 337503560 808653760 317718078 864333084 339343429 560721872 823445294 433965361 831952770 802399247 412436318 348851902 996185703 242078397 344355979 603015506 273486360 172811224 291025992 402767671 805991726 690762772 256007978 626811194 508685041 622030519 983840691 455101342 149533689 964742242 289662954 227029863 337682501 388930744 270824877 703206263 747579941 155561699 314330030 413687014 705618000 46422164 800355424 630065420 807684428 883685007 330909212 166138307 996265850 204951337 827577697 424784228 153585982 891751641 893988876 424916005 576033564 528352085 468488763 557480476 605000591 488331005 125564246 430291116 571152124 704469087 231639904 1132425 660123091 225833647 805708950 154300663 360421209 255875190 352133097 481358634 160460157 148701879 573568442 337398073 255589731 315445833 749351632 772086115 604685895 69519819 488456809 288604551 389211665 526932780 397774003 32431423 603106060 166025954 279286400 824303217 903134820 992816859 90794672 410817305 98554896 210023199 558863198 592872107 39591817 908447651 615066222 795503418 756239457 566961585 532372280 199582470 467931207 316445845 950700493 992751527 366645291 943288189 851867378 337073755 2807955 125634314 747215806 550132586 629020158 529400193 627062904 468348620 592260420 371920718 703399742 970135991 462049589 19438228 411261852 631071891 213025300 229737239 209234620 885933532 434817349 374866712 735150468 375315901 323961049 793730294 819726346 543556788 76984148 68182954 855364531 965242494 185743849 740915614 332951229 663366155 936239786 685726886 605146956 569133363 264580704 50615829 248532079 192790524 688875992 53138373 763033812 118625720 181917594 623237078 534210359 809809629 355919786 690801313 987283569 832282426 677774702 525296010 520698341 746063785 752797419 117712518 491756202 983087603 589539652 923792796 943720552 354043800 598659915 165112213 714773351 596017739 85417273 502871989 910857540 607705968 90774971 133942928 407278565 565954413 413301947 78066326 898111780 904711261 310368699 357621531 605449573 782432467 735614019 50700806 202664031 915005199 732037206 957672549 428288999 944734200 781195818 505444479 97903954 489264611 44568174 428981254 625196684 193329464 428052809 943883991 118689218 349146470 878230577 507810535 193969315 975906044 800267323 525680575 653906288 761327289 925570137 375536386 315263726 589470552 157594547 555161562 174760120 667906261 811438405 208166543 182599885 708551719 146581082 965614833 272352947 965515983 877275622 674767367 1821765 908293539 339043129 652523903 223171855 714449980 170026152 892175221 546467800 784923227 647009882 525091434 473936708 320552604 173478582 355871391 980253447 288043407 797188178 678664629 583402957 841450843 858840217 997710041 331691824 288242803 640525627 404355759 837805086 941399611 264771304 108698939 341602391 893775983 558497955 394111753 412483508 177556276 819218447 781052165 14885635 267331943 598436404 555675284 399735606 150412610 615179419 928643944 267760054 444887930 930049247 675269203 575742264 82408924 161724130 317393403 92599318 801637005 779273628 860941834 368715250 993575043 738796365 106742184 338492771 750271283 4567695 330343314 958448623 133008666 116556461 514389088 945046316 934139600 195798593 732673175 158006567 411761156 892072896 431729298 664965174 145435359 663602510 996545879 124987264 956911995 938512732 821902524 382314097 848154283 236933251 545261728 239201747 845172248 955414160 570551060 831807022 998626905 118423145 314591414 151130328 512597618 269934722 542927604 885050057 778060555 516293065 392805805 572552262 50049706 997860880 248264987 584567234 25869036 251946588 597887836 176373093 37108910 219435621 138191766 276455476 443075468 742559576 447257533 115756598 581275959 379435849 84174437 657188402 623054519 667131613 797128501 151862185 342943667 842323549 628286380 695454396 693366390 127264522 223997829 813978740 565842980 401096194 322676209 521581843 912985907 523164101 144671248 648710616 660513784 546587758 140540342 985584465 889989422 48958911 14414292 21711805 590200832 621098962 266939606 901472709 433663194 863869299 111905121 864502805 315336200 476437449 714329547 919768481 325092913 926349385 637360135 312398243 210420057 286359213 820969248 240357057 601754648 226047423 117642223 934025390 767118642 453073595 140844193 783182322 893783303 974938628 74544857 109932746 375621096 575513985 479079349 136572474 164380819 952861938 588070814 77659568 655090449 953890774 627098017 974993772 308309639 910292894 112477254 750626952 778744915 436461542 787147701 251629013 838273569 646926462 96953044 289099281 315317414 653627982 534106728 966393670 568673760 278411526 364751902 320357955 1418745 741864918 823735286 457901684 211714804 676825042 289074167 925207479 634752631 791540503 147829741 435046099 276050691 730426389 840977069 689009760 958737191 481060095 208079995 695934401 104626542 599486679 625416663 141215719 804717808 72380759 500702414 88359559 130470116 86110767 995867800 16582110 712721295 319862652 440569837 422523765 274422335 19187682 389324888 326678018 636345012 21769118 448474908 924636838 139361446 325284907 360946140 942574227 127474806 283185750 812261829 333239337 927376770 387010711 228714315 217910941 439843495 478174797 901360947 170233595 537338228 382325579 588507733 226164250 621544800 996192019 593169444 136956167 923910874 645312992 159640993 682512221 410013431 28954706 612323969 279881832 552164190 332823590 911772903 151495126 152082680 78715143 977182094 990125730 637953660 332026617 940435023 482024329 126109169 170437216 515671023 564720494 414477 319667998 84649430 577120493 516226589 151309911 397128085 109699457 112235572 712258304 55585347 258176114 52045205 790424753 804222498 399575870 763619877 802011480 971964443 874588716 791673748 953754205 788639899 546801725 952602602 867447308 993242088 827656162 781388031 286354487 817843669 108961171 550452363 135659878 670862119 406077614 40585388 96507374 700244684 188716821 436091756 744868885 171229988 187901022 276310751 222674398 294605648 985547098 518180444 166341954 756148247 870830398 748947053 41154814 50169131 494095647 572501697 33565624 245527750 134498422 801079257 761568601 725293698 177759388 777788431 642682958 172352872 361254759 70891940 665851475 971477866 358772377 608762913 936781437 687147594 256228611 441949260 400654007 921722845 915104447 648442976 86238127 331265808 938172013 141049955 795202077 398085381 131739194 390969994 676382342 845638043 498061654 491880281 130400821 72745866 239958352 273214769 834208141 97705274 293811772 369133905 802715282 855478486 615526992 992443841 952743976 634904611 907094545 407079847 528517870 389781758 59589476 654200520 520234950 964080867 958412677 11180988 95455711 801817250 196845483 199762375 362411745 86033879 845832101 581580763 161208861 411285604 26092333 447218213 453809267 730026039 948945286 279984525 778988317 509241250 988031846 810703156 274926664 60206840 406813521 569231001 691243512 631579673 385917804 710085242 932667129 676400158 260606740 92064860 418077171 587847192 89315114 850696813 698463465 587757722 510300087 991116363 532395818 467255465 598068782 328953900 266183662 673401377 20444263 671529363 704972984 197345037 116355865 145800823 358010741 662250314 895271455 457019893 606341731 486799073 244566987 560462089 178686237 952996475 709860537 155691277 648832630 642271033 688826579 226294606 7801309 901383697 283626714 137976467 429295651 830726852 115288913 30013661 445881737 465065802 659748860 6567096 834008729 462949474 908689639 299030744 807433202 197370811 233173850 526571827 466012697 779464652 477826375 671445087 658018655 459273363 773943759 196580283 746045358 328537443 972475846 990406780 666256831 939822340 348306497 441066094 999103585 926060217 673726006 621514476 778094709 479385599 818683222 60209117 338109447 993508443 523534963 667832715 478536762 284764407 228105590 156974017 446753532 823800876 363733092 733817301 947854076 815207619 132474757 796914428 895631710 602359815 68292560 922740123 733154767 359591624 106658466 763993993 353922253 899554301 423633905 306685946 570162658 971556856 443037590 37232110 871255618 436226211 553218986 410819420 628634999 210938977 345417487 564318729 689092712 509970100 104820744 351895446 355335161 671204407 288906407 98980260 330989515 230626718 776751666 343352602 914576447 952387668 449737726 38507556 234790751 538363982 860252892 561025162 253159006 593360126 457749266 183291552 484180451 861586780 93856305 673440204 863415314 176868130 882430551 867130737 93395153 252257817 79576796 762285199 107932054 486954119 859503872 478235471 507497647 766903541 477366555 301806525 876604613 479392526 425250515 318780471 946609034 212277413 25104261 915644650 913763463 416383040 927263866 619592116 497359840 615705991 299572740 23033712 498152048 671186987 519046497 920642059 193185603 409865470 508367229 553039094 910532342 285086383 374227204 131625978 977377093 85463449 451628904 823818096 927919247 97742759 847796189 280721123 884897604 992279705 760508710 851396925 287040963 943496338 531807943 972739758 371326273 477233929 448892403 442764832 37645296 546456666 19288756 180446426 515640455 171595225 711229258 5421656 433821401 460725760 755241643 768587555 665058459 993054898 789992838 425086024 551565091 326811255 904611614 152006294 480646151 144712620 80223873 786443736 155629740 892589934 767171753 810904444 824418438 644657819 446059761 896864825 146902059 259507386 246676150 10056175 983811231 610033093 190407432 310262084 902680053 788281480 524908974 25202265 26071126 365084150 798816871 747460786 588926879 759087267 23964323 630035486 623375006 837099087 981221248 573716513 40033807 802577758 953071578 967757788 417899238 395874715 731170630 338562543 596824598 763904343 95503203 499927758 842969591 391420654 950398996 913988071 651253262 57563356 916357553 466404391 638268756 875368408 148562883 140013206 248764314 332835859 439853442 632622229 445370110 707141048 232096463 797484686 286309927 794532755 554626908 46990614 770426943 977648884 752617320 535915538 847707703 840631872 785318854 368838371 266480134 819437837 346153869 68624249 25141217 820995144 354301263 547712771 61207603 877964693 879770786 136750125 924000798 380379937 701209091 178623517 778659549 326224534 390393371 479108499 517195502 33611241 83907681 451477526 494403576 789304999 360536934 518137654 86254458 941972854 778913357 62685268 65960918 547995557 245459642 356749857 370487979 632989636 105406109 122701396 467906679 55136089 674787884 189363927 974301891 363905039 848469847 245788578 243605858 400240055 404868131 289998450 433036390 857019529 990660497 266165393 399472133 826115059 347687910 63133786 495790273 805726701 590797500 788580225 239999349 549650480 23505070 466174042 318094078 565037661 711722372 226943254 893599779 598607566 486774085 727268947 853035129 945673575 797162658 557022908 10485594 454610149 678866524 928040758 36518303 903278544 883658341 492283470 652701700 75249733 532885818 363598978 227056535 648898470 212632687 498424216 352000704 759297623 213088445 947402948 440472365 296387057 353614884 656803450 251056580 773985448 275800077 391872256 500599401 771819256 678311551 111309513 235398690 334498418 571290831 147419915 229211666 362146720 217036883 723746839 219786392 359983205 374907873 323015369 412202557 147070633 961715797 96184038 659340061 983184782 704175584 359442655 440025713 184628672 115325558 854164832 366020103 117738175 954108184 667585700 845955213 906852740 954913665 738653118 50995626 279836977 501851530 154339038 412115010 54480994 418525880 451127936 642337070 18633082 416371104 590125236 733254875 174488814 400861374 989799048 870903522 884706089 417126363 532519723 942333682 975649508 753520761 875670993 71760147 306441698 461422048 146975611 977018310 433364728 542301716 133406850 416363702 28954737 210778372 877133600 83866699 245157194 505571719 951714234 98437128 700737417 566955179 843777264 532132964 89173625 917073846 458768532 544489771 413052410 567336165 539981043 740444820 778176028 429985995 996379896 971785761 303699138 212114833 184733947 670739975 233817547 2033605 764147902 66313207 114989243 435257392 795168345 677263389 975667378 828559578 139693425 500538617 596065066 316287495 870301985 921829202 243532305 156257289 309078669 255796265 401607171 883018074 522510986 883595421 447999875 895847423 393036305 92406271 335492899 128277818 688253531 82589566 575219595 35372607 287425226 608521807 433365631 996153587 622524193 185306066 425220307 700882023 910836424 865693555 770849410 144200530 53230117 774977918 24281334 957015256 516420673 773313147 939198813 565992279 382066079 107615857 265607259 442952392 672491209 687329616 150669916 413787566 887472271 338182954 409990303 578669335 519405391 509479992 196195780 942635056 35258375 103123078 57400322 747489945 57892779 740733748 820276267 26118861 933121199 905347621 956189579 21625316 824078967 150267256 367904329 81661671 724035165 496660594 630346262 935106181 319927628 131366700 264600745 251155739 741268079 21271680 430484924 499882980 751088152 904655356 882279235 927665461 914588771 759510021 789437274 519407618 657530454 99563302 831692550 903454222 310557030 459092435 898387987 330607171 574069071 46714721 4929814 471497810 20262773 520798218 616236827 469132522 457303191 428496259 937321375 223957242 893335055 830173556 722017610 431074523 481762251 409735457 584209003 661448409 70973135 481132660 956960074 850263106 44216481 883366007 494945877 141623527 844519507 960403222 520701547 38269888 984961514 514301566 606643254 447723786 195728233 383809601 412278619 288217147 141574679 615959515 262695717 226180671 404726815 615449460 885810220 157176933 274721092 796795975 101966852 494011604 119801954 871214796 811799023 392128580 408219189 462543202 630933139 357886108 658182106 521225950 114695391 150765289 828504156 74563334 672675956 467374300 526872618 58360199 60297710 465395361 228743878 396397060 927784073 930646397 611050349 170144952 130954594 558655716 610718126 636063857 270483337 642628870 82117257 567495001 859969047 558501004 614264918 928217337 120020218 585725617 769075290 156659532 493004608 524592420 416659517 943599596 42463746 844081598 383451161 567774563 273209906 856857855 50755602 458543577 37502449 812352518 544770024 184449888 616963747 56139577 155661834 633791193 75027007 382516529 730710916 421707283 779439412 192966843 456512055 963172834 336289839 1994252 358750157 318281142 838965263 822631566 690965666 402354918 299419922 525355754 186272439 485310504 624766926 311253817 501596755 237967029 304537424 672677529 539735047 813739084 462385467 464542293 99812912 601115663 673444700 764925019 626862919 789564634 839881627 467223959 972352313 287936434 391482436 942858954 584762611 607715499 310598733 160403363 527519144 133148100 420874379 506398329 672974136 135498943 949779008 994177178 543931845 768550148 288481276 19673732 855468773 911249583 363279662 506313664 526709560 779458748 170744510 505715527 161277563 598812173 158484202 375025139 471855669 914236786 225785244 208252966 60936474 167092292 1842333 974830217 442419160 493269476 988043786 920001133 463315417 917533661 840496722 170624865 26503161 369159872 559066348 680708171 262852962 176215582 287959078 700563713 602226674 804429273 138282143 613768704 781359270 855586297 134266258 277574098 394934507 750853336 44396186 83845732 10470396 987488323 10015344 44779196 739598083 583762863 668067859 93424398 868836433 447910598 451069181 192389494 98621058 236291280 35047163 535697637 543460677 295562619 289469522 185319285 713157158 633818743 736633606 915483389 323304749 301891555 890580261 251194308 706836184 63986624 183474964 537551925 747295585 818328812 936846289 474494187 476200976 174580033 635503045 989880138 542518845 30891187 330604816 855087263 967508242 384819524 270663260 358924708 566951579 431385539 387091018 716891735 372623932 586810706 423796887 951487601 487449532 751905471 475896466 433422102 364545900 520727138 955605768 619677240 265980370 720698100 454648989 838097481 931243886 430363984 55325870 201875333 687577513 343586656 986119279 509704708 102779815 757652597 63184062 295311520 453719624 193726682 817524178 536862540 422063824 13338142 24371697 711872219 252608672 721825153 239514907 54082809 585632712 491019452 454868073 669491811 182645860 892504951 541189257 844362704 220057371 210426683 781910390 646724701 243387563 248529950 593632087 447260461 609655212 94208155 802222673 839286861 209561579 964612096 375262016 747722904 881699166 483093921 914214445 285617953 347343566 140577661 809938059 978612606 497392008 332815149 996121234 696631645 921471072 393308570 180553190 254076671 559516407 68800006 838273794 391975771 519445530 236586951 268900767 548678599 181135314 659142526 197850035 230996679 306871722 920632646 132718714 181112089 608834842 349867780 480701040 40391241 864566002 679468402 396582255 300267029 992266148 330079528 434986819 859873432 114100831 18968704 698429187 616387116 957601666 327648263 162671611 812978233 778829602 658018905 961706258 820611949 552005064 546943850 802436111 607968973 903791924 705993351 56018505 782530223 672777464 575861920 213864322 862175928 282124090 419868573 182526150 795868198 371300379 394199291 392772617 317013059 920892785 707014659 750658459 141974761 117266480 43475904 937894326 217386510 175500408 14846256 577473385 964394730 432550229 46960297 796800953 797147086 955319271 745373446 857926125 426325663 487060841 460312501 528372078 661160768 944836452 751363416 626540262 736474297 965663775 418087284 503305893 422301257 590021055 763718884 994465912 163096147 597967726 701698628 9671005 589270269 619264081 182087621 3855361 648372649 155904013 481788470 620313570 121366539 208138524 337530363 580482798 853827662 846712413 741327659 492093507 222432922 948134989 750871795 973387978 316962419 490631060 363127254 407760176 9007431 215536082 200273076 495209702 181278047 993998064 458087740 374863226 353942456 251589632 378845419 262573986 934337036 3684815 98004895 414985544 972072862 35231263 523457508 994798488 72693963 459042007 564071084 81216777 414005298 397348029 597263738 185744131 482533271 885052317 581278066 833131077 333134493 777065067 757644613 208413952 438373409 512974597 383284558 518659573 933161172 298647990 975234045 511844901 4913070 651973206 492346467 714254973 947833192 469944586 31444059 434066926 886869373 736369008 884842524 425114341 119846781 400061319 372060227 720395412 937525438 812507153 411719909 825238624 60861423 164668889 219443839 934567084 147832983 556749398 969591641 338740521 559544614 909313731 720215561 172669208 232358827 198649927 532882876 260955760 227882910 364266783 890089607 858555661 678272241 951198344 442453071 221978373 339696606 272388845 440722275 772861930 48333683 712934152 3626998 230919105 512443125 232796156 465983406 315632708 301731129 606939811 543896475 269840414 86411577 994483427 256345105 288730892 205030848 551303738 369651228 176818768 781489082 196866844 351525886 373693980 958482896 867130011 497204363 961790300 566364529 855045622 181184479 390085420 348181503 57649291 963845052 766324372 179644192 243755403 651594873 860952488 46778047 878211042 882124934 270723706 832962452 113412204 488451132 440853133 615550507 50069944 256561630 795198379 983375656 578575076 175969714 330946215 21431051 538898444 414591101 396625413 910413804 640523622 908355422 362464527 464960817 641525675 597083004 26532288 779997522 216703269 153021806 441338955 150547281 253412903 950328281 83138287 29485430 321184139 846314537 887075927 547660336 806777292 64788700 419959891 626145083 531127256 958522424 502991703 967072554 939118417 717671455 945124951 211859707 630736726 719132836 26573976 201245724 674871090 478296846 164984305 233753240 120887739 555078837 438298148 441158291 519734773 847392328 248723807 372277683 24909963 531923708 238678006 373994667 820465274 394008662 120977403 310744003 771779844 202322252 709748319 799424921 11552548 785673184 86223505 202783601 933069568 31421812 43244106 988765388 266294690 17670911 71422843 718471290 470550442 376936834 375753314 857485817 742720236 763826205 925601794 780844582 132322465 624246761 912740331 679295747 185707624 727334190 120057867 904108819 393207065 478863037 206623907 227275114 533922705 743992550 452395616 445215090 188474919 509882656 537675707 976817289 78432053 146313053 674400934 171873999 987293405 316323246 601334231 217091382 377012389 757007620 54672937 389381343 661167233 314724750 589905880 580125680 364275551 611950864 299292884 232434667 275626351 292846227 976082706 169875167 122023273 148003961 421388971 107623108 991921007 941017858 997469885 272283536 788817265 935038230 616653510 189122999 457122604 2500610 343618320 948599601 764207198 737151559 525917991 955572295 757364980 419259610 476498010 186744021 565360387 309049124 684320589 458118621 130272698 98820868 816640931 562939070 697783421 243692802 414244648 839420525 907457248 432366665 796880761 116499664 62635366 382527467 606403355 329839384 424870712 393879289 870156400 629320199 529801055 621005063 947700245 163629866 873074053 42999053 595682969 100604773 975102293 61614754 749783719 975094650 854443094 514054697 438058857 152125125 986292350 414421414 30092169 258139816 312979920 887964131 405796509 290237455 127200305 710625298 901326768 3276468 755899664 194495448 708063627 825406050 345507067 698794468 584313005 832868072 576487586 777505050 570174119 615226700 294086923 355555605 561840322 448189971 308613397 468489923 82112384 736920518 572587486 342051288 547568814 776838946 12702716 517835401 397617906 811472292 95052064 574256335 895318257 116262245 471007146 675061105 903845855 885579984 956857657 548517795 183887020 536255267 708684503 36834447 47079825 383347337 983203393 901189355 295147221 488269725 874020801 546566526 608081930 179294462 715813414 762011619 659182042 794642534 842694888 19063628 489819481 90251860 534122752 592412406 728815508 896064546 272846816 233133157 574463486 739457353 133025480 697455785 266368545 751308952 557080031 769076009 170726542 373762165 532036803 93791703 757005291 47307026 417359593 234828756 780412934 306164533 135946071 141794660 979007003 432147080 741588154 213190476 68234616 717282366 403370316 342959418 587855574 106666712 861805268 669072428 683943612 569709048 947464290 755839914 472632794 501054834 50339328 707733775 305411444 124857898 773954346 103754957 918354061 676063051 997988559 771073507 531600179 249693375 518215585 405159651 534775381 372564204 343229560 332381410 924096833 494177501 919232155 857304177 875683285 519019974 399380838 741016000 771505462 548559506 231898515 854545829 878364801 816665889 909774299 128583812 976159557 28522414 557423353 876047740 206916164 527030191 825116509 525804129 116166078 896943280 194886080 284042771 805526704 142927527 855198724 918520026 59387003 28486612 708068123 358714535 901854721 378462099 385426104 952404492 774529980 330621439 703387326 917489072 272059894 294661512 567024535 638659623 752078884 840547238 87093703 524282422 982431501 940804579 439268598 556364120 932805766 914020527 795002342 132751597 785979975 509779442 555800392 376037889 723398564 322451400 87481327 708118710 802644329 416843433 421106524 641861930 100170030 891415551 456763282 771242459 182294560 44908974 642142774 505530082 158327818 460588763 924959517 371807318 897737689 158152542 714628329 91775868 907601955 413750131 886248939 31208157 779072868 917923471 48632842 553807173 150403060 327926884 995548094 460863379 333143545 137101154 158075639 591598176 228586294 322304954 306605207 980531911 813023980 698885212 91630373 385281448 272608407 932321473 154259992 959186077 927371860 14633838 500619873 424015583 734098060 441093128 862391644 466527299 903363432 606464717 318436643 219527689 53817154 413377341 665243432 323683698 146121469 532975237 586461536 127168076 590881563 356058521 253954450 362313663 858665767 337719240 918537832 306407002 496479644 787562764 814947016 722513649 630885101 931495387 78744973 225450152 324828200 722761857 299061122 515552825 816845485 928203836 416245319 197034764 870869049 693204639 818077005 936903830 414715908 518260391 940236050 595040117 207387769 830403494 422934213 846555513 330110856 947854591 208296995 720298054 368548805 485161026 160518169 777332452 40762234 510375478 376481838 85759856 615368630 518050566 236948110 301297950 538848738 240642433 930084411 193715697 688143480 680890621 916076556 726804453 969930478 594173680 240078255 377091384 555193977 384756902 494294568 888119676 482622075 412322066 436717988 574545072 57211468 273207861 87280693 71060238 207794709 584564835 283096489 63358366 276458984 950252864 932613472 446185203 49037093 889045943 76071020 23722309 918797405 346826294 136687909 407172925 996898619 431167188 537480483 774003191 993709290 328803225 687331665 146989046 296262858 290250550 144749892 900276844 419469970 499002369 893778665 438532756 185253877 16769047 487489432 174256565 606680752 51519006 867557581 334161273 227317745 590850018 749495935 969975515 863412065 726087407 765675331 207781859 389736540 32705429 127530808 254088468 918445116 277430446 327694979 647203412 269664399 626977453 600640464 463092202 57188299 199787534 232663901 851618742 295403066 688348407 348176619 877659631 104191047 277383213 205046351 688745532 64547435 415299701 822004954 710935024 541780241 61022671 416042463 967771169 101102495 636142527 679255521 142492353 649868541 945280991 61694487 992772053 535683807 216943328 947090189 541400757 403316521 527412691 127977251 841557151 256181654 996657838 270144072 320112740 57887268 1506078 630932994 116385091 324161953 916190921 915244356 97361725 616846393 460294520 703043719 357604544 672193593 651334710 465186274 807485232 759533554 319762470 900905266 646714793 509325030 154130094 819991617 222122004 6079298 913317903 379815844 465850414 704171627 88144131 264876520 53278443 331698322 891224514 627360112 921117431 109281510 774303339 571315016 632415021 136746841 896290129 944295050 321363985 362099076 445408330 307434683 453371765 640663504 855695712 53713737 385750479 762877378 453776047 856189062 144885890 418848545 326691270 450655738 542905607 387314230 880488526 234625764 771229904 420540741 759483241 795404405 334302718 153531227 371616445 163432883 549357060 10033982 131804228 568840435 775781773 774680492 169834053 363007498 151272588 309862515 66045644 368925848 613637643 859346076 103399277 353078769 419944985 669834737 904627843 300826886 519237342 608367770 822733647 446164371 556981390 25439997 883878586 385225091 238414530 236582678 142917659 402589169 147969129 363741954 89727430 117583815 745840909 985219167 894823320 70163480 907308253 291330681 351078893 696470428 605385242 489128885 393638486 350009546 926882229 473586716 855094986 819365980 927734940 81423383 224685553 585549328 298737299 527057841 248701212 762373617 791156579 39170420 848516360 66774807 832169190 648080421 288858017 531363639 125774806 516854001 503161762 684411914 379048604 759471060 211772115 236158924 138896700 322233719 675176267 752680646 851663699 781088935 989104217 206995114 780982124 649052582 183470860 347726047 682820389 661078074 420679360 742962199 71275463 665298932 802959318 917179997 180080503 993948513 464548169 253365812 944899133 785424337 651892438 772500981 586537346 409976604 341143634 367556735 97217572 77273845 729263629 765727328 54833079 456225443 327941832 67316798 587063484 707007303 332691219 823714007 567096204 272942177 420134374 114153672 708111764 768303947 705879241 754565817 193445368 715471001 673655817 150991846 830186987 603786477 752089858 470419291 589907355 685139961 504995773 373951438 325128706 839944470 184984140 823079418 572748651 624569104 271171095 761751763 861023392 18363276 17746226 651723590 19880359 479757545 889430456 74079666 762497640 835257189 351144941 664553337 544857079 22722159 710485664 95911717 666126062 272912043 416920738 618473045 320801488 817065615 227538852 860702704 830489175 395169403 373448323 273970402 607656194 688752769 865598955 896000856 946813908 501016914 924307092 334162246 329110301 320628350 679421706 259521512 495685963 938157267 888447136 259331444 499217969 216098879 253238159 737432582 914057407 93420167 560976180 374720978 118660084 543835924 64535168 409032313 92764434 651183803 653838053 787765788 749305085 370655468 775771455 86667025 237462869 424125670 228730329 229102991 30040815 942554614 28154685 110400870 135564290 276951130 251868123 509152416 817302042 743012164 664299736 688967407 118714589 178549212 840073538 238576675 737479968 112313804 456188666 781244932 667602495 134415220 196494490 441467142 345729193 498246908 69805348 476539974 118558123 301971315 363558563 352105713 45248046 118540245 610424172 368884466 182894636 357957971 30199693 344367297 857858287 629419555 142093375 565660120 753388818 456299484 936393976 728230201 681505717 457448492 765739934 2218688 662871129 410032362 375281787 488255747 366717063 319778706 403877785 187532153 269694684 798171355 550598591 592031542 415678301 583071164 262220929 410469073 192524237 199059996 223077299 666970411 83727205 682138703 290678914 70780564 440786232 528451674 48591772 323727453 169386150 591563008 895305075 132802088 329169369 539729223 452788124 824109602 476992743 432464725 353351677 456720382 408449255 839567379 363222057 983080309 902627318 889281791 458372400 418679659 867238581 965415604 555997284 385092763 994938177 920237598 873574073 586621834 911081807 429185005 93690003 115658373 766663945 958717183 276079549 817733280 221711941 316497337 90040531 769847298 712132310 298944890 414254137 377776147 125003273 392236538 344295442 216753649 110701373 131074610 667655335 49302135 332426196 736868481 890933336 926686111 510211438 954619367 504166290 47568957 126198432 247104381 475583215 64162717 243933841 331224683 944250812 577165126 788373697 630793990 262309127 512024018 68351205 134732871 846425109 401162185 702497648 490335241 954150202 927115886 792776245 687179329 427450255 130750216 321030712 182314721 250898484 637116674 966492217 852701522 358994941 957177470 916763770 423265149 349350650 614676888 383981634 115672999 659929122 533581687 490276968 488307496 273629821 865726449 852871980 55980870 424604973 104721519 7011841 485953971 628114468 543168369 645630272 877750444 991374974 939382087 498066996 765104422 319049266 387461641 880187874 330886260 661645715 736083520 773078953 202538374 439173272 88316918 50958220 570166220 391242232 963976070 233658180 828743961 457142797 70406985 589501442 156346256 72611346 714449709 488400714 312631198 776237936 16623243 26485749 482822572 264208863 806319446 770379874 62871806 942943489 298703844 101770688 525678677 207837665 336462946 148401358 21602123 271601926 339638197 624605983 60575676 391330683 17515620 558967715 955717143 641494411 567590990 337365349 32761540 179199980 545788627 781358937 527807961 903885621 743717164 19270580 398678064 519259781 303203641 66512940 526225786 304944311 955241998 816916493 969680351 93881765 772670698 758302988 775615329 660480216 542103881 22208628 638311062 321443303 279947429 75809169 53162149 550702830 89621260 420073391 655385933 53029975 946709915 483251586 318330367 810481745 402810046 206922039 653001647 536925588 824439778 826444097 794926815 967854443 780585532 500370571 626238963 784962794 543761 563348465 864573070 200911820 465427072 922938924 329924085 136225403 30129243 128101344 9078020 35597946 558828072 31933260 169559304 788672175 364026232 491516665 63818438 122780783 185545927 995952136 948456886 553904026 443871524 382284630 113073045 142293417 307513353 33806659 591731503 863433048 854288827 596657586 998943094 232669711 645581445 405346127 965689473 212270969 44284064 148135623 668343464 142575488 894182512 945501312 5963591 876332216 839960791 17920319 119136899 586962471 242650651 855723379 120753438 83895703 35933041 570338340 479402123 795615620 327828143 600348151 967920226 58430523 214422479 346536750 521849846 919994008 666766471 256074958 210549939 447894366 511961923 34003333 331741298 936130338 709920991 660537344 822829527 505882133 158988667 84593279 29413401 674270469 605707228 273769542 593005993 75208018 153638787 559926071 988635424 886343111 811678085 261989191 821790790 899880064 896920589 983794806 797129257 660046025 595997642 179190509 259290419 741911989 853723550 521286282 549069631 420211138 675791016 897375796 496071687 314554183 302187135 327585942 863746716 852394413 969912879 605881416 882773206 970940175 283288975 517629732 810471669 938329619 882569072 230850100 676711813 830943590 551900165 428076717 647121542 234595950 920892445 871951550 969481120 14285656 638345690 869107789 716157019 297058467 481766717 857493002 294227759 697931474 808950326 112193752 284741598 695723024 325498389 976651834 249186711 113187033 960452898 76963299 840816415 446724716 830518223 502355603 496144378 673404347 379586503 868301874 958757367 226146449 945845915 466994998 877820837 35403781 944743976 256498696 368955294 184057044 240051375 777055317 492896705 162904458 501166971 452933786 250362932 97059985 873363551 425966873 364112079 933877349 173836580 827534592 534403199 22757735 233694271 697149085 811757165 417801143 592480536 848326725 564136111 962433918 748532489 743810141 567268141 828305180 471993198 124285911 46976362 252551661 68126689 241441518 104439815 689525018 431551539 982636851 612741240 523618014 343890042 211380778 966241711 847750421 646461858 313966117 824737935 457959009 457160507 737457461 419983565 467655754 718151356 155702026 746661618 946090819 611647469 202610053 554228402 993253784 611512865 406704780 259969135 196786166 107197483 888530569 14060626 431118676 239203366 660492905 217544823 810403889 514543644 388675093 596777323 327318352 356065832 334400813 243158412 849336766 725626382 265272095 406848705 710755699 197184133 523745674 372221941 446471173 58096065 363155118 910389147 959176023 919276531 179217340 440783685 828364692 343983763 839730444 78736919 388765422 656617548 718196587 43292815 549782656 229153718 596623366 89495904 35017140 619502808 237055302 540279207 845709951 236593174 902594094 257735788 22592636 645241613 750038902 768695681 45248576 418800405 228888466 65044987 266517358 523953670 128904417 169467160 970654534 401856816 204528751 123037606 614824613 3186648 861579583 546444456 274582766 363936156 627695387 974469712 712287551 377201838 154960818 610841959 194779509 667358099 598548557 817621488 204287670 815945840 174280832 343563151 812440979 5662481 901743345 804079859 475029559 149442648 78890020 3889954 359065070 626882564 541660970 512501778 659102383 320795165 265282447 446582078 427041333 644752477 252890401 802216974 411056757 628193780 577075058 349840228 191130028 681282867 191047440 179536358 938243682 116461316 274426681 128789039 283286992 35655323 973879844 61642547 548187610 985444278 57859334 425183403 214440247 841868932 289065292 244248098 903393728 438388567 446406632 614418283 465624345 917484955 648700277 160845622 529772999 329372440 571323305 117068353 394962508 834216441 490599149 580198319 79138580 409121705 225189401 48125726 855449561 440439540 418941224 346615828 679764218 979898097 361598916 389459182 25250835 669254638 995096002 761640294 34827941 654174217 556771020 220937297 951111488 45228755 900500668 150073219 687295355 761670652 217054895 228992102 205074562 683757930 878367650 841382405 112108961 371120349 107014712 48409861 948717057 4117826 728535432 899654303 619781179 900527575 831591949 25334137 61001406 987338231 879559779 312835423 436014705 504946707 760494426 80795974 583031770 67641514 659510905 245490462 380810348 420904127 520127214 99045316 768926415 791904570 330605452 871974418 188173275 304628840 343413094 871627961 545502257 496490374 223946803 675738819 86144204 431168158 950811969 905722425 517060162 19506086 10321340 854386404 244872127 334691611 56360448 659476530 255276128 620082659 235742315 468435984 764032799 88025985 966658095 715111868 823687458 954679391 13359358 244235937 204320158 490551619 767614117 247428956 98857597 474774187 913096168 915718353 473313374 701812109 668909740 928228323 365822436 538501052 891806837 828180090 67410148 321184588 737417582 480362664 759269043 653792741 740785308 941945352 711087444 815915783 670064169 736652035 775316758 512606819 883882952 840956319 603684231 288646545 638111724 572821789 526842976 500029000 128371655 215822627 32708435 279549300 731039479 103111921 15729838 856551178 125637232 22491474 725507108 257278189 99700937 652239656 926711491 918663172 881313337 353988602 466928075 61663561 819982537 280842896 412511639 177149555 927168894 834521151 631448704 746008807 249006810 370987145 397440459 781520191 562711421 56570273 245534404 296687524 306569565 934943300 832704022 415443307 797732563 429839479 238402705 666100537 122220480 492244259 689990752 973750359 373623008 601337975 269310881 295669962 642936712 896791875 85178820 967802861 698951907 287427548 8343658 200630539 287547618 641773963 601234880 953961319 867302889 78294563 109568341 823672181 303451571 977828875 265143652 903094820 735183483 757683632 142464016 965532364 149217862 501196825 652636902 704042807 88108050 955675933 131479718 886335849 565281602 353496664 100869792 943710611 943939935 868240942 434781894 34564260 671225377 525712984 650794523 816015958 394366143 98550340 370741069 352735349 92415095 613583054 573318420 857773194 456528065 509423973 313702622 622779107 674568690 236566123 978746566 186419328 635061756 705947650 962933609 139039842 259929655 447360407 763039425 846070579 679459367 702259809 609866349 103151561 816782640 552774244 199952649 155395195 619884926 51170811 873142532 65015312 582625116 749143252 933648317 572239075 716586106 968795596 745454377 728037887 162578874 526087795 652959541 979917117 578952963 294519967 234186725 597732053 494799069 410352459 887844198 473604074 849380957 905007333 239593793 543076837 428322366 917498557 309504761 694924855 416796733 715431234 258462826 152891869 262275369 200792597 340711379 557891525 906548989 967561570 581001545 670519694 885051937 277294294 958039616 340508820 326569321 463874086 414460644 798083657 113677188 156863165 178719157 480930795 586919787 430292758 381668155 78344615 984478478 935592644 207641199 357913974 768328220 403482680 544948363 624589638 365704499 923542139 682530698 453595502 152525199 437416195 123578798 871221710 372733597 894205628 713438594 943616027 235066224 997418560 74621689 865799210 416745984 430504302 611651717 929761478 748030240 283188446 96792544 71300035 687290221 807568784 994708117 879570793 826055897 685729083 351286332 183031682 399743709 65947181 810809746 37395533 348645611 837674534 371792936 579849615 252260599 12262308 34912357 318700292 300709839 452753418 327885902 853324744 858734231 56487183 266179958 427119961 448711719 138821969 546163538 77822593 695175867 762613709 462561107 297450295 465817279 760198118 882009101 775063209 234963462 370899510 61888102 109190893 123005655 147792153 191502430 85418024 790712711 727720777 460306099 743058438 17212968 287089253 466263776 798799698 635619850 484718773 679238563 713478290 822606404 390481668 876639921 786014379 968943941 26822360 345319000 706583883 690979961 430297281 792779552 190989583 366691252 533050353 865937571 519383686 359964548 284423879 525188519 488287322 80631687 591343447 874676191 355260919 110041795 795331854 787200531 84450361 142740688 608745971 755492259 768381239 728330764 121811935 818786294 397711534 256805582 513323938 819010791 138017187 672702714 216970551 629372602 895490700 587387089 813597128 205402503 828650078 308425779 767983591 731702578 522455712 458130161 173259717 983829883 402266276 313694583 393628737 909617401 351532188 757256508 485099155 810709183 682667169 873132334 740309768 612516783 850658814 60881769 176077577 232908782 762086291 119048275 254688244 69153548 84983436 100399389 500024135 525116919 484836794 112504559 265673372 744937038 762918760 921585395 402500028 444772397 9235490 601125416 384568143 628167801 94194647 43932046 830138576 53415602 305047250 91741004 666140988 573155072 860609297 873238607 76275611 390893803 903606519 207835390 846585059 960180804 532370767 992841746 971293146 19873581 870470292 310002649 977136921 691383312 609058263 132274597 695291070 833201880 293139030 822703905 173201821 321705529 120429996 422649292 428996598 893544244 347163736 900491551 979688914 6488100 177353464 488061089 381584345 829200277 424750234 906658844 556209305 584536565 883508286 680233236 300521557 559084555 194524577 714195251 340108258 145217946 967416029 918811759 507501188 903657218 496316193 693394116 803782477 685291618 257639579 148870078 874102145 449130469 608642771 914020286 271182582 550135033 813292641 314779287 671854124 564961535 337655428 356280077 816175731 92270697 870502870 8578673 489635656 23697377 534739139 285310323 59377225 63538161 71950424 593671852 402207769 89219890 285560002 697077325 577521697 364316478 502846562 162279556 827301835 824363192 298067872 934734757 953094529 365061137 472265150 322635594 987590297 166528256 116421972 975142658 895975097 35965041 900748678 698324705 764403686 496643441 73636389 758806740 937818626 912422828 820359531 134713520 311106926 633310889 163991234 614683845 451848343 526765945 336730171 777332056 135463180 760381126 494654343 601803859 121407893 749536205 982218499 736371893 266088186 883281442 94648009 495972102 994936084 171935004 595652682 23873315 62009744 660669841 369958618 812203392 171536889 252684588 736285088 836806977 749262168 380848625 576155017 337063148 228587312 168402649 749255617 816870713 659459988 181781223 927689167 625723659 602146019 177054300 490942973 366021001 713489514 370384422 122368866 781403250 284494580 547816172 626954214 81197901 669841562 857606131 549091396 562370834 493420717 818857689 940045029 330727097 427194291 562274524 598315013 90949234 731881064 902398359 456167517 987299543 903607952 108917545 340415456 666888879 238966848 853293140 134902050 690721257 85975528 102083212 535637821 121685934 298601012 953373037 487451399 860753871 991985437 224391585 664696578 468237044 21034006 139411202 167262862 815857793 584585006 762839493 620751485 20986915 132647265 713518610 437724249 237831982 727443276 797898006 843479858 210662232 533885124 294123384 603460537 798564222 898837257 564050657 545812276 658108437 340495384 814257020 952621831 567496112 542910433 846899334 380094916 886993308 963807444 599355384 150062021 253832852 463546199 116257248 191504441 898081094 842281092 637912444 682615854 655726284 835539730 502020754 267646438 235105607 481433753 426838961 92411633 111243061 999013516 485809078 595697255 661629727 692142612 711643517 410049955 606131004 716953519 585261240 983637137 475319902 352314188 70774641 353932375 994508638 847829531 945288900 143170074 860754928 674786098 584414210 146906410 325123024 299102443 20923372 38478 680397958 758949846 241623908 390337567 580462332 854884177 594190627 479997046 451709265 396448041 719567796 741865982 568199296 705196352 866721997 668426243 615705007 944845080 740784557 725853937 4385869 843506958 552741000 276666374 435880493 440747970 161028762 65278236 80863027 143016085 831344968 593011856 223904148 760046076 238350342 262567163 833080771 238595785 933621946 858618743 826051566 881075142 758278323 814629670 729051824 523873915 723150997 790964370 276812670 596878000 455174178 690717520 312303196 150296835 275002574 254986638 901897068 799676756 680968158 634563501 921864850 151635080 163871732 534318550 907030953 986725515 490858466 823256457 127724001 99959659 616621919 712992243 184342698 613333701 120249020 129683540 733531927 523279681 457256606 24427559 585660123 253649216 94452108 785789039 414115415 733691466 76949945 494283585 498593533 466762180 720880010 314980678 67566074 680554752 843105101 33107266 956869079 447292933 901148381 176424226 73282339 219405702 284083800 309277174 744811603 703428500 25648893 877974642 905804869 485390290 112023943 7234845 752812858 605395342 293735185 343318128 646243923 621843169 852894149 401942498 263417102 353327052 709815471 362526546 483430185 808329879 932181536 395200304 291827876 9812280 227901061 492803797 535827427 484853270 101385569 364428391 260093651 742025908 125002618 689202544 771562311 437494725 459464165 176941263 77895581 283494314 828066314 226062790 731909445 168549492 675502467 325046059 768240339 797198600 372824406 662887929 888713420 287196518 443649616 797922857 120343899 881804892 808393381 835791292 870197403 660486998 380840205 354619449 11470697 55117370 751344003 932347481 382852719 385830831 394461057 974456126 160007739 794817027 497379985 938711176 103989635 651102786 627118233 135971690 451296261 588214609 703163297 395778486 861797895 626852202 521604000 494385635 96090653 936650870 877844423 938776185 222325940 911179648 157652173 704085870 855457053 132448842 674523 685753727 813456235 985775270 173497198 697073295 454788585 470373452 715946582 907342855 291021486 248443880 980072129 963053536 79310088 789546711 272280167 691274381 73255140 262099937 978737887 697498386 962659424 820825009 239499361 334766501 350166992 695543041 176370159 332627555 753146586 149059773 947488680 997871420 262868515 157236770 296383689 164086071 728153865 82232800 18424435 723329224 32244418 762943702 740702149 283551814 116499388 722228672 553700981 781166807 575784120 283836850 160963950 784591400 121483429 133269960 784840807 28426764 305154647 956202079 931713942 805112861 32999414 144692400 461913434 969628700 544484655 217039071 990240902 241451691 333852204 216439208 502554082 475270368 270713825 922156707 995668657 805798453 341800127 726473698 714174221 742790790 232624439 164456287 742010953 215417658 786350721 727535053 29357896 607908559 811722934 785413138 947448175 471412245 764190372 7621424 907133359 310944584 540337309 702023225 738317678 771599027 890744522 3285288 545463896 541886665 15410399 142768392 125766739 489475892 923012085 120099479 969981857 903681784 143921813 163897998 578780814 6555148 939712171 796030666 364327974 560719655 514170233 99498427 290433817 220941141 201941403 112956329 273873105 218014563 396776226 874436610 320913363 248728190 774527887 127483380 8502150 452577769 628555610 604874452 300800715 480606577 245311293 672217246 968293911 93935304 886313220 316896700 540314928 350403773 946081851 391193932 566690335 863512761 208956877 901407535 918969200 759815848 738992878 73747097 480606116 194674123 420652484 278979950 6686776 180514389 788500759 426129911 99747889 535246412 655907459 93892093 55340304 572679819 545348284 308187157 999582181 926568968 217420011 785244993 596166161 188147252 999716850 93457729 242332396 68915047 339162323 611263132 804394513 346975714 967792393 341917441 27577829 34071880 368956759 705006116 264142984 113932186 253056570 282939917 877554190 514055863 966069631 406873545 221382156 639375099 487534629 730732934 165352294 240162407 509642870 219583342 779278494 399274114 335118514 230757119 297598828 307956042 532379462 867525013 155535958 985231388 528595938 47342530 927799224 281958510 934215039 106557046 625425219 916191838 844396206 397863481 177326339 713893116 45876090 209814105 851066794 322191778 436089288 818201077 62865815 792037843 124444089 121328676 700874290 488013389 774313056 350512663 854823859 691797753 325724767 137561552 552028498 805838067 839713919 201736268 230017274 541786941 926436870 932464929 773914853 72809972 404458855 123592643 719596718 935653951 828365978 576775794 108249361 655707218 699457413 134823137 985168393 968048563 637190099 338428446 716497054 1692017 469340304 54204439 571150191 171930560 926730093 603873709 910441040 696375456 925426983 342526046 779712165 741367792 149594083 126269361 736896131 256022684 5033985 489708526 393635004 379964252 845288712 596075506 323395833 519168025 39793211 268166867 550940509 570533335 464118877 799022406 826448834 778554811 504192842 305487445 637124189 297640964 205331293 712199020 116420102 499334190 128711527 948294671 412873977 867524770 417466974 80480033 920127178 904642069 567319816 484603449 319823968 789180782 512551137 504535983 794180602 685444649 373331850 130028432 794101948 293251244 45320288 382267590 847874757 477524959 600038997 949765648 2803262 456401831 76203020 538832908 886766462 739667089 739380407 731005159 182756663 234104088 950589054 798568189 406435852 421986249 317973788 234238609 268165908 599049151 19535257 284159358 49445053 895466851 184014237 709801418 516766975 39316774 834468959 866537126 637768723 299625299 625452899 656590203 420168163 671969477 593950540 821570821 439628978 793843248 754954699 285384188 510246386 345483997 623413878 240727712 41809827 513354293 387940708 269095177 970781924 3073443 856291475 700674698 108250459 550560535 356772680 30340657 631067052 611490369 220448901 824649445 973051705 386528561 569144229 865953895 600988490 928634315 514058980 996501931 77527898 602844127 260302251 297796078 567506739 771488193 88359404 75266508 855836781 48129307 125065167 728173383 247318539 631272667 616835475 906255436 928895476 528278704 369067515 753402273 43835483 911237728 888195335 892331124 138195813 410124452 284409687 600888717 345301222 344772505 206138424 972424829 444870906 787494086 631115495 837704179 860853892 71953683 951235112 154183779 541088810 947101729 606022858 662320471 721011772 35453820 970663752 929041249 837401398 929900586 663721940 425016908 620124904 464315503 824409040 49035014 591516447 448798437 637639499 98520964 40396336 267951601 341474411 245850760 643724384 428947008 638652054 20318589 764099410 235713440 757355858 47193983 430354574 311046665 366492254 75715234 463977856 348894331 510321786 730585610 881159702 426852959 319087270 347926662 834485547 893245140 975093632 491592041 196637819 904667497 628687956 597938880 702472331 10306622 174216151 545308741 3328628 368454691 820406693 233677070 687441135 364279195 695711527 73844738 358367657 765797250 436999358 444369540 13134543 563292070 668590198 914840325 809992947 844387574 656903812 780817655 362992023 174836582 901723857 78921732 488464236 908389832 90121815 954933575 243299579 435329970 490755445 781202439 29175588 201729420 784155064 68020963 654795327 607726044 546186742 920460908 629342119 470239130 981120992 990565274 211679464 980167901 556864049 23077862 992518036 490538600 227492906 299784929 600324182 538265674 613549360 857210894 844461867 399527081 743157236 595220502 208345634 12905372 431799717 62948724 166310029 14801813 610104062 380245093 825183073 508656123 835356945 342687805 714802102 601236811 640278852 146453824 145264538 588580224 268690715 262333944 603137232 383206319 942196376 976961344 463936684 407227121 603257901 670841971 14591021 238923245 534709191 709775198 245522494 240158621 962258884 306589584 531687760 129494356 566420127 551107107 716095263 346502317 303098809 751002014 656439100 601974574 247107438 364566959 783426904 403593997 792145297 498864177 670450889 39733046 947652208 923007462 575003047 732939667 221213559 2542967 490570007 507188509 567257018 55980330 196442118 179989311 680158649 421659652 749038476 446139538 683366711 111445254 763961965 616445982 447290099 200569423 132301993 620835043 16772218 752598250 598673108 993927784 171527613 966381319 547210699 619766850 653233671 544796957 424233087 396471057 544873806 380916648 147225868 516537890 715242807 817090167 228394479 239115058 511971004 87015206 947943554 463668896 972684955 650719754 124464633 746590845 451746474 321206410 735264708 512649427 212868131 799899539 948991980 880752919 215080092 450392928 141402451 492630900 921122000 278996204 184564510 21275133 950336973 406077232 922233099 573352591 415423279 203570770 503020577 782194819 658694147 539876221 427636805 764255434 568515124 579174562 730371713 415948672 557187425 280240518 502724754 813709970 690397478 158186504 685504585 583704971 15799903 215058470 307185492 11547802 532406975 713390446 707375731 706966628 128050584 962345116 615832643 650730130 154834441 525050729 488291429 639691577 869680187 996268666 966205241 609209522 132077925 976702114 817051021 242319943 279641440 882668027 667928704 755422726 320408825 23102821 971225697 223632733 89484282 872779413 674471097 742161042 777544281 596125334 566745124 98825038 560440309 92722528 935911732 325717355 318219010 89550105 832688556 550188672 619368533 557979047 857060532 500370086 117065764 93709231 473571155 837194384 38831902 806445711 231979650 757623533 460308956 60120917 954208855 708118777 371672930 547800624 558435337 504238772 136548190 707858611 195734643 692263386 101480865 552117234 825659422 131956322 435672929 588331411 41371066 608968712 757732175 393232869 692611878 181252321 138783765 33697016 363191689 288807491 453773899 171627007 740726464 47257052 436052165 486483475 224105630 775874063 363138007 285486615 573539516 742342657 618717257 512872094 633484322 988793736 534898372 859938235 572874986 184893384 154522805 443108210 803665974 212822673 246810779 759822182 631544978 33290989 200858927 64047582 462656814 771531092 446223712 481312757 960611043 386896041 68711900 978270070 508986202 307123265 71766376 356747318 283510603 362809667 213761191 354547115 716119563 698770867 524112100 665507325 226731773 629087138 261907751 443239497 723971389 797713336 670835231 373752299 865092632 283948953 419129546 565745514 947375603 422375430 18863559 36676374 944282851 979803302 253965820 252309083 419253031 395033407 990328450 735187789 925645222 629164593 141003218 281109547 695275531 312266115 365552892 806207984 146372072 200416220 579547612 113174236 530043709 960830309 882767480 269874184 376295304 836497796 39772747 330037375 558168794 79433556 96007401 731703861 995932907 992652547 440590167 215987126 416862227 460742400 576299362 733348860 288460720 813153561 135196527 976697213 177038720 960175727 140064562 420096390 981892392 603949143 422142258 567886497 925262509 923718209 938140103 658923788 655252337 135935940 66458954 206210639 812185508 930637556 147361531 443381695 672864043 757800889 672654003 668375594 564500652 697806754 172129781 764186264 864604698 808728312 789293293 422056987 186456685 70323105 650036928 762124907 971843192 719718443 363235073 364596665 898092589 164344813 490927712 975458175 208611295 59335050 985862917 865669340 325171228 804473711 937176169 763813372 799383849 365553883 370946100 963579159 835646807 953067916 806945811 487842053 169712262 911779939 677907055 272295491 962691939 698183409 442053020 61215627 765109759 387645937 971784360 212481423 310598977 537076983 681495491 635232541 736899068 251399207 129932978 45097088 509578638 99013980 781049540 680355408 502365247 748710997 645878193 977291738 689856606 830259407 623672691 6481718 935304725 841071631 432443674 195992668 382095535 650296688 905358026 615143915 911989873 931070294 704501469 281255018 832325103 134167119 249567258 15783475 572444736 858409682 830876990 765342942 443811580 57479843 504243930 435807192 430093163 878645658 393548383 258725345 940006747 658701322 538060882 31791986 206675165 583605565 588189853 458539129 731890208 305846311 126518477 329009619 211683689 497892304 10680230 60150375 985583561 789376621 205878377 863437601 109424876 523048780 92578681 959552587 693689242 998166727 765176672 230088009 456507560 304115159 188966116 5675316 981172846 609694483 804753884 513404417 65322133 26098672 386448807 68286366 914114869 975605151 200974609 921561729 986354194 282436357 390600375 558402945 881715774 109151709 109992615 489996985 243986790 208180561 254261115 375169968 605017263 857814175 107482190 945301267 357610877 763101950 974694544 191663845 326308104 856487864 436926090 578439998 375033999 598916466 279729125 702044227 600759954 193677066 834704356 701506891 540471868 576151063 325117161 905268669 982656345 880781938 594457867 278948581 265135293 911505416 62668518 108381586 145721860 246370595 953547850 416638155 756705387 156773020 52686717 145056553 414225095 196846012 212138333 803605318 933815062 108304876 728302953 420930572 957310278 23125943 46615591 782551170 799968085 222746956 789633818 810937239 572637010 588783323 980915481 27254656 799251076 667358903 269652751 645982240 671814545 802512007 989368293 23218709 241756198 891617669 967058073 717675236 614291989 373392874 326167079 142320368 243141348 542651937 71603103 109927138 995975430 418146524 255612104 243811470 276063187 297372800 621311093 499395408 146877599 268381734 417250093 485298078 256777207 998883238 64822584 965142517 26328485 908714161 9258356 503830040 978969883 452583595 602518390 278228716 379585688 966718766 928426064 800762983 345354091 164851748 897409684 912793030 428353759 167239936 311330207 508822255 791667117 674751393 751400779 36110938 322690722 463625941 339077624 978608649 581518034 241293741 528846081 308413544 440542171 326171124 543192890 605417160 893597213 676463006 734889491 197548866 757746668 493358233 42988237 333443278 503159593 166872691 351311914 5641177 195565046 61121143 109316206 751840786 254961501 348753591 783982676 690204949 626812147 755141379 95952370 292650168 804099608 497520728 45654680 812227266 805650574 763418630 871206660 292373065 665487253 1301768 309282411 73683858 441559300 831498895 784273647 765425092 945949904 76026273 241337988 528254481 643401788 350436858 527816573 218884854 480413321 694174643 444349059 512061127 502592932 467261213 80899639 138143296 790384938 68857852 863616022 625538283 334393697 610447375 697484736 960894204 374686727 927931562 16777934 441743057 457668313 222224030 359206620 90249192 779699055 976589265 728083799 53870987 433169322 654530486 869626411 103563205 651004948 642955653 147406387 191121965 943648053 359258262 572748577 790264482 72182752 44161568 897035328 970945872 901630980 757672456 422743935 370901819 928517457 157034147 508930636 102141423 452978897 426719816 550669454 551498702 903257182 449558522 213376746 679135219 749908996 359459269 873987633 692683538 560077297 322932002 766903631 940966121 296556150 380283921 621872404 517352927 727978137 607947998 959178848 58928933 633949085 858822051 640993511 18908435 422458907 820312661 21013362 131881592 602281126 40333769 952381219 364187255 367315607 673256231 66355912 969940925 367759139 287417463 802247635 12782057 10054331 6061614 935235173 947250341 713424461 357689852 917841479 241959306 910843172 131605687 976049527 777559105 277889301 110046523 961731733 706940038 247463399 194353315 704001222 953524492 825618853 418300155 535039160 932686172 751713574 876535590 629600282 494088102 843635310 787361279 650672451 496584886 190526608 553161569 289737300 45699160 585591188 517458300 176972126 573099757 450472684 347226227 140617625 20074419 876449088 820750127 543586922 150378967 797208853 315691610 73600410 282737281 457636640 364852622 530823169 589641164 480549715 139081690 154052898 975913821 415626567 189192488 506478403 241560470 896251996 938213064 239210619 795896703 550939769 128337431 428693665 657114644 282584636 40046240 349227469 898686251 318269856 986126080 133005672 318538290 386581847 987526395 134223235 29129131 606478366 742456883 260009436 176466203 660743074 54979747 945397250 940692407 535305445 770332414 496723417 632638475 757557973 605718432 69602390 734370949 450950730 651297956 43755497 430062874 53470166 334519101 682625702 807804517 576895447 632528754 766045178 896655962 633460328 103603051 644364148 595559524 961746072 429189802 139313605 342841226 231514758 539361955 482415541 368385442 772473660 743173516 430435268 576699067 921593333 880881665 596028615 757412464 471047414 678019940 274697016 789031529 237139572 657975576 416922423 427308383 125653166 889493395 881878970 187332783 670166498 348517731 6116839 444693850 94208072 716554858 356689690 508229245 19021246 412943242 589798774 104774427 354169948 689893788 576365934 707323832 316672432 936220201 805158795 992362959 700151799 802428314 767754909 948782045 526106733 48335074 269777953 201670701 42329269 103139407 501425166 653914046 67126278 943325269 937043936 636816341 484138490 644650547 574762280 381948772 66118289 724326326 918416225 200569409 504749413 515727266 188977310 529643107 591126107 322448878 886336074 162582357 451922418 381192765 726302077 72707889 928433403 552814144 389591606 650623096 893464013 358437979 381444360 961272601 877469718 280144794 814095685 977135847 324953871 791911409 719049131 587769577 508673266 505484307 656445711 768990782 964419554 473917436 48713261 456683273 74890771 372182698 134666177 199712157 787662072 620505717 767733195 236952384 300742990 434435552 172148224 11639593 433143475 554883382 50610700 495752131 648352007 279300544 63168121 374975576 607396322 104388200 983213398 913237211 215805737 142049199 983959214 235119029 596502428 551289281 233403138 43397042 88432871 271653550 612195958 748711028 265652106 916920347 410425812 774141632 296513473 161938427 274748583 986293192 368731011 425958102 509099843 390632636 411723958 58429821 720301211 766145553 211098847 931458080 62048277 859780472 392074862 21212766 272173753 781568540 580668992 600516818 988883935 310113194 727058599 158316682 924521574 617060959 390839413 594876257 730386286 227289350 74056464 417461212 860839485 190657983 706925645 138215065 592995840 586955207 245692762 422343855 81642871 761745435 193719567 38404919 463037284 380901832 729847150 73140648 658737748 650962166 685880406 314430956 13817619 94060917 924193271 209576440 123370330 667794957 314682931 407119114 500936761 519693521 646153356 452728469 117129215 825920145 298581421 829585494 185792968 599413698 729538846 941983068 421914467 880827010 609580758 775420498 980910799 412370598 386024141 11167320 967708195 360485974 347114903 173259010 706024050 415817880 176305060 225396950 824709616 148944643 732270198 374324284 710845533 829183530 632117783 982143644 35622302 613265623 797536950 542923549 569491445 959299029 235064813 588965334 957059523 649353342 294801351 301114355 400037765 681971066 268661405 490880495 171350393 76052146 86118333 295936491 803536781 184104816 501824637 391125803 380295065 720078287 605836466 453830496 689858581 644841574 157783024 227353469 349209893 181307157 86634445 41254716 361153026 922943576 901041487 893059595 434054885 777070858 941318388 549685822 579567992 887887615 543310556 304452298 435212322 372884245 395857549 825716749 213745266 542298891 377059545 802831241 69300459 920920732 700594774 264467735 943135342 435182464 278690463 685298026 276625368 456088520 647831817 696456011 249402548 543960971 409777019 408135767 379420933 177312965 748962618 863697122 106228906 352464757 615432585 603226118 988244122 933484347 733035926 951932768 417368827 270375506 505681379 717554858 36705924 798970359 51475216 719789862 320784959 360772142 371387109 979471864 892012843 898479510 455704701 96973270 605917900 766533227 235829029 602674261 962612976 596488289 921935796 434552530 903723111 548699659 243024076 646626835 285542610 614555004 916538889 151523915 232543195 708538153 190701400 231919714 826447694 813309436 297026777 971654248 476814724 423819205 945938514 398555818 469073024 544135333 631036455 755479060 840223731 455508484 204171944 479565244 569831058 877423792 682261231 61503516 864655500 639057817 73838199 450987785 66884322 567612047 749659776 288420371 292222022 968071549 797661727 933782577 534097548 735118352 294016972 730260997 671979142 883077614 587488773 648753947 476038268 76659161 364499350 577350812 671087322 104709289 732540694 778439929 483843875 30958889 121321846 187705923 361429984 826692282 791094553 515202130 987552545 572063069 822188202 171669592 710908457 395683651 96881635 535095090 818530915 984612717 254376529 270259687 567716452 403774579 447153126 182101518 709770251 278224167 406355801 182872631 682937714 742273233 777435643 11661109 648694058 666869778 116046348 32986573 862328790 214828953 371022934 362796307 692580373 789780889 155063723 573347285 440465211 428172236 684091582 912060255 19574323 547577470 130825591 346456272 329577274 827488653 742066989 554610965 853306133 160684610 203891331 942352769 243445439 315057278 437133947 198531794 249424166 13148102 239059209 953232805 272449677 812293186 930113667 974229815 217209745 229944357 367054582 624755671 775009549 894031258 107154133 974826829 361585961 810760456 104204133 836206324 194020486 59543216 310041617 926488328 444482672 166896684 600661692 134251772 80491148 748848400 209607169 925391865 886057300 57624264 487918063 730983914 45588599 484248551 265071992 972906741 259891801 891564483 630080814 223243240 402510541 112700539 627888864 853418832 232451419 245887792 109833616 417783280 806250323 142992209 113766462 882945608 971350388 162808988 935265958 152173412 909512722 148834412 285816921 543332351 831459781 198215792 661449516 100036084 15215012 38225253 639909501 496192711 847504503 578197549 440658525 421868647 946023711 836059918 482738316 403561346 817658672 41632739 945313434 736338127 988148716 396262557 170529625 879490865 604108294 801985249 60950556 684149934 169396062 136470714 260282330 631938292 895114445 310606180 532003215 529637475 54315282 369294781 826700860 418245283 43879563 89825023 613275685 323634840 563512835 172438827 379451236 455269465 948381560 277012492 895167749 88104287 689832990 896340243 773823756 487540155 877944811 683807175 602989848 486500144 11551624 924491919 789457521 444966806 731312258 545238908 967849116 990364708 650261178 456763415 692678084 275648057 206947954 130206113 239822332 903589837 975689870 760789784 195893917 190506269 552200322 16893792 901727812 349196236 636570958 910230091 408236612 685029941 78336206 163892950 840679663 927240815 178995924 777268933 52212798 693958955 272840017 88857293 469363149 226795662 628338956 467759756 432744548 671444957 713540269 26933271 938225977 699878379 28402768 959559459 881177726 910571636 833987739 614393786 271372353 531278175 946034818 39096095 756498708 860653146 787361127 375555668 822658461 925199749 4558097 812055428 188516541 781856238 885411818 661558406 400600342 857210184 434026750 422206358 635866176 582998449 54493403 628749433 597188131 200952862 949386195 21408755 243138030 854901644 777468357 950086583 143041691 367508213 795558707 243888154 875026892 951137651 489796899 554060861 423640452 191426282 613590399 333095567 372163041 310068416 763218723 352435396 254478934 805714530 836695806 213013699 820637132 414257951 194885752 953611385 255671324 833868557 656353617 127000620 669800462 430841722 178265963 774086730 64760148 363559255 87804791 41314493 250844594 473152427 550098750 92969384 183069557 887603407 902604766 226719412 919200412 289779752 268808886 930069802 454702107 819534671 624040009 895123196 887606843 316105626 754428442 479217618 493560116 575571528 824529572 637877527 10032184 663628319 747164181 289971231 805057773 282140693 730613624 968600549 496399241 205742887 10352881 565252819 853668079 717837665 507055659 743903382 66830349 594234872 203912905 332393501 216531587 782376443 308225137 25297100 176180654 497440884 669085472 27105455 184659994 875094956 313321327 797395878 377792185 405967492 375234390 131346713 272856909 700973052 486464227 861745075 620142360 980391538 863390515 755702268 420850979 314706024 351713456 113034096 559953657 38112830 173872722 198277511 702564807 426250616 977711121 755319540 387930076 390672288 436707523 780157392 937278751 472375662 438019108 985561727 478842646 219256108 508691602 58224835 209525962 609670920 501969704 772650254 516133110 562321360 996593297 829272585 436729140 715043978 186053858 248190370 231847023 555972687 43307421 323465626 286196974 595926274 400062869 554316060 947258334 584962149 177786991 490875345 790026012 321382274 89055512 64420725 447823120 859382280 649730974 8400197 504638523 265359295 385985362 888733858 148423980 417640089 321406503 66522103 436307495 26409081 617112576 863859407 614645578 161282264 482772283 105942605 878368066 884541045 830676678 782801619 588541503 430384190 237362587 968045777 684193794 977349457 249221256 27919475 456403816 920980309 451434332 33404497 650092964 586741992 564667228 602146514 350227337 320910157 561152289 298564916 880198282 336058866 969732434 974297747 403030652 832113481 975983244 390216562 542675867 161279410 156088219 229071793 769425576 221577660 647371706 690580403 39043729 301244732 233082885 785800181 692879764 875276019 121058689 240958213 640524062 883563287 324973741 144149687 70241155 435975557 212460957 681216929 545524518 827430553 886510021 493127203 66813024 991842820 247959137 628706145 15107687 309823342 502285768 689103684 793162845 764934587 707355914 749578582 29503248 849946510 519175355 549584702 223101099 167828429 473258984 590701971 651506586 64516111 452872308 161354538 142466260 523095664 688684926 841655482 956856431 847934929 314173802 19671513 319675007 517213483 634107981 568330321 518546632 277122398 712139066 788781411 203226586 544940231 533053546 713187648 51009777 822071941 582443427 311122956 899462451 966388151 835268471 176077880 465492529 515420306 804286310 277898376 392500030 762328313 457614495 328447588 907572655 799920918 677522896 304956671 288768158 729901253 416092365 139202184 128561012 940303876 460695709 920866180 570532339 772677050 348560312 241719673 935838710 662796020 962366582 624700645 159187132 510167297 119930351 684207548 627222143 461203725 682806263 831099874 846559439 34524024 397195480 144677557 215327552 795204663 44357542 480738368 822314719 750276404 350156625 505925564 789523830 736541863 910271645 275842533 44562780 263820063 477773368 618875547 350016839 149095409 387386545 1848685 267300684 490138273 42986558 753416662 905170710 577408054 348904169 838147144 118936559 838728969 821043666 591333191 758025085 254828265 349406464 355709543 435614871 372260581 59520557 90504285 260584316 439400133 81977488 364752065 730571216 656124571 297162099 397402196 983595608 878723606 58170346 855785844 372933115 419234504 480661998 665477278 126297741 486949607 748839029 273305516 654372293 95086608 104394055 870084621 808501012 583919413 619595409 357924989 165580368 419941699 540747143 632748646 475292002 701628431 940805964 391645005 508320785 619903262 169767835 378817791 439049283 846096478 307987444 716148079 739143906 441201683 861504307 293535434 805288059 89406832 815351197 438099370 985185431 85469371 260165245 3719889 759815558 685664516 260648454 867305982 729156328 151823911 86153367 772566043 331169123 40087268 856378860 310751710 676373567 507009253 413327173 985879267 259453195 56466822 927431213 228256769 873879577 608622038 961666127 151928885 449855328 387648914 554316357 438317827 254606897 626085279 34313779 181920172 298665055 647164769 786661943 856056408 528274471 713450597 751510507 478234006 413694106 425384905 954114246 943654798 995440178 786431985 191932211 279395344 504715430 247624032 291768252 791090851 98010024 557095843 858424417 546230445 550285699 875513544 96422553 785146552 645013541 723038670 960824946 943428275 341508515 453134673 345321149 743444239 75391280 520929966 616124838 761274792 543212638 646727340 529499857 611719984 556699639 462691446 548413085 14160969 934445746 69793844 782472129 242413002 356204629 793532999 195568068 147770502 674236574 783129198 603207466 387808996 445928904 499839828 529923063 16952009 927238987 251564636 55749293 680810577 216712095 381659124 649744717 724226098 184552335 53102191 510977844 89190624 540547602 182981411 520874832 659549465 882164731 186038295 535501728 151672222 410791543 510959374 836681652 19828895 449905821 902412976 972038133 464606890 271214846 948670899 433407239 345155747 142938913 299658863 379368819 797944406 825133632 601920484 602552447 742157068 52426465 841792304 388670767 525041064 976456101 658311174 481993485 87780540 329296668 224245351 647545134 326224679 327721035 716722586 200753477 82474191 162956067 466493904 464827143 476745071 35374940 851841228 274212216 833952814 471740181 792293450 605985936 762160864 116041061 598516315 539743769 213799524 481252251 501932289 126119030 705347525 875851850 862003892 824149241 246223426 292941288 615842234 278126791 475513251 660839874 437057022 822365390 259681315 64533879 88790000 263305786 292329196 621009597 794052453 286705616 716126659 421263583 561303905 67693513 173842020 754134256 314506473 866560680 427343063 240443526 847761762 314887614 511598409 595842249 11161465 585841960 980227623 608696643 49426487 586129562 325801517 647111147 891165483 905181161 172297717 739972361 500312077 790805232 44489418 467048422 808274655 269356627 618188519 975957448 888628105 283914274 610044150 566430186 957952771 838186724 316521742 263378187 423942382 822688654 552069627 635422419 779960245 585695703 719976831 909234065 235690958 653756656 747851550 147525280 165479198 956427670 37529355 199725862 469861652 153712238 748019426 473240297 56810075 530305894 191645964 291324211 64895686 483212835 793577907 272184824 141548038 550179039 42709967 807132940 619530421 394593068 830227786 27397305 224768304 188425378 141657550 783818527 164234833 710476123 493335258 948842371 849015765 1857441 850873902 831784456 37066825 319983364 594055442 447626462 7359490 372308970 130185713 756063452 499219417 893380599 874314845 691812651 92383509 536932481 327086680 901590090 349724211 361716644 917123336 911080973 167677211 816986156 486519912 974237467 365039114 692288327 497595416 48370236 446791119 165507965 607582442 219111373 322807714 21032792 78733289 157727409 172591074 740612988 637044979 105205179 629521342 610127963 121525541 690435629 490722192 987219913 984521622 162955104 764787393 647358580 503532098 216066385 729714187 235453405 750847563 804791928 181608944 933393004 790106717 855035039 651683443 646847657 781970155 930582951 767663038 648059986 992531908 565287687 380010657 634516298 527396421 795259220 160959788 560525553 783186949 473501413 434082541 63917752 447802252 743523934 930667076 104495665 292452625 575074386 414839132 697696970 739317812 901838503 214115880 279700025 12528542 508383465 791992308 658404048 288178818 93092856 722640319 637189191 418599083 371830507 412122656 280753728 923463257 22942718 288102702 960861932 255772559 687166746 511168096 113636715 126057551 511645593 862061722 20792299 257508127 251897008 320597986 557003425 873649393 32184921 395217018 695571669 251603899 738381402 817117318 727595857 107239622 645807586 545376511 541642151 310130280 311867973 537997440 952524381 549511246 491445829 435886051 929251445 952910857 349983934 659436360 542387203 695081762 923156786 643693288 584420298 689049503 903575271 305851946 905696190 288832349 593824233 746849451 855953185 821107297 453802591 617888778 708439956 239198970 980775861 648330393 781460652 419958332 527588298 821535631 264122378 578204584 305913296 281703274 573303595 388045821 801385073 599376126 578872311 367663651 508523994 115721497 922873999 614413584 634645226 395405103 755983074 70861771 970609885 942950868 458892889 178923832 842526270 421955286 569032099 665157058 61720133 488737051 516897251 496442892 581567641 844344566 62530356 262473173 944616237 759481414 347225990 581310763 739111252 273720833 462034067 163855076 635796615 754112171 284961795 581968840 202330016 786280910 641504093 945082239 407826608 834424722 458551639 885236156 221957521 18206585 325583706 86517956 825752480 184488190 370200133 543550683 841748725 77130932 579242448 692036636 96722474 32183557 435802047 687370343 737441414 630761650 759212420 511524758 929260129 265683775 852113907 357022872 592390957 75612384 479743525 574663735 850298968 389659758 255833422 450825781 968341068 655891253 632346349 474412141 563449651 33930010 720223717 873560048 641055411 945016520 42468818 803235679 396362118 995003821 16838618 90278447 435958009 814536119 302465294 632440679 359164936 498298357 894727045 496209713 363756265 896315284 423262999 583526623 282749506 561466277 544674241 393479237 631716767 42281223 691445496 65503837 932880377 736244547 509338836 893598186 145217659 401522853 450520987 324542735 950581274 819175991 540608273 283634006 72941439 61058210 133220941 436420543 362272876 131025413 764481902 660309062 755054621 331830281 171440462 564506017 556752140 402007562 82906802 574538178 859499388 501348571 200431561 892156750 278757538 421546135 657527172 333537554 517677557 371399833 855898693 728393542 767113130 514249999 170435805 251810609 688395448 490584043 968297611 946645773 920202059 767714318 539182749 45754883 928229924 261944712 510321822 103582298 296671174 834975468 447830095 569489639 751653560 905483409 222135369 974629773 865345801 457094515 333971787 467058565 195286176 907101652 91598119 960631587 341524561 950965288 806807365 588786988 358062978 148862175 617739978 380789225 650895096 884315872 351539584 891473241 74300777 885770661 219036776 74672716 838143579 114407068 425774378 902912140 364734856 104331237 964607793 480425897 115586535 703707578 550365874 156557411 158001166 946080380 505429495 237300650 1463558 92273211 294185834 757811287 106361875 363791466 945289981 499198845 813543062 259962108 435314873 613792424 989540840 561548561 419410274 532976610 253072134 264630058 312798887 320581766 652214693 790374730 787349256 856680116 673313115 333159522 319734036 241609285 80017007 127345524 890838095 756502173 36600248 560836364 627928559 755617464 87487782 901234626 780181257 213183583 731427282 231551347 136108259 78134210 516550411 606563896 382075053 950544368 921613975 810053781 862294723 927955160 71993687 116580658 460250609 802308538 943073128 294803445 640833239 917705722 853257167 10884460 355162023 212178214 997406421 253845162 865318962 286816475 858997245 931441744 817237790 995595847 970628129 38222199 437561826 813630590 358134597 713484717 146876372 623086978 941267654 661936128 87625494 190860297 541113959 810829070 595329184 693395576 890823064 776157833 370234700 58240772 382832888 783938374 55545650 981711389 285098257 484387198 178125983 309741960 603238622 358379173 424542047 752659212 579055564 351568043 2494721 724552730 113620939 339814798 822617272 432282265 262613148 222927359 138738277 836319210 507051111 892754319 338993753 947919772 682763743 645179103 848343737 20389853 642709941 380644056 547074270 410650956 910520275 46476979 693712174 995959521 39985114 723409471 835051756 440706590 530978709 133835241 268968765 901175845 879504399 982615767 886558674 213125873 491250691 524816649 968246185 704017934 393181182 443319888 328169765 908428539 441658274 361652619 566109393 797577754 270383044 437737776 775231846 706820075 369107513 722303847 863579980 89473165 613065747 469997931 612321417 57029069 152707697 327859255 231636903 259932128 923731333 719468148 844203256 214152729 675451079 479396258 480773850 938719475 356200872 321498791 978202055 578379483 656656080 882087305 381783099 520023717 869027638 565015277 780109447 794167383 417982283 152884856 791829097 148922241 861678935 260314576 89680400 62790019 794636262 565291755 426912651 653512388 934424463 915088483 650148736 132226875 823596823 835560596 357889338 952452726 759916782 174681886 935021813 935984161 225519877 587387455 200887197 788849299 646126048 939428839 363445754 383386273 732342543 364217842 665253550 710935350 406475071 9477857 451576266 442565712 745216514 222730948 940683309 492346644 392638922 606495727 394951629 828303366 721302076 346994192 927927363 116871047 873031273 96879738 521545856 929126529 442848040 539426859 753571170 358290875 320706434 808696386 726560792 203411223 398681958 774875719 940967764 508675967 233494298 743292736 585323545 655949768 564533364 5224624 774781114 264204173 300899000 251310406 72424580 382565429 842725059 956962977 113684165 860288240 641832408 963144132 766367229 243854362 464254372 498433609 197563617 970148623 551329483 829965966 433909918 263206872 253958197 479683696 210956963 291650576 42576216 586774186 475800934 207400488 466688460 692017940 26607320 387263810 516890964 87369778 623315825 640881414 344061312 14269736 298504751 544342360 56590556 523408492 967744425 624528800 6973978 121729384 664722696 366487439 829065788 669929608 348646912 191743378 689171105 228072344 336043557 900452516 250296952 429129618 238666198 82305119 819318363 448283774 197848200 572857090 740708483 434871387 645133477 225151464 708389958 509254395 731554479 682342057 69438026 681964260 759670483 901850105 894616822 616414366 876489300 802092885 326052085 684684880 155859629 50749322 509325231 318045312 592807340 433335978 872766642 202193904 493024689 420658624 730048994 272315123 366402642 472979756 413558803 456374858 947390502 527360354 652147874 38357944 949570259 532951855 743734607 642999663 515766846 105162802 398172086 448901326 733127089 375164894 470563420 972533576 500059561 529162909 313607623 988570802 236946062 957728050 977011891 986001584 943596580 860325009 811329096 109425637 648507625 134850203 552883304 379673096 751983628 322324981 469134765 648323152 562667277 580035884 52560631 672195367 596451871 165417143 283906249 861323675 174770992 107785644 795569797 684362878 525986031 175776727 801494842 300274613 148499582 307581062 702828858 798793438 813195835 133685604 722460109 783447849 575937330 93278818 290854659 81665959 588109152 681493122 146803981 812899034 535164766 762848207 632922106 589342535 314679218 154380557 268588609 216790296 709879717 430551440 49254339 767288987 678848966 488153362 732181949 532723052 905904091 333833884 924449378 99078091 931557257 743895144 563085721 791608145 284427467 632797324 306665941 105996041 527679807 438981130 629896562 348434209 515843375 267442059 352322238 851328531 407187554 624924035 331676387 377431785 100311824 203952347 706986493 163422744 105486138 567112230 414785584 266111983 301410779 327701710 215291225 510111785 566091800 493363034 894137954 929040373 48190504 660259574 761206784 5915603 593584170 803155173 23361048 863208040 824733247 946743768 95384277 272115561 237545286 327234690 780439713 828855900 705576749 573457458 598930816 376527091 51295852 882026250 641931934 189767898 778837013 707537995 117300921 562714835 737811119 781699635 27069763 373985283 246856305 186646894 735081933 172131252 944358999 750650903 765774663 757096053 735678890 673630713 466381948 672089350 202980526 602910885 909635655 130113396 475569424 660383184 876222436 2423952 535688176 804753592 678035066 445572764 308238498 790867571 73450004 662997027 380891621 199524222 510496780 877021665 511813284 541870788 353102777 283139516 36164354 903835483 23638453 253715146 889035794 32741798 679906056 147084677 349380182 232762020 231395570 911535608 803865131 5371352 810486951 493391076 564853433 145290291 795923044 744795457 313562090 699352769 917085646 579908427 998033148 733950249 421318116 693300885 514568834 8250179 624348049 501686378 929433148 631098110 774042682 156896736 542953171 357201411 699172420 458498239 412053256 211292268 322293654 549230185 850350893 569571062 812652674 620749544 861219578 386422855 411213668 157935520 141575502 856412186 144559094 272905308 190782047 845893680 114986270 257494799 439371038 901535965 514248484 757069958 592161773 629976513 120935990 743260624 834596805 489017850 916543554 351336781 506619867 209648 676500055 503911660 537948900 339591175 563757449 642785051 206768835 398600472 570201590 148808168 362738876 753051558 115523651 347047716 901330301 101897921 813296229 536572054 187079979 461518448 105745912 833184903 374419484 72953412 229903860 427143740 718023897 735811981 312872299 267335494 451773894 520271877 117046652 526192531 483757640 769943828 352180251 815574628 504300592 210098961 688394885 653677061 12190403 936735212 484495962 393891399 449275541 196708743 161811554 268616805 475036577 880743370 696391617 395237309 500799594 765921375 373235687 247369390 998996627 709220812 141435587 155306934 738586922 898934281 775775082 109824113 579771001 366986587 174575425 325810306 983250982 55437914 36800215 338995040 787695686 924056240 561596055 833551497 336103063 847429841 90208642 735451661 14888138 406569234 253413109 12487083 657049378 447904246 675462371 543962308 435003479 495946391 62530332 963585671 531117824 150552796 851785874 242528530 34508182 12477894 12036840 945434119 879991045 88404169 163046385 61459567 901655929 578919462 811509688 230607545 862873438 536248559 366997756 291941127 981243863 700490644 418993460 957406127 853533524 526254528 14251179 597245747 184335388 100767042 69553109 506868699 87396738 431711413 604300538 724847737 298896316 817880623 575354961 65655880 482769187 639435734 869544783 252972254 252752968 577313959 693431117 354978539 406381 229811603 234801908 927795463 841833993 10683843 481529822 796755903 790948172 8051927 257185165 30685215 122151277 625750399 873541476 685717540 254122320 33089648 806868363 814560457 807679475 916477402 518156089 922799249 154748416 229523729 356218182 472697479 896590920 862293403 773445471 220245057 9495645 172122355 908023597 517823540 381185713 440728023 793823836 306560728 406211732 396459885 43646477 127942931 344005351 79379944 437961704 661380967 676239111 640839090 410914647 523858777 180236303 956442411 511509250 281994225 650638971 704201613 34978337 949710076 967599091 255445553 926981870 345833103 942781567 118919933 241309564 500501135 337274211 40397135 493489000 415351028 449326790 521735890 253138992 51278704 491862006 454589921 94689020 199580769 904171408 386670539 986946864 451278887 547856885 574448319 956545432 20459704 237696841 855623738 993015231 205412845 417226190 701435838 234611160 659179867 56276451 532742568 143189887 339956759 695566198 537114620 167505990 815919889 179396247 743333702 174290921 689610028 848424524 385421604 634889463 631662837 869774895 284081086 974769429 21019981 587435628 28564138 272164515 130474615 161866435 141140534 55895525 382689431 853856317 836082515 643499092 940231017 45641840 517486564 391122459 504687919 801311712 126199458 948083467 997239659 445605742 595216067 969395676 352106670 649300995 86328463 549195495 567807906 576932943 417904605 720854874 518769179 838540880 57972919 808120983 627618603 296611680 922015196 369778166 803532815 871463024 828971176 443479259 33523398 104264557 856270021 924695332 933939032 925373359 528940720 962054713 148797900 531356656 757543594 483025415 761689643 45236789 24123581 232347873 893064567 874617267 454534081 719201066 813185889 106619958 197723601 77228695 725631665 516150789 200224690 74657044 476087883 854923415 868135989 298220546 113586150 718143324 866914124 958320868 945970331 823295618 717910381 114699811 203439594 731124490 74586335 201123130 108783364 341880638 9835448 219155527 440812059 795015031 748025817 392841767 785521207 290723066 307734134 773902313 321091554 908417612 524347957 820113910 682893146 150872724 168256623 341960053 589083393 974427454 866289919 902862320 246363664 81260489 90878324 160622445 622628350 577263185 846406691 521743653 849492752 347426597 501172319 539828413 80471587 811094403 250226641 681713123 981301156 650567072 90516915 492544558 34882270 964726405 513188429 803556414 926998804 549290092 4722890 748019629 725748923 450861913 480061747 323339911 507018248 937121767 870790153 590208037 789339601 693837710 641208241 768620956 1346736 297412542 86674280 129556306 416221638 532279147 770947708 508784372 587895395 377992902 342559762 108582509 417098495 438330314 489955252 585323059 237244066 442440974 34372501 760285216 896157988 891611361 689414081 906715453 574605412 228912340 798226668 713207767 160293549 564301773 758905258 53137179 678836671 759466859 476704403 146301962 92232338 540803758 839285980 393836509 392049601 225758121 237391194 239455655 638161997 629374998 460284944 138986161 716291426 359101782 994521476 593674813 482593641 807808626 976343298 635210264 693943009 839474980 8524350 144182887 474084549 37910760 776856711 907013830 779099702 270078392 256784616 599933052 30292828 898226880 141799566 223286010 449553795 637473132 699113796 843869528 510698247 167502203 843123801 284968598 465651351 356534533 533423871 677505072 361945034 239087708 524953995 324707762 132598124 866452458 678256627 659548081 299997032 11270753 667716539 644956186 53164874 145320063 657963486 301190009 832513616 510934503 180515404 493901088 658150737 705816654 904881752 545152849 961347840 146252977 104530154 473238032 773410094 529074832 59758746 765201121 791857434 888481441 629345707 794467183 718517810 39535481 798729342 116146101 397522145 410350102 167600814 258747511 387160747 411102959 155098211 673001166 823745610 971455835 612282411 242925207 213244492 59068588 320456744 539353374 609219046 901881828 274551501 4793558 560239071 470741900 971061337 922356700 556378342 79014547 449383468 262688069 641650264 92214921 425375966 463041115 186578884 856927970 474095065 829883681 192912575 494258045 931472076 268670762 640485405 147777434 192226881 477878042 486355219 556978668 85899789 242781281 613325071 505420522 642257020 882696750 332682381 602887165 259377020 367893435 985049500 35110017 461994222 979705175 394855274 735971531 414553571 649448324 58513436 511476585 26335409 631055309 226146919 659566450 530063361 263125125 708364855 460311937 612925446 480240993 947694896 229634639 22110774 663362864 76832193 258457195 46720654 452452351 103932451 74084021 48541781 133464557 300808912 568309624 612649073 188258687 987474378 240352798 514737566 427022690 693119591 9619268 740121929 73463227 350650285 878858415 402011691 926975214 617859980 146792952 898381206 575498631 585867786 917916002 306202420 822656060 345816778 146404758 170634069 64478234 232277371 90312213 227447896 199526162 473570681 574345715 444592769 639165853 895799379 154124751 356669642 417977 321318720 390426442 246031933 948775525 273173975 562694525 882403147 508832257 741782467 42555781 124033930 603789558 933939809 941144130 692132063 354960452 986424949 456891937 876302807 56889201 841529635 366626851 380528035 460719183 831560233 410655489 977610111 308349561 495605161 546635366 511890416 249190504 530347464 777339746 899595366 432707703 701092105 534867821 152541388 693272979 327086249 543455893 614026860 772737781 327640575 792168999 736390396 870855372 181537672 947952961 607020130 569619028 781187703 192791204 603453734 324410448 170369187 43974292 998904304 318905399 963426446 687240328 110429999 340428346 518557967 726978395 831911028 666529977 59455889 540115590 83365338 775444870 266692259 878702041 239306007 546854426 990378218 17120200 39885636 956152315 297128650 789413365 231304376 702791540 352797420 651484071 968753284 375640335 173306477 237742798 295775236 405129249 842784388 273609112 231924146 245601497 759772308 744045515 314022727 393305215 870276704 648943251 517277924 310299794 807833221 27641017 892841273 342265789 495130395 67800260 83152843 999012077 36763984 440883205 853077339 804327681 717136535 650779886 137772501 521685514 395652211 702029730 291994216 346723805 458041786 749308037 730792570 559213065 143522415 73353371 875289677 730342171 252321854 527841480 954196686 943476628 824595634 296896215 323728560 453661468 713983674 53738862 174809150 856913973 120896569 772054688 719228746 389762666 340581813 549243512 600226977 248355056 536710019 391364121 615010685 711217902 452630789 342899888 611248834 876899375 903843279 513947799 795353149 357698172 663039157 491798063 760580905 461628323 482492851 110733831 462659002 459349301 525906673 241654090 227395162 556402636 555230326 81665425 676668584 291770751 522954277 160049523 72188468 335223557 947616677 198517355 827556465 559144103 758578726 578351030 91775358 619977035 946643988 261394619 421106542 902066693 410480059 402323316 846417249 880901365 992361228 239545012 235588584 886727893 525619888 979743864 524797940 922086673 446647380 549745078 86613283 662854501 29644078 538331689 122460999 743050773 519513151 754399596 434835152 144201241 780922854 335977296 232551893 463419787 311674469 983123503 737988864 770653424 754354693 38970994 587370914 261321526 906081368 361815978 350017580 776817146 724486284 848049447 336156472 706025209 122654151 400319629 431813918 708901767 282560923 58319259 863467538 240309346 471590418 120270075 41653593 562769110 867662150 760656109 556104126 614653579 856024850 763800624 123211181 859585322 528970166 932097467 697465754 955234240 326951753 714475779 411756348 204122079 762655466 516224926 809843052 532459399 566756455 987029818 754160735 986669047 953260794 628249322 385985368 298606326 468352804 396725711 197164226 789270300 459311205 569737095 222572000 827400431 74175232 383623444 362075531 563257030 109947913 790813597 758519588 149284227 313345480 188151172 948153779 556119972 572147300 670919514 598478329 315399768 586212723 66337914 486047705 351664002 691545806 944465172 797682490 80751762 66123895 686249417 839199154 488846223 635576567 437622613 12096701 772627289 906309527 801385887 790121429 144582406 442157694 929770629 740547559 497631559 924194682 858695579 964436895 27694962 596113860 270345822 531298636 674646094 504879995 569537090 465614001 834281238 705607212 667636840 778914868 62956022 690327383 123341667 653655908 262161665 912926043 582919679 970934414 208379299 858649956 58112282 327622596 202094938 171468177 429926119 669994221 648410208 938835921 667257955 71307105 704442108 476394972 716961459 109802752 244394972 338627349 537320825 168277192 753220547 398677006 914161829 348922402 536510418 200834505 658298243 383752416 201189798 535145073 230273338 275583955 573080728 358068385 47284776 441357252 566018870 602276125 693540618 566099961 285869165 661102820 580088903 714724956 277192786 194922154 447884015 167173219 591358835 732667034 503563196 908146536 920396600 598736547 798863665 429064281 285402614 801469846 166539904 807064087 778557703 516486405 196721191 328799964 277343610 162366533 559044005 453015244 914840197 967258817 165368586 317196233 811419845 512475473 695086206 651966392 355001492 741964706 126673463 312282624 500538664 999823681 86185634 460865076 640808406 570713772 741184372 939975232 493230723 976485790 416725314 445993886 786233424 574487282 82764432 433823287 111065493 961162564 587701482 6394393 341756128 782428417 146188311 339794988 70903964 238275942 204630730 233837506 758894390 21655024 623461028 454275295 177081108 643903561 832779771 943469005 335518627 246864807 382142880 896371019 238426593 852265796 792346742 840786799 584115567 192730732 245720306 808706697 999048361 135428937 572377343 149097796 729377579 100362483 670372024 571451548 24379353 635528938 812714636 268510656 536106764 214044583 524250812 680169433 880485414 351040786 552524600 129817326 790504542 404002614 498254259 96895201 641474691 778825768 26590919 926508536 926369156 630601920 28753463 1480892 195779270 540615885 233968777 424599834 199584104 206390459 293169767 11556747 305820882 625771304 535364232 458923505 24979514 511124023 152597886 102688427 447562492 699618545 746717305 180829793 683726610 748054696 377563338 879082514 22632207 104361896 545824983 921387585 74359509 192284056 777647100 959839727 669372737 871201021 208315972 26349280 762945464 566922468 367094902 198145637 421376933 875865459 894283393 631148821 447387495 987363117 312360095 127697319 257461315 788615761 566274760 611552298 760913403 1071499 338943261 666489975 191894818 422115712 72667686 686553683 932888733 886055238 306535983 955441924 232818247 335148516 374934569 332837612 845790561 573889088 194205632 707888208 792429190 262588744 85654809 924724391 884123692 980060850 450491643 631802218 311117674 774942406 376095990 220733088 457537811 939311025 450972766 252232820 686312865 174149615 564974671 513282013 976346472 637788520 585087949 10962317 70263898 363652442 858903227 503901760 280292990 887660729 14939011 164592886 530288598 6255776 66521053 888265743 608550035 911113066 152974906 361729225 419123662 150011578 880994954 89251633 913084919 881262940 615102348 479173267 951669124 616996622 480139115 746589726 916895968 560319857 27327991 412189172 953441957 74449957 879084888 183205485 850998147 466519843 634284392 851002396 471467753 932368837 548495171 996399076 751764389 118653890 288248463 655740769 731771806 204053153 132810240 369601378 974293176 422922907 158591589 266122369 511933668 986446479 114406654 391371868 575342222 413373536 900817832 828060172 349983291 211604398 849091335 720876481 143387963 920817863 397553859 608838250 527126912 551075268 702358307 256530084 562709595 856334018 602498826 467030994 699683515 736729267 196939549 742027361 831242937 92111130 866271970 660310578 79475981 217400242 152381896 979748277 598387772 111433830 859173311 489687104 695849563 973567802 248546374 192675854 466570054 180847732 622906 312398387 171842228 392160519 388676104 360071161 212746376 596510996 789916954 450846103 745180172 337836935 972473155 217868768 776086468 437845557 123516149 983222548 383784447 176790039 992752238 402797979 36453907 896287591 596204042 547786133 685587716 90767759 782197399 100521393 735243240 245523602 985153407 683619428 439193864 564376875 651064819 373784300 981909110 522355286 351535929 433181513 684489894 370650835 940482367 93298963 341722924 769518494 835304371 936430680 943305832 19762018 998279220 636064807 776787556 932928269 588249859 447043728 29834869 92416215 943908782 644523388 631007810 693523745 756344701 576540377 651679414 382886524 210967658 991096173 141858962 226987634 899067843 173324391 510935030 908323876 70392257 195420996 869344209 654011554 954483763 482132922 702209092 77567616 709420665 333452935 994294254 914258454 447111397 943652443 388466162 451849507 444902125 26891379 776097305 843782240 740443718 403917032 501192117 914401590 823506239 963753646 47537136 123775127 387010667 791133622 323496515 812393861 330350535 571886730 59931119 609352543 602906447 814647471 385893836 322865887 63463796 993113928 482438138 311436208 24205336 526050468 428097343 723961495 775013224 338355997 624854847 354348759 2000543 726691630 822796587 919992219 313624292 440608264 701274782 474794401 883491413 34493521 810973168 352645978 589146945 612831028 318230470 249132741 890212493 72320099 21361012 504392514 626859346 332152747 829751843 623593408 741910567 703987061 776946121 210478259 478190438 428102172 484530288 288522254 480489997 867470611 432615790 932401311 840560014 980843308 753769553 831495882 233066688 527802165 935992375 833811927 471563633 666196641 958841859 985656736 188978350 339914490 203894468 718099892 841034338 440094721 500827102 837150922 894284531 561985907 732571304 666025765 723088072 670393887 833206586 214539361 592482723 752647780 41564896 918150508 496585740 435260092 435344863 324956285 832811242 383886402 221560682 268862996 498598546 644412189 766362092 763938341 128986392 872884592 814625568 255335718 844422587 272077624 476375658 664229781 932850640 172889232 899740 798410471 775722742 406490787 929995191 292160045 231666595 546425345 496964733 113234135 620310290 636804998 961141505 338873398 532939901 68471331 273544698 165841225 898443056 904012351 268765470 114907160 294602384 308104522 823924167 476947630 849922826 544918091 214511682 298455402 876400575 731802356 29094316 82395721 411394386 420515896 225122161 873448016 113503868 229104126 109200539 967282739 376371077 660669474 873050816 867592578 903118485 313125226 172483902 739767018 931272777 132729335 632111424 302908668 459493049 68074235 598876043 349364883 918856344 829728608 193365728 576502907 875916420 478834466 340258212 169139230 155674257 677605578 434062380 538967658 295086102 32901302 183291704 948235169 327865093 449640052 150402957 194444988 428763415 808400815 607812130 63244243 505164119 950533751 405943334 961694510 809433911 325315144 197864709 426277060 158845482 706013946 331587361 407738550 202502711 940354258 479180804 165456532 403946647 113258726 974825362 217688045 714984876 944645589 447087507 982796473 167174724 115615016 893113686 488433566 573955221 220211392 514039007 728161919 985901450 77481933 71405635 6108535 351638146 946018465 759026206 317023590 607627746 443677731 599891422 798062500 996627185 751563870 15371836 239118472 162358761 523946246 314290059 984911608 201237328 883216848 649495020 416798681 902283303 802081847 664703795 63850329 928737075 548423918 834648442 361455963 599286752 569639294 150186624 710142273 633071868 429549234 689337495 399327595 22361006 631452884 491472442 325073638 135536975 285146365 280839765 408100196 13187058 450849348 419044858 397797399 716754698 776396876 905011403 477233680 890228263 563275461 762538965 141264470 605570914 628979545 129360005 178152916 878873262 817616683 693627934 99438267 831477185 25270192 29972354 221648971 561811544 862841541 193274274 973767288 749122462 911954959 589526427 809405031 801986198 348034838 821773415 846747052 97917210 972821929 28206450 295431981 844925061 243728369 159958188 415932901 571450766 467063109 572335726 222772773 296052050 513286293 552440473 501221172 375717903 172938824 699577167 21258236 206595808 410584960 703335694 348018981 494984068 926227717 305079924 693713026 367631260 958589771 391853248 382053333 732403140 520783044 225218344 987776906 294042108 648270042 669035595 192038658 44812176 196860278 469703875 374282844 957629650 80404388 788002770 18612087 973295634 669754496 315541159 326742395 123734181 906242910 954599869 594047865 683132976 703447700 834783901 877701782 116842932 534777677 196141782 420440760 351806815 671939173 19990951 103621253 566686616 76131856 76768082 192315873 467453659 49000599 729940321 944656724 999259751 359090083 37408844 681963935 18426059 56907334 747513847 952146081 463455546 582825799 951287294 351342781 693452740 896494322 294546478 121272945 723878540 647192269 417565817 5403738 449832330 978152376 682256868 797784580 482533237 583003721 139010124 155961096 788671922 539077605 535089634 910592139 368237618 424482928 47438978 730524723 314086777 262328569 802271482 932610371 527778817 697420542 642630622 534074591 355610486 169123961 435105265 773157673 758060964 465661403 915824965 33672417 143558621 42310903 646695572 649858543 693495825 593046546 829764395 660455723 544657802 628467807 704414616 577951349 360009754 698274916 26027956 273149232 213287413 819102305 163372891 228822949 261502852 236565553 504403945 260788116 725275837 364264452 544937694 713045552 74078572 155654754 811316540 944526979 216534209 152695287 671544410 965387402 368375376 592220329 565230258 420373899 478296686 35131935 657170056 303321383 616746530 855065143 633175637 321146792 195058235 474945840 921945097 747476597 116216140 421068654 98842408 343336016 504885449 69509837 242975711 952697862 43296949 460431558 822764413 843420458 163079732 953040990 544074730 783480155 220961651 538337815 960274439 594812893 953800393 495071231 694008342 936009721 648331257 193391474 540183955 789008363 712986374 936585622 395005298 483414480 955486777 538621408 536250547 4013305 699478222 715334443 187747170 805509410 734578056 902234991 305442254 727060198 54246693 831589734 932692277 443553597 106681187 358543797 421569289 354297113 817830276 690250889 530374679 122944636 276507418 785066112 456072186 251481493 772867399 261067403 383857382 954471162 228357754 579513348 99849440 113085775 448093580 923673185 991069342 504102813 513137504 266579841 876200524 129187728 753708311 755673505 318570325 594748328 754070049 413744710 18000008 562097520 192637693 480324145 704928156 659364524 811528146 167865897 210584573 958875322 131989973 54140299 954683329 859979899 479492510 274873156 70583179 28726824 313598144 764619957 737634355 430111881 23605361 919540173 770003774 706787846 141273449 95460474 314917528 696014462 645265933 487874862 626508686 588014393 369054395 416826570 396829426 535665214 608220118 908006123 332821970 88607396 344071 604165308 817835861 822625174 135334672 612226752 412413282 522875502 163540640 266092988 338459639 952010798 621067761 914148650 832878697 864824349 641771048 2521885 654248925 303959663 228140191 303760944 82418840 320869003 987333215 805786893 49794298 401933692 104274615 648052062 868334887 29262796 474420594 451832488 368003598 494991136 325856421 850808254 432805273 861861407 544854766 901023380 973980878 159800385 140738393 429964062 287320800 91688049 942086660 941785535 496668791 863436297 566580249 212984475 883071042 633099470 375430604 958772868 675334663 657578492 359204039 629459605 64625949 258992887 299571013 413692725 991927201 139436432 60705814 891839856 518267029 316842291 867054179 471180515 850833240 268868196 558373577 977073232 548345736 467843568 446897059 952947924 791003521 722974365 374957852 650771128 405529467 566462776 843301184 52847747 73877680 82586367 826530164 984917396 704488673 764524472 423928818 499570551 895482381 518354495 892334697 370004517 574726397 380123223 944679577 246232262 770743635 830138591 793565559 792075043 845073852 684202203 601357835 759569868 108938143 258765424 53674303 166750929 828251279 27367148 542586244 59997671 865292626 749360599 797620551 337816959 61859028 853768676 284168871 995618038 537520736 633134548 389895674 559882433 2827612 412922119 786646392 530789067 547490158 371653294 789289656 151125155 978310227 173710234 437739946 43843034 96455133 474418198 848167800 522833943 460080584 970203039 122904773 830698961 957905350 10817715 952722203 886552532 738183839 551874164 676377353 766142673 357906660 945464664 290263 547933176 586946991 398755675 728418562 746944672 459381842 769637462 589609904 624403916 369093546 19977834 678355719 872386892 827045272 682217639 222080983 970832696 723516775 524342171 292384104 546867054 968906143 334160441 986788733 894690526 884601382 754589531 842773156 199480989 241212827 602781843 239004702 941345578 964282998 415402126 820379107 974229802 318838768 130127518 944838758 803382004 959059266 123815548 648684394 578277368 538936567 524444403 746196671 640161867 278552782 597725531 699442630 949045447 716424105 154975810 234981539 882459966 113431982 926016318 79481925 90163709 721683651 577088872 97475816 495189696 95234959 368137393 625558112 865138662 442969586 109015590 810027032 395357757 132652364 573654987 639475780 308820561 167847882 975903287 543183314 82873966 591114108 561156116 446182002 943784664 127510402 621215166 12224964 647324423 399637955 118668725 397765798 386385294 892679964 705158130 385433144 819158241 570053318 934920047 996143802 138478785 616982435 638899999 922222730 949062619 243411356 334385228 171572305 571208940 728163630 585273896 682079552 222412215 289310266 356634606 433955200 761533146 815455341 424311106 338561008 292557711 199638421 63294820 432763552 503586160 937188687 231160111 549018983 708281107 991057921 472276142 466802950 111568104 479691158 58253436 995316739 355514508 377904634 954683361 164908784 575395860 258206591 766177568 750235472 378464056 231712913 78632491 898163412 286850416 918363811 740154226 189559841 44137284 613039333 999648245 474015250 443074608 733003135 958050971 885244478 658280741 194185216 347379978 248492612 360508405 972907342 952466114 107140124 450700860 267178460 22915526 405660410 93875713 742424086 304748682 949986775 374791806 787208157 755311939 107420042 262783610 153999312 973164523 57928370 58517230 627936621 642216149 707768592 180875080 70494993 189934337 123443612 828798356 908121359 48868074 110940763 759064612 240034155 868521906 227670726 167000547 451701628 654018431 974255057 501689513 879696581 266024931 517938621 901538407 526974250 621246257 642782097 133979515 132148422 214869104 741578473 705108172 165638665 250083613 407243867 93274841 87773396 443166254 742061701 183598723 380706495 268396526 413152530 772676370 582329040 46482473 205093625 310724449 517605755 149705444 275320864 913626853 433780680 451736394 84436214 243808616 717386678 754105776 750894954 957070113 340173959 849400562 241559370 842521614 985640110 220962864 480331142 799200245 36625710 865247660 22623686 823096060 394322390 652092243 27161760 142908849 84437913 569048694 872225284 118624098 144422109 692422179 607230633 937693791 400194192 112728708 206513511 693067099 726920835 790051964 791977064 389589929 930032944 773006203 486446165 54443841 807942522 920861566 443096200 679915133 68317782 689050637 747635012 525436646 106030519 10531247 884291731 140020058 533990535 904403565 956311931 944690602 229503640 914293095 748635323 13013605 696270822 399653228 767411597 979973846 752087976 624464549 306819343 97707526 566246427 494610876 795971805 601429905 537827604 92948168 355859302 324652357 800076214 598835482 583490189 192810879 487712835 124459085 92491138 552200384 847199780 630982429 859139839 922250207 459434881 639889410 821829977 694374204 748357983 280659772 156762947 1675413 252896233 387108351 358516179 991761361 326414311 52656686 893230943 817536891 762146483 709504045 795514678 748581825 930242853 176347919 956980682 592125571 677548621 792086763 55750712 20852357 716589902 168054629 292663060 224336253 202103027 667629287 228456198 363994614 790565507 637842210 212562248 241290081 125025138 498763517 15530485 733076807 956470030 2533439 134683765 226995752 280791010 19220157 404086680 451286995 662084271 240597676 353287023 303530270 379601977 789629606 836639290 124249859 99994282 523034437 152976947 185894777 134012715 1801684 631808773 76587858 84452943 3507139 856675649 786095948 318917549 438449498 355681391 653406231 742676311 67241357 33142882 835680206 47359613 620276986 644694345 677343497 723518441 316011149 706331018 722288542 748766829 880588465 676746383 277882704 577438879 130153112 890337613 904734604 602712159 287222325 82355406 161805442 395120160 595351555 491274878 150559994 475436458 637387427 726296386 154048888 2513941 122225210 501925050 453687892 776178613 236667604 893269950 320785025 611019174 250515224 823003843 156930218 838537661 665284876 572148732 854522693 648581741 294585095 763061068 88634067 839740365 504371263 399623415 772488873 374015624 964428666 293182995 499940920 91340965 395888585 944864531 147085783 886719601 143828616 375663707 301620221 647056102 875388179 131909384 99087953 101902980 726589905 210735881 387799079 432755757 494158052 27133363 607409113 325727835 421258890 611377348 613286675 565440888