10000 407
384009217 684362095 682948927 118680093 961899023 856800663 938917690 891650889 619616862 539600283 833089049 995825150 697128183 530703583 738422739 615216114 746048366 671454005 735209828 930949048 949528778 286621365 667849733 176986638 267631088 858952484 386252463 650294529 216791424 874605672 132402339 590940206 719947607 715368607 237434524 891073990 253623119 73771989 202555882 183582855 424136647 83705285 317475110 468978178 134883183 836381352 2293220 777788739 523342254 72841167 133748253 739930634 17526974 311616120 91806551 711524184 933795138 908643494 567110528 821548049 747292863 705912543 29390308 307733643 608331610 689118438 755096222 411946984 469577058 856977089 491563676 890177137 924712890 723322843 205910100 943742720 536686791 611326422 524504521 734660721 119646665 653319547 375494301 504907542 973513804 836734155 906754074 376395392 752857506 773070931 107304133 555460735 889092873 214664062 722385641 949980276 647787903 747229788 213986669 833285158 706243433 649268499 508455277 447751879 889983290 459307579 810674237 661108038 950645655 610855572 997087704 37902682 795219298 771843065 557509283 670118166 629500296 369753899 988957728 864568451 832259537 126591495 332448730 745763187 33869443 213767251 148277456 625550789 670776230 648413715 312321472 860819387 248535757 855940363 602044822 666756474 685161195 713580163 830150887 638934258 801847555 372239928 603828868 14847427 730694056 648483075 693514253 511294798 26460737 364763047 752001195 170233158 213602160 280052225 733092004 171580122 593227615 366638556 891718317 681907189 662716406 115673244 582929438 320182388 463036756 283245101 481345785 99787232 525020648 528075511 439566232 539943813 368497673 137877174 468325455 755978517 103805699 513677632 173055179 205358120 847868213 953892316 731679393 780307504 717076728 352995097 426441491 716649019 936436292 673218580 556659971 272938047 336596722 193455484 157274849 328671388 486777944 712277655 429748403 116940927 62715026 311578596 33095427 935225873 622471466 997438207 29005966 350666169 306407066 624593032 993292912 467112158 847513013 250366541 260427742 823074363 46379020 385673586 660786045 108610111 301086421 674534266 662216020 171687665 670814773 709872179 422083608 233576399 817290393 27030162 206275064 650379858 336751355 860891405 178207822 419255856 160620789 891185288 784140753 370110308 616272165 352537121 630339531 996144580 869929249 2339268 332063404 686614464 604070852 747597259 565835188 959876107 242083328 704196116 863985133 190517893 436638503 643130550 437949215 211143146 593026131 69359664 417749142 932814769 998042270 501628727 939287103 71190091 740596076 498957460 797139244 905583128 705972259 886994040 726406735 949821030 910067155 922142613 321103318 6639652 491575170 229514687 872436599 104744682 2060162 912760361 329703021 317697749 287070365 56958080 461359620 889769775 371617201 320334837 352319794 526171087 25278247 969630030 186765533 991547163 225253477 180269134 723433798 346234564 795914257 365067321 630946658 282289769 824426493 579457505 970192750 596964793 496522646 486207967 831312036 504457451 885903976 294974772 434637154 205018375 620046058 463040372 49790996 327453011 994738729 204487985 498380560 25546393 533435147 565157992 999940292 376226818 910406055 369476321 249175964 722358430 24743398 894542425 339259680 402742303 594767235 151041214 27573772 666515053 810268163 210493405 963172553 840830585 772128845 736056658 821154520 74668160 599289569 163881067 9817613 982841779 866317020 937820510 818718243 526294936 94931204 494062484 830736422 377873041 524356872 264530640 625687414 466282911 723785758 723915340 559884912 975857246 355626763 543978818 198673418 397164129 766682891 693541421 470714669 179319660 29384004 381612452 674110878 707102237 604037527 827415387 112577345 821071492 692242771 686160322 66637727 762188367 341418029 337489882 178812632 582062084 823855490 51411936 80967283 857603496 551774755 598065328 678920290 346245668 485440636 201081443 130061330 966506554 546960308 488602433 142246415 552959307 900226844 301093749 518536399 305796411 171410609 482396445 371276420 833391086 858275064 984434142 276410321 628941925 135677576 936859811 201571025 249532554 905417565 295639493 640112284 920148755 670819959 481562570 555097680 258325798 537993087 364055725 436342873 714102020 567260601 434018107 810996838 487262004 265500506 240281137 454105578 28544210 894613568 511259380 680944799 888136999 421732757 907253797 480090214 782461695 503826785 441603055 489266223 973352709 723150634 956353552 203578195 188902487 565295158 179486580 647109717 444913467 702541643 965112854 551511501 990441054 203567837 58904494 145454171 955842553 190276737 548877939 873620689 648914924 830073113 409017271 922007707 241895324 801850620 49053789 320479477 83941085 585662910 266353353 864434549 774872350 876674304 578698228 400038440 686520884 759307305 308835942 309991395 722956182 634748918 8495960 469090943 934626250 220184062 281427324 688286329 463501792 968748664 834769193 382845405 174996933 72010590 848679181 502742015 377833155 947439708 730424633 124427186 715551150 441715773 293153052 621800348 553497633 347835216 367114857 554017245 823162901 259695411 919244618 551859497 391762075 711130148 16590540 433963402 369901867 745078355 884214042 138453447 861392882 627289117 807521049 292641438 112225148 774483884 707687677 465852303 448987409 624903963 177518430 722679458 621065226 560855484 936823441 366343404 719083200 678481160 505405551 993112194 440468839 892592497 789888686 777479300 453676980 971017107 920410851 171111759 884988042 973166335 35674798 327673147 958481405 255607271 810040618 910202635 938507499 970032167 19944259 254440569 81876383 670980643 752065636 844579686 780548698 241546324 149604184 864316756 449673684 527339198 290991048 969701353 832706487 681709727 198727166 403161234 325904009 340343009 525242920 574984937 131312433 263130472 965337443 560044954 494705884 285446437 209881774 885268234 989851078 549528409 733706674 476077421 80304985 260837402 397855973 198682230 145610749 227245895 255938268 414075413 797348636 589016038 698232265 49274281 955087166 565184116 411777595 581531228 987513904 404815621 533796727 828018027 499058672 590263197 36172141 192414536 260618975 746608042 789231869 69030736 16626399 374625576 230770710 560349898 760833822 161095331 931115650 520908605 79467834 574409180 782938043 88353531 215525760 405325562 69632198 663460676 838097013 58533326 723931289 195069481 16293395 685986305 581512543 765487880 908162580 411481644 923156439 313202126 669584292 342145989 347640288 932240910 149036638 834925156 40794626 912612708 874709861 581337022 601050795 742222275 534799202 237205199 997415890 916926529 523247869 590659015 965234339 212730826 747307996 89101415 322452659 495196260 931957224 349579962 641428937 804056282 703548505 337037964 309757161 426948296 467593808 57853932 847280320 481421775 492115608 164326333 658607739 340687905 538892702 522207754 293901415 639551650 333624401 751616073 414584893 963168745 423697243 357141383 544129760 987654471 433151691 770015615 100483905 103956480 846333848 497516438 638326084 24166520 944874905 669521831 845075242 934870376 167746108 487514905 103945362 441671551 611141279 567373020 49598720 868645421 909422727 585845314 650019123 618739694 906087749 456561697 195714463 335511512 396952399 313332632 78568963 239437639 558269789 500741169 32002515 929156138 602554038 483826095 96961073 999288092 634518433 986123970 342910709 428904482 721944335 678690417 147222005 368173353 983693492 906335186 580896276 203074792 862116430 313873310 353752907 593185915 710314847 143680708 804375614 582830243 785445446 988858547 222348721 544436842 609694483 436407038 366227021 770212538 153226093 20714749 28923604 13315260 900602630 603740006 740038410 834582506 982825840 69374599 641241942 367613860 34910889 572448263 372633929 170685943 458574312 686814793 915035909 436933441 302271034 833121066 58786921 993223974 819671473 11043479 858853481 679980559 907762659 273990734 443600365 589764121 512597039 413583209 993326362 909110511 578265514 362660453 997653257 114218101 275575551 825985887 172801106 93910524 707386898 547487787 849957557 255882820 861622362 568230061 602686165 579094740 450141075 115488850 688575534 883558018 587497574 714294022 279173632 231255769 653400660 876006465 424315061 629193582 194360119 33685218 793549465 511182600 71303991 611779732 791523063 916054403 354385358 115182061 113840526 532707137 351888405 295282607 495771087 725672663 643722629 641929313 642276220 198077346 244401503 274728393 213048345 55409031 698922114 173931581 790199505 833331471 548691623 602994131 851455708 365060955 52236457 429021956 453028383 877826501 908329134 945878162 199044199 487396502 420479299 273484488 400370569 354672777 501564251 337845726 96120625 770031763 185882833 934333193 192465166 280537118 642379149 702617104 624426891 718767257 509194186 208244950 291893292 701389873 264261012 675284673 549261989 884127725 824176148 401640918 122364601 886721339 620069876 670082870 580511680 96731233 785203043 79904292 452095993 718194444 8794356 383102110 162363361 441445835 729642755 752440995 120749033 220640845 300517419 35191628 422913719 132036173 939888745 624283059 368379696 453848047 841425900 381000743 829499435 913813826 616688232 759884471 762794178 706294889 921807473 865509489 923604066 105245090 582921081 781076202 637952118 882903127 705903003 676655304 331376841 525322978 482357178 5767481 991011293 33688845 150101999 533739423 755850620 565684894 39561707 185704747 227198554 587119035 114944504 380688153 951864843 262130258 507219826 337534543 365582537 292120198 338469481 515500610 510794301 52894035 360730792 955251303 663850076 95890446 600478538 933580644 1685560 489941031 915706804 370812728 348730368 210073547 937470518 145409801 199582744 820229276 930353400 537320333 419448389 597659719 601840569 372504341 328022807 390511488 178788924 793075809 252297737 93805492 544332856 687466576 134743562 856491933 637759977 893410476 359470133 3967700 600198372 147547873 244343307 918092909 253394457 816769123 962880656 572544236 139494756 666458285 513024343 683457638 606560291 486054437 610234734 907974514 251044210 330346439 535145015 248180852 620046467 489750580 284062378 78546798 749462560 495518389 797691700 256677031 317454077 950147659 428279351 991626880 668745350 775463229 807599580 482115286 318661592 24664453 566772061 793578336 292614963 207831535 721177898 878387727 307162510 586876042 820372201 267668428 110828985 534372624 134913185 470640254 595843877 312303799 308682214 198545298 123015757 652968945 653513723 559629279 586175339 940996614 287059638 58038519 941771279 722290776 696074079 3155151 855551765 388068330 508233791 812999944 430372829 135941573 333896680 787652382 238634879 997067509 442582150 42738938 456939108 694496466 213512636 491716611 80766894 569639862 434302439 525450831 452015158 195186129 346206647 738786687 916519959 43115997 638558086 726462601 387082238 274206182 969781745 328344613 385516022 46602035 563248363 777960516 456302493 532060189 109994627 871702339 468866494 836029224 823854670 693390212 211144550 534048487 364073274 190785402 245239423 905190929 108290667 324486021 394228458 118952644 878289695 584624970 335271208 877547042 954347770 92607726 828792588 790770355 782183657 108143361 551939146 22918566 730656843 50292970 810193422 439972846 227930085 796873154 702545222 146839001 574622439 506060356 509286683 471778481 545178630 819002251 131073212 954104563 106815313 136210413 693665613 994133712 119178474 579554358 668153007 838984143 634982774 113751968 146910541 797370293 333482302 786174075 581703276 987480819 121054646 389876960 624392832 836433210 585124834 389592780 655450275 109699674 900697802 691424610 317091441 462481355 966140064 47988368 546509614 502050017 546440225 530676612 189501018 493837079 367170271 208147142 337722823 210813901 706220567 81842893 717149932 812289373 442408331 883793325 550596618 502202227 362659454 850943226 73991566 625028427 285156892 696387087 355714264 818732976 75837609 340391378 344812901 673576053 996407665 893343377 902830687 195429814 725110056 328097358 235535132 928309122 496991345 196446616 52045608 247902724 856791068 748424209 770327616 931817359 629552390 665663354 70454616 545988448 944016261 864574137 582889708 312718951 89622014 171018172 749394869 288136860 970267638 454987472 366015248 697972982 96472889 481841346 77787901 611403114 876560886 768591653 135320389 661545902 455761763 432909343 698648471 304734704 129404466 675307625 337410769 81467157 373162855 344405801 993576028 956712506 87934660 930144733 50076555 846671274 327599706 206144088 613879334 602558475 356989901 726324734 632497239 568040049 980678518 252784161 650291517 15197159 897854518 944324383 209272231 95739410 110780842 752297634 480412408 786664843 179470116 900539239 734827005 598326816 554219028 12520978 612841797 742778541 401133744 358147371 490222524 596615328 233946599 579490300 969113529 583757704 64878494 667198140 354518247 122994431 846606721 356274512 15005463 10418681 446120329 441050394 427162513 791372038 467414218 665064087 321448929 40325522 329724097 87687276 789874133 35933455 789565280 65274454 465994863 413758726 917632161 184882519 262174524 716046423 386078335 671457261 202369210 546800887 181333860 773706657 231307712 510113898 194353098 51283609 516290972 799957997 952738351 225469670 142857803 768317270 611274402 286343739 676932897 718880098 245321031 714987173 729411117 16936429 735407967 911406103 855469961 585756552 658879647 865496731 394457824 969511022 677524957 844806977 483940113 515708245 274206272 644643155 767109783 515565933 818645643 262279431 695076011 319868882 491787678 47018665 953075322 398498226 994830482 217851182 625025885 575113256 68674923 322235470 580772197 717930761 915680866 6084477 795070069 31293834 915179363 376065962 933606335 286596887 244890758 727213539 666225982 107056237 770225801 609911068 65849986 740595959 886750000 88274834 233370246 320687585 171052560 824778542 742925620 858830536 415871804 752384581 433210002 839230771 497454038 297995996 252698815 794854059 620457380 520958216 472783203 198298425 924309899 37938507 913351214 796070248 182404467 664591348 835091869 148048643 892158838 160690011 64419740 95600016 414485498 218819587 227243821 305679664 58488642 649002691 540009673 338089927 394866322 136673239 629050873 850062372 281813536 668529296 256100484 779032913 562820615 714213406 335703047 560095563 162012261 555451479 520914792 466854341 844712870 750172050 829325095 601777163 29731825 932992292 483484056 140476767 334666944 759713605 580636215 386340308 458760752 621687764 186714309 353700947 217532166 636850506 12108784 638501471 473172252 41213807 994232220 339066089 496627049 953434634 994638874 740737152 465140280 591079070 819453138 503938583 587879517 129067089 733723234 502199893 699423249 254132555 274379233 949935429 466811157 723964850 453005579 927240787 116456418 855896770 299357227 784141699 362517490 115637080 47290458 804431010 464382945 969724685 622952179 998992570 656936547 996558361 94199321 911941973 29629864 782821124 643131532 900642963 259308027 486327756 568397790 95270069 513590677 692885939 536174014 876495085 888287486 134316372 803179518 1373973 662725514 78046929 75626621 319188915 178186426 428562024 436159447 509269470 491108207 437228359 351502672 650707845 249036267 916767667 854894060 383253161 494167444 899381257 418135290 429294202 274134547 97630411 717694466 918660310 589375095 124429255 164960912 164599953 285117734 785968649 947673921 150393039 750374405 491652298 515520380 520717508 815770241 175974428 186221253 478223783 912003463 14796556 563710613 197832095 922627356 53648689 17719546 701937829 112174791 69244574 132151370 207928300 770182229 372786599 406855135 573360138 433482719 915132643 585353284 569035906 878532181 544437732 567828262 86410903 66666645 808311584 614946963 197619752 770497689 309850980 899209968 610662794 58056914 608396439 709358316 217250738 149366200 716104191 224229574 17254785 594759545 923483903 197065805 271700401 205272339 326067921 280478980 764260750 66566186 823379326 67420849 792320300 179985393 206392779 504150267 459807589 844363566 118477634 947371494 168731239 627814856 582349298 344301445 645012227 261902421 351500883 316662732 149063494 470348597 282399524 554693498 677305275 536558510 960877833 93927537 611454542 367702748 846535977 434542916 387070576 493597634 832466060 179469232 226023358 805101247 64788553 755944747 818162511 700288092 263029851 448124223 697066698 402951809 829619960 867436357 471610619 149828227 809969092 819927482 38201958 475131889 631119386 806309188 391881730 71259043 678417045 435193544 715398697 669953710 248352851 952121571 362536928 266693124 292900425 320847246 721023862 757769421 789338031 277854713 709740512 762659400 540237438 818967257 855038890 503202213 454600825 619957924 598092896 715788580 666396012 463822413 441827344 746494475 318149589 35588341 818279750 568389339 699043208 945777945 33318602 565130728 331883265 633792415 653209754 553776733 560859798 524372166 674587603 108835655 402093710 957992365 107530498 496110849 862322232 446078417 493493190 420188323 958410581 528257365 757335615 89888316 412677111 19557822 427426044 645383321 980766827 216070144 374433007 716206394 830196074 49066730 578879616 823505370 290153407 691362031 117879378 5486317 190932456 458219249 611859789 896430194 318450291 952454571 449788597 435547138 852129894 918969665 309653167 306783709 821279911 831496665 189583742 130924219 294808067 896405533 956294686 754344377 202216549 631830061 279045385 751640157 260390670 36036612 982427528 456336988 739140947 599693005 359437347 992565693 170502161 290242300 660803115 163329286 816716539 43341568 978012430 341599201 267764467 748447542 8787473 500959792 582905049 597947927 844871667 729846056 629627057 146507592 726137795 294997499 429568756 609503044 107388934 701793078 867026815 720504198 746528884 44700993 755760425 516408483 931742375 907437170 625338893 665102760 1530106 946172660 526410154 821148854 709611437 875457626 662236600 11823666 885406561 321405672 200373003 228461606 469224794 307562952 986720531 966898567 408784783 682042138 723839881 704230108 333151958 654698012 180283458 212870573 319636420 443311216 679353172 522589488 941576970 371456996 933485488 830972476 121189704 912443309 420779121 936304564 748609132 748484392 586615475 873892919 174231598 551062366 180555564 218116825 419855510 245999622 467837133 895432434 123187122 996294618 731291891 597734689 824605004 705016481 192050118 136907096 703575687 94051278 795544433 466032782 365763365 407565591 55869200 650253559 583644571 967943226 829006298 287943562 301344064 345151870 235452622 717052382 709910086 744964155 185263973 409437773 618805417 137561015 179141402 959959989 931908770 724931299 546280856 396327237 963457433 341898345 527621996 828684705 132834886 486076869 74581999 422093760 43542758 672165050 685987837 946915675 678417553 553456382 310587297 833100759 868114392 749759676 929748102 645665806 886391668 900762360 323940856 785329833 16678245 139229730 878949425 246086252 627154548 494177611 884217692 471829049 322412471 254371437 795849075 304538154 866944131 619993259 980686223 846684110 822849778 992254416 298135434 863400304 446390668 102858967 516292454 803443112 868478270 973000313 715222075 469995093 233051890 134432000 990365630 96676235 581792487 563350235 789047912 574057515 936877806 636016646 526326549 558766428 561814912 595715187 330551938 411076929 35537770 422367903 896009964 917631340 489204401 21152578 974775363 699873467 363997708 92324480 511260252 910228660 907736688 149909409 470396932 339584424 556859941 110577024 743962379 427528921 722739236 618940814 41415915 146682939 21808949 90301901 845328428 439524593 407256612 973838209 241137719 522813126 692060079 720507378 586950854 207041130 477095544 65404204 301673617 143614444 801731474 868098394 998057835 65557336 886247031 656008546 5338058 616296091 816447739 99554464 529448993 205226860 818931421 292083415 663459904 896426164 434462257 434412855 716479824 100774213 905039291 414505381 877986107 311517101 902613142 209220239 973317128 926096095 424164015 657471119 374692026 461910190 713348267 989798640 531946089 24827126 697889704 557279645 767250659 164173977 611008987 522276667 961807968 284029999 827959660 578653626 218173707 910654365 810828822 951070592 136274551 619621352 880408296 611242290 197605887 973906552 177984065 688274302 544583848 689412272 647129535 407003703 851164214 424370469 243469481 254666018 860713511 887894271 764370965 255917880 928099362 328682337 916380608 479872657 476296338 563371284 873370254 924216364 714457548 278884049 488134070 521085676 875127113 769340165 83789760 387779760 590375746 488187207 384068921 547706627 292891675 173621443 854204049 611336881 628183487 547453466 882014743 660061338 282002911 815841051 548221582 510994313 964649536 24227377 387431708 160687607 151636607 305241281 962774658 714687631 974149914 929044787 207102292 605194452 770428059 745056161 504478371 933596016 540975457 454897452 591797123 61669566 730442324 850773853 660997699 786649594 734093688 869782954 634528998 643809057 673746610 619444527 188748094 59962531 85884638 395824455 725884016 247924687 112942949 665348729 376122900 597519984 291328677 344200192 901667658 936746658 753504690 864798548 562882386 497642015 680723192 937775336 460614464 162215828 77438238 438611457 571978222 777190645 134450452 170842120 498996639 663035304 97671842 914101779 510589556 565654441 980332606 76621862 164415021 444180381 850647369 498385771 264196692 588601044 594812797 8376792 759632452 109738916 873991007 88247273 844317819 1318177 115888267 453487146 963035318 776775466 687850494 79194000 89894097 768803039 279917582 201679735 225301346 263122445 824692927 691147339 792381832 869053104 63722550 42721618 881436087 205556815 375393404 126973614 120807827 708857494 839585285 416053070 571343807 699330033 861325947 784078039 7622987 337004084 29134860 498030518 68562625 539378268 189125001 915661723 353999749 181952138 262957292 489434935 517024189 879630541 865252945 307373579 328601026 550974297 645542411 686484537 137039162 184096944 527776934 82787165 657990708 367633987 749980703 610176013 675609852 960648738 24178559 738325623 22691357 234100002 145570658 30191347 755192828 880337235 116223704 523051369 880846039 662985706 249993022 236177208 919786546 222243021 278073837 830983036 311241076 100478056 323529311 120217008 700907454 512545585 623670871 375499315 486121971 9193973 81578675 464074474 525190503 172323184 484734084 323800456 719974658 980435296 269765812 726273481 284644123 406728574 352535279 838232149 390986274 213735995 158826404 947916016 155939096 13371226 607218746 856301680 81328175 804214390 921632483 299033320 220506460 362231416 917358910 542797611 569965671 664780957 892534193 421034137 189172271 644446807 85909109 752645299 918727363 669250168 174631906 848650764 656605013 75847992 309002858 625209085 542304415 622147426 496927162 55284500 257440767 189063633 278263526 798901687 156923040 904443128 180231144 95603697 73436679 882287613 175355704 206937876 39872284 168807949 483414061 857992142 186663321 534348501 217269157 316343716 758359268 821322493 367151649 900111252 70000107 958182148 837969045 44345183 819930043 327032391 998311217 170412894 475034526 437538459 828782711 844988125 619564103 230197414 586810420 486752546 955530825 892106966 154166112 582440284 491829637 317993235 415409570 427947130 868094292 860093631 349052109 651245091 680494234 572452967 509589414 260937738 404182524 958720683 897930112 972794759 259486766 584998587 789223328 811989911 11678785 240637994 911194807 651149442 145851041 130454100 567149170 887342140 155310419 753478118 373509047 136717908 720313239 105708653 500827286 104879455 822547106 600461407 891252875 695562633 660711950 153158127 183427479 226175798 981732344 897593260 694985621 50135132 987070172 189559927 153610821 2082035 268156566 19368321 308490408 228822967 271919956 573165006 529534845 591893805 815837532 154271299 874310992 249592609 396801810 732046946 131705802 473460315 895855889 703828330 522410341 852976286 865570977 673616929 708691915 201631320 488068140 489608282 452597508 602153690 241944603 12092727 434325730 496593344 627761468 195770782 67562835 981209512 665989953 565873374 695079085 494330560 226056879 363527413 424404247 417017168 648930890 200548501 10677251 942352333 271354218 904423716 409663006 308432481 877516423 982130704 937989246 189575006 57170172 157215409 322552936 120321094 590307883 659979768 491059383 494021267 685054182 326808636 242662879 298991915 985460411 570950737 49694613 589043273 198866433 92443653 751163120 641137400 70163994 669029773 574177718 912727569 259587198 797430257 763404642 870555891 821352537 229704391 899484762 664272090 819693053 822980440 755064744 77313884 61951225 506651514 93365338 530880992 195571502 566454264 499290487 980619713 325794633 887769579 856791215 509169056 70409968 155043419 460064329 905255827 612824378 336322569 135976905 809510041 49415205 958939645 400271391 231456226 543763581 927799561 889359504 96920889 887811340 369124118 625267493 717869858 262484644 858189449 384627450 193506982 96029094 847612246 285318152 808000912 71341962 354850152 65957248 87657788 433242580 749702172 5931299 519399907 333404967 906420571 469113504 928380867 636019788 640280417 823350944 624381220 25124938 68365165 120763750 71792105 608234359 255320465 8797734 959987694 820319880 545866369 48820844 345559470 235142004 324135259 412438647 369385790 589508234 290901029 221879140 456856422 188627905 865252924 726521331 758600158 354778567 864030295 301202684 343755322 908500936 959138283 689536344 95904986 648460247 560127222 33088594 786104479 830637177 183099182 909325074 591778206 238140870 539273998 413339595 92682600 908830994 343146268 121058838 995979438 187600936 351202714 969309993 779090253 330575204 196857592 841679297 963390923 71914266 368265174 217248698 76702304 958448730 254129117 380967798 414785825 999771198 369378665 865948797 968047993 744666215 749776504 594874437 360501946 699519358 46432786 830951819 302625754 775812975 709903186 328346221 275411830 570407640 518924068 423402295 771998026 633674910 615776021 794715731 918983545 688300700 933136638 117959316 121610323 848339233 139078101 137264176 958154155 440435855 390159350 26109873 404623323 109566176 803099060 959530366 857173192 950274752 155353900 763416173 23767650 980044650 81739185 132543581 846113119 178042318 653674382 870291962 595422715 389688137 26132088 479519666 859893929 428787684 310939559 140617657 599260235 815625260 840745292 20724887 263037936 908598540 208734652 160668055 243139511 492322172 749092260 768145742 557859556 154590303 14712545 807949107 96741375 812771037 992475033 733702778 294072949 299692486 723714086 81238353 249336086 202499302 923350597 125515086 237930471 171438668 765662307 33669458 980804704 527926540 72532748 803931437 287099810 974552877 960171084 763507750 598986072 628335883 394329955 808014161 823548741 71971185 731120941 815824735 43036816 25176365 523932313 388711859 233968841 153297656 863569464 375239169 571315918 983660351 45878378 778701816 323264627 279283488 149322835 515050379 154081008 225337650 209009902 456354673 360429762 619166386 690983088 83288671 359387639 470643624 227329647 273474480 376177894 699038646 837338527 984426613 190763799 127229912 690626787 40931819 456293502 611730400 341610842 413508816 785345898 885748307 796337400 535700943 148199411 969120370 809999046 22930328 563177586 226461398 439299683 650815065 42046378 314512972 844663713 620426398 806766098 296394266 804499785 315234331 349468560 174646144 521351211 376266499 620891311 868532389 721854940 277329902 106091849 949614415 180305238 58062707 988139385 840681747 768335495 322217457 504930180 723671244 614733610 866687732 195575240 184674136 402217300 138260235 860334711 414029356 440526041 553868310 58716293 243057380 76269632 739531723 456471960 109856305 349383581 91171325 794935580 462860132 774846760 991616219 251694716 696047728 567489978 256574934 374960489 749242297 48698184 870128954 370950120 513046633 895285357 280702003 67180486 528171802 737103650 874642249 16066028 693369251 134681814 778583076 867296578 80266630 508757698 575109067 216068566 71784888 915749849 973399117 23799729 592060620 750223321 600739368 980802011 311663321 440263544 683263910 334553016 455723415 443099553 267805886 499142597 378434543 358383866 753492791 263891804 116029796 282394483 809945514 514404923 752488994 508795031 307628622 81150325 969402437 981616736 740849012 893337020 124804966 239730795 311182198 677228124 70618105 668125340 172650144 613677893 127854326 80626183 804546544 268610633 400542151 153024781 72090107 139277253 664741332 613441042 37386137 163299105 157116730 885174482 645360816 524667546 787417042 830176203 455725741 708333152 900745461 258127255 494066014 338624786 12777231 84715411 989709202 425060749 98251704 6345098 539829735 656578535 370556959 655832319 388190441 725387489 819135684 679251752 680833213 587390189 40267278 78006582 795570003 297473593 998859045 434459519 124572333 399739076 642125086 776964454 688256262 885065941 427526166 949986734 755139773 799947107 597561077 272800826 816921603 971930916 890107367 396339019 56613973 545843611 32585675 426395005 551683443 334237072 86289969 50861140 748826924 302045497 766036789 268844081 84347616 511233782 971879160 924611085 409233145 236784285 917773372 590482984 730611382 345240986 668076553 711144427 577835717 750792942 341214819 152457977 450791643 669942018 252731720 758129614 300566488 947201974 323222147 156460596 890795403 941545444 911234633 708115777 957967819 517076167 599987773 39903163 134999078 289286205 82979982 108279541 589340626 756213636 797768061 847173980 827837129 983559854 123631725 614665840 14684437 794622755 188607131 137823436 883653979 193593620 532007912 310313755 339730137 805063682 901542198 258760421 825844150 89220658 850909133 262401728 524532239 626366433 272099732 813604001 956997769 953400334 308261279 429919436 257491620 636985457 309442247 602502007 199639672 372963543 27087010 134760900 441855703 260412612 398402035 815272637 792384683 965727714 584413827 642420659 693194995 890227909 452592837 814698019 24598940 821161288 466709404 684148036 567828653 266924690 370028482 138254802 911360423 712175811 749808484 56867957 518730874 603422052 826738988 894829622 20824299 485495760 569743998 792160440 726232432 653649432 177018835 138114351 402153200 347665388 23652487 257056908 682014715 106826529 20006458 312606258 142730978 6161451 157296734 218578924 967187025 703823912 486622111 249082133 123762846 128627779 941641 818257774 937944757 432114284 784858448 400955732 845954820 896958202 940958867 996204292 766757160 692639414 289027529 637745426 626763221 152146261 368114895 356619144 996839396 354354095 931160284 723982394 679166378 75610852 903603344 170594289 142679896 827196734 975370773 906576535 190741072 428704658 911662394 928701899 448742563 757910939 279770727 823558761 446253535 322960173 772105171 35471826 538032639 281435886 389308765 811581701 98456446 716714058 685535707 590724251 87704954 332453470 958860833 245098697 197880137 748139058 87127096 758590574 389890799 76760615 508649555 474716248 747026102 468331236 435089315 908524889 942667460 601821740 928074468 405462805 715990576 638035178 52552301 594546995 959633461 871143562 967217569 232729579 521487813 396296090 829756491 320628181 105401761 674237854 152862456 731853011 91532605 25215509 537175124 873244351 908827709 491632518 278953392 303148623 446137501 427758880 702027688 888292120 987429357 479227417 504757596 147065909 317264083 638431951 967367651 35074760 944555738 526524940 598566591 160545069 916845267 397006598 226823766 969341001 734205883 527078196 407702763 191652307 781323028 448271864 560736108 680795908 75610376 939304501 445539977 566631045 305969940 919828065 59246185 199739081 882742665 881301912 789832311 799594114 43105810 949947732 112943885 629562460 619735442 83169017 330713545 591889291 664554805 45241170 169805016 724577653 654216421 20094543 343913046 49189675 732357190 884176726 371707822 909508301 240429126 790122297 186623278 170007368 93275391 430094417 764777128 51711666 11880347 836215372 256605333 275163548 874444593 602001983 232922253 891980120 751415178 987388169 896788398 573812268 942777466 963700683 793872942 350286223 884671366 704722693 554726621 577865104 414612076 690345209 246649282 217518532 194134380 861800077 755220340 739344529 638482651 478626160 453273854 466430052 422252277 770389546 524627316 904428896 125556335 317741535 354188722 540895175 17071465 668383099 642872733 994911473 52259337 588223878 682330413 424614913 137795454 901632695 878216119 369256322 824927187 211326011 27406057 476904767 515617524 82234359 501136862 237659365 53451839 83497773 682300632 377751961 800665234 231154338 262259356 899234051 343061486 172438799 175567643 586060631 577343183 29319602 427503032 221163913 583585817 760429994 789670707 258128950 233321894 139813515 548649553 125542882 402995181 471019922 797379635 395638970 329228523 653288224 343094541 560194158 577449431 78169238 238438628 27163460 389001504 505999983 338976209 905956546 1153341 302814814 916450674 606560575 328885532 871930571 503779827 941295943 909981720 47249339 732106464 219957573 74999224 167787538 174596258 996178479 956731311 657968215 692885161 311720487 171019475 475998776 483750430 333564340 437472273 89957923 245671192 765506506 366255330 255415452 102805314 487224089 625782554 596321050 736357550 803543310 872551280 667442341 488627168 512424264 219238685 143746797 504734655 399025688 469174909 118285748 640973283 108727134 650009451 521651833 534926744 524245752 336953099 529254808 477916698 474817434 861361900 154134229 683477431 726859150 174412956 729050658 612012301 518551132 309875172 326664262 802632462 574800100 373795285 378083965 583948796 699829700 268249377 555571526 404509720 456074448 162149805 230251312 184514107 819772989 250543750 976532637 511656921 160413947 739273388 247389885 336099606 913243257 110498875 132304170 633111692 661152528 300633640 873417356 913988550 794291781 150854346 392709343 871865448 453699610 689467125 601538527 585138670 932409538 917991846 470883612 429483156 376905258 573954890 695826820 88498653 394474168 616424875 534853734 441163538 839929029 110376139 844881191 792654469 584946208 577538568 114323731 126970799 707049722 305997582 368875291 879933345 843905503 3387331 60510346 890677036 653119906 264599965 403772821 861736473 559749306 343871146 833690053 4159567 336947628 588329929 67369804 711541842 72061608 192889082 337860677 885610467 250441439 638732040 171964429 377579207 279384547 971417349 990133127 467363662 834818598 622262861 592609152 400368605 705218758 60967948 109625211 752489952 639385759 976235796 834519224 596155216 435036209 308871881 201014068 423378749 932802785 913450170 522883398 352531692 775646098 436207484 849416207 290743931 961509288 449046518 319773639 166031603 408057712 989243224 232906998 731984876 221052946 966560982 205205966 591009334 57076724 88476455 247223905 457392857 314398732 510531460 658163667 217077833 261150082 404837166 581656359 630945847 37666917 369269779 130204453 311008761 673365002 440566058 444881895 210913272 599311459 875894022 638557819 361956465 675438647 750546265 84904798 691695943 19092139 620953677 710566275 541564736 484491905 465125938 766459903 536882746 810350874 69265554 822593106 959209753 137960353 834232477 691316928 749382511 562839855 785909761 534924759 949788408 839395628 458283210 25039700 823801661 88304126 532528965 286035527 941272063 997889430 185946887 47462913 200884588 277824062 960475342 291252271 393596312 567978524 593369311 480682697 736604321 238907113 958507326 92352131 903989681 862444292 958139568 962275130 759179381 743411285 21021859 158420516 412848130 676067075 366795592 271432149 624007355 504339259 698034009 589059073 967018542 722742521 972760151 698697349 597007269 325664130 139525928 574209168 372875622 960544646 636431979 870280627 359182482 520763377 723913229 333353320 288374444 747623741 376982206 612149640 374397809 796970556 525944797 822467023 159539618 676556990 269102239 330208837 147563482 737458962 505648516 598088240 630542813 470719640 606728141 568446636 310619925 619860663 964845590 175435423 627891599 649743689 327229150 381795902 580745396 535181569 850282916 282019067 706603383 112969710 62268344 182317826 989258225 429235693 159732675 310518322 39933738 935563669 1451899 768077387 79177477 939345832 944992298 981590536 859728722 171788467 581925858 861873901 394542330 744379870 732776841 838498994 581409516 793968060 511350515 964287031 234797611 238999902 586705973 888698375 841710764 915090501 42291650 426372857 37998611 635570958 511282679 408478952 455552474 508731583 592703796 624572580 274251942 329524545 667482140 760652319 632792928 825901220 553345889 945888238 32391356 404364133 513512008 550267060 608733401 710947353 682922111 759786722 898173322 905244338 783586944 846176182 691980556 417185117 900028429 820862617 407660346 996204893 364748382 459729287 863950118 806330001 159809137 214186013 293653910 425592804 99634516 208745741 296959359 202899487 28446459 355010639 581646679 873757567 763688294 998677369 997827996 324813827 454235752 870805615 917622083 293356798 229979381 410343189 517161138 645582403 40490381 263877194 210007274 690433527 705573925 374002746 815068203 737208886 397148973 110236915 463548587 672340141 285147599 241771816 111561520 970835565 721536483 668082119 402955381 437802336 493354648 954416898 89161043 523455787 918204257 227288893 134082195 698498316 913571815 801718852 42380826 885021284 828115365 235974918 33201406 820367116 88269479 308261726 977249946 886570744 117490724 851583076 174242400 699390671 817483841 38794935 5875598 668873920 537815779 656617143 839909001 513851163 701945629 214064530 398600188 332069050 80462929 928146817 393182729 920348670 974257905 778387342 408489379 539271951 811926681 205706595 416448445 28261049 669646146 808363437 903546362 337467273 903627638 40211062 921182855 345611707 353689094 945931040 311139540 510942352 59171883 413134961 565279649 254437556 298354336 170418698 521809457 783001235 46089876 696723301 251878847 430805277 893678903 977718564 723899914 824735359 498006498 678883757 560407740 895662408 281174531 283152118 520881794 452876522 221695727 863223564 825006449 355474414 599646146 225937203 896662663 620889978 467079009 497734784 478276154 879232587 139442851 26598149 258727043 128599511 958350082 340191818 257643957 895201783 775737391 979106097 953050032 384959410 901806376 569460375 606165734 118079699 110463141 207287570 530754515 339255438 45458678 899307385 30570257 816138977 778270674 86913736 351991042 610903457 261195158 157577137 10162517 691874863 165023035 183587643 750984160 86941079 613447224 25152843 540843115 661724633 204988662 46136778 947237730 405915177 175661712 203339562 202189930 483623428 267323158 84664951 876878706 554434261 403455979 117696088 781984509 608879526 181864863 203380057 77798089 351441534 761704509 35877844 282094636 927860046 941169695 119648904 307273412 112079612 262158440 880124910 939767613 398247646 713673986 982921805 340060665 306098239 327650984 655885327 121495884 38798159 471328079 937500888 420017639 439904659 877024859 92185974 779796833 743689882 54680582 753025028 718699788 549493965 131906306 544175033 225373272 885589698 43967022 328933032 137762425 75363128 74325066 418205115 521244476 116224459 464181137 968285003 380232801 552708033 577745029 972960862 704468346 872735295 613415909 721354115 118393377 398121503 102264757 457877316 536304350 227883347 206410083 604147845 123376685 783515641 28922901 724068107 730754765 310216083 591147397 671103930 109830970 626883526 895369017 647207801 846966754 265741368 177699818 620206000 378096071 201028885 470613342 400727746 876439302 554738543 31257705 660903627 361082816 572301427 443101404 251252802 426054806 800614502 198201712 14649338 258675471 283118 256664161 190040120 529279676 160566841 740590552 951044517 731778712 309194044 222734653 146781229 483038743 432392858 712028192 808988164 790898728 133623626 461768045 580053434 477644434 280452228 945125731 909709606 958668168 175381604 789402420 374833391 535445728 299904190 437548855 618784132 306706263 583463548 125999726 466837684 75951587 893676059 990935059 627442665 356485782 890091963 421715814 168102652 780720444 261916450 200782917 919558846 103159338 517342422 150481427 950943660 347081925 378635912 422782611 471633317 414686966 447367620 484428441 897586077 948287087 302466924 449978672 134300030 90386638 624930546 661377998 836387819 489862621 865712740 245599875 487954967 493142015 167732523 996919042 982734594 108561591 990647594 473167105 287399810 417394911 38437255 794344888 118523459 137927778 479279239 409352725 108011401 714402841 819689085 275909519 934938844 126784141 774882399 517512320 64707289 252204875 363386898 26626610 804505472 965195037 564295824 609237189 208035642 387781402 436854261 94935290 847396884 427299116 863056470 315313731 698650388 649814528 695044598 482684675 796406318 251224483 514157290 801460025 826407600 623680428 952653565 769730898 318991510 481457607 371385223 456500938 499570659 148304992 432789250 930534875 63970218 85736559 396020936 18659510 649541504 311806857 516092038 641726279 26159562 649314579 601423033 971458693 803500563 542832275 936134023 298501560 683434126 312504439 853447367 751054763 708606926 695439177 912546411 350562253 35213042 799683455 608418348 976316537 669930519 621217635 122725562 109186971 33435445 100007482 137275051 979869648 410336608 337697680 529238455 253906059 242047191 996880416 286263781 770675681 236967883 117299991 956658440 891521503 483784203 498357474 348520461 223081780 290281976 709425791 332403929 464218022 934109530 667701081 326755483 432576651 286049041 865870483 735739663 791830882 266229026 970466944 487974163 510251492 129169563 404310316 705213114 948882140 17901000 909383437 629339478 933061403 304241966 495956584 894633179 84855374 918028616 800254134 996350605 90148364 924886321 54855785 751848244 380873060 620859757 106997097 296674400 535843649 245322798 280574396 607315627 127177910 145453035 520742901 970036049 339491997 926116701 651523355 753130920 854374804 416078878 351955562 423678503 967604948 202861955 551397851 618857767 535548311 217105436 125016385 401294624 132660358 496307786 740985414 255528932 5784106 756361975 15530915 313591741 223940330 30048348 821339324 853479651 818323858 628140671 253359086 635820591 417691866 894499346 347767005 244071578 867200789 305478823 368056437 277964949 625682928 724721039 439517176 728195245 683297165 532824510 85242590 427487272 150477326 852369520 839346605 702495564 591782498 899849445 100424915 279613890 902009547 226791679 483627213 221865351 631713303 666037366 128514249 518492660 838438655 635596561 754345798 78167313 170921184 560893713 457872213 379684883 440269872 877724957 626972501 294916044 799937956 949709909 333563339 717048806 149114164 742347040 762430510 691523797 731331264 218928286 916428824 295652031 370034967 914406837 861694390 846471810 538832311 945754103 425094020 341756871 261239719 381228987 236309299 973917658 446117052 852666002 92846777 833052786 625356135 269663346 570647302 623900325 518375391 528284417 522219617 625943835 168806473 931867382 870648492 247682364 913070496 298986128 360392215 947426389 291680514 535414985 33316069 700397722 463676970 662289901 55580714 29157296 837318403 41696006 548600529 121083210 480251670 347767769 145133972 907400957 798251221 570648267 142472947 224674774 933692516 818661116 35164861 137413622 679301964 412117857 300743990 619079338 360631175 406941024 561472410 861556099 604499413 597224900 735361736 712474529 69591152 543402836 613966256 60126861 205035005 576735743 177131760 303964864 177446107 114781993 425177831 905617243 643080766 940354663 389494601 738697977 80272482 473004712 657529364 556426436 476817407 901776143 498978694 383781217 839776740 840869550 616245909 668303043 143655826 128599592 527143882 653941305 724820019 638445867 281716696 262918006 427608843 711146001 554580260 135197691 740087385 86137164 991806031 432826662 441586445 802844529 657485549 623474685 368403155 576445794 345784304 480183834 799254393 266506435 534691056 622515207 703411252 942507083 888344331 394532032 967483487 289692343 956780879 346113870 344622443 203217042 879684827 185528495 372682810 8248194 100189245 720964543 216393411 44042570 501563420 157661463 970325239 380799743 667274291 256056383 605148958 434452547 680348579 636492074 20260874 643839877 245459928 471135702 468470169 429285176 227365207 408362821 399988871 512230255 393985821 11564068 608926558 570496051 432355049 993834431 963731181 11456638 311105209 773447747 813734130 318036401 318312017 94839191 523567554 187459362 106715050 996708002 590474014 791060244 315806579 670707536 191941374 354020639 10939883 726978965 42302766 66888086 779489681 814514920 275811112 397795386 454930104 10974969 999513873 614155886 839148555 319774849 964396548 607490535 779486971 185822459 601434351 8021780 57549423 766868063 612011636 881300895 736297276 740040547 809279178 492157613 621031302 903108170 53106967 78426156 828991810 565827710 253573681 561738396 105191005 130501082 666390704 592529664 402883604 793221292 607319596 79552928 824731453 306235257 877716142 988605033 220752645 599939175 57087781 253412458 432445031 688557310 380046928 324608470 417286474 976260424 507890691 527691110 755836842 337641113 484258651 226707411 428911778 820388339 162369623 151612562 942485888 322625437 991608332 575813476 334852639 360132723 972934586 366611508 421963716 923031370 967165711 756409828 432815337 452210330 410579084 672651202 733716097 813341235 955551473 770284066 968920531 722418013 16018934 696554649 135026396 659055519 430391223 759129111 7962192 291485119 881028233 434338652 101018342 240568704 93807409 618706477 111163548 761902277 880853158 410002839 585013991 225473580 126400826 157769925 383431035 426299501 453671264 752507041 362278261 592475548 532956435 362703030 598841267 754966971 696048703 248314505 414277756 966491482 891151071 680109195 843104833 799810856 557937936 335366926 268943446 619440304 304857597 487235371 410878227 938978284 482375841 613827471 921794854 827670553 661555018 544392829 328389326 865795817 75769097 494100889 150540717 245186082 890178410 119296227 272456178 646014971 80795734 670716230 255012839 813713936 675271009 74505287 930324220 364856866 576945946 918338512 94246525 911782466 405750737 930906446 673682083 900958527 319910439 313790319 620776586 699168148 920739533 245371762 925611691 830912308 152137848 151836452 852900833 666519495 183475052 534928518 275090976 553244131 687394033 758377362 175376481 841880687 846085561 135520801 171605943 51799028 225805005 874747824 440959906 444442006 577608136 18716968 547699090 791995884 137261483 444502777 145666 205363044 893381203 970915137 824970537 575714783 732594204 688904899 167891335 373750452 579354461 654670418 552281679 335368275 271756193 858577740 735590358 507701123 351358376 319314599 196364200 101678762 746636811 845088184 362430713 921834378 396226759 113144114 78837309 782019082 448130540 107908805 237851659 867433817 120730288 550836702 506830561 7874410 967167417 165649591 751513607 775900134 867508438 163077346 77738571 241646481 937436011 483615628 847827495 221144701 910957512 284728798 267299520 356078466 83270508 3890675 402613961 1010045 907007286 651284762 839358811 852703120 580992104 170571591 552177522 651343899 484295149 88306218 959308303 937802541 887935846 59611375 1145562 64893872 853688533 355526868 391542459 737099804 667667975 560823717 698525655 657477677 408561797 239741642 734640295 468128339 957794979 393869605 234772688 798495951 166762982 710560567 738455116 911133283 206744678 636372171 80271838 924671541 464555624 745583653 864799264 62392876 742812394 758875161 154928366 733411919 183247723 756525360 459418634 130904824 774054812 658037192 142812995 639684156 284950530 230417275 865829379 409759830 62033359 700781481 560042825 825120633 266595844 432288219 152144488 610242792 419835233 82319640 439552231 351731619 257803061 59246660 242658820 551194210 8080484 30224545 655476898 646718493 564617810 769810876 300619540 249038332 124000781 457953118 514227492 307188874 460045107 134164491 490638955 683586961 601213509 786311296 541360764 243308637 716205144 884431074 423847897 209101374 209957202 853915950 837871727 102625184 734135984 659814689 990418054 425668656 790890038 23668548 65976178 940566296 750795168 200487450 387414001 826147762 782978991 770741837 602247465 893402082 837103649 954377834 527267553 198129681 426981123 641137023 939914142 329610950 718246903 760169220 139910388 146007265 30685625 318751748 468744089 181810785 806633234 922784348 153997077 96763303 212945005 265571715 550789480 103449969 556650524 204007120 547681795 467437369 514185589 269988513 62920918 316106472 953917189 71291023 341249859 422744717 996148561 887619698 852545290 918174007 748148439 153862307 619980987 490986279 342382702 738672144 784071534 505459852 364343756 175254579 632559871 988766097 698968618 709166987 24699108 958686194 762875514 705543583 88405722 616682543 490233086 657220774 87592830 723161368 206058908 747214915 748258242 267306754 315715966 454943247 440130697 840835268 379551422 968074984 645541052 718980184 655366599 819895785 648352252 940578503 439623454 679447596 480231336 841316877 6482662 322167051 968870052 128515026 666935759 757088710 807913137 265207622 1744914 578138465 796762360 749054158 48683679 663214681 349910537 481294353 347801993 155348197 323885695 632327512 458385012 422622850 139119143 85993680 68592150 917030695 319766264 243444260 377032354 20129510 137537124 916322218 376451551 189121776 702224288 113717224 202472080 507597562 38063977 11406208 234834193 866685988 354314928 600321847 714350216 870944844 519708914 711364947 178683248 422412744 132392392 548340770 514122145 586401918 417255793 322826439 565477143 344856053 694739045 764090780 705137945 526058893 344189475 524337127 472007267 366208051 393218548 464893194 754103614 552678581 158632986 903664188 902325465 342065723 707709454 861502020 983356709 74909719 66598864 549524330 475512093 430982875 515906272 784498895 490167662 992597963 752001537 70702235 610839535 130936123 947612922 49706089 987068327 530394231 482662833 946248714 713407844 655583436 532607713 495589210 279543950 439793678 545512562 661175123 244569906 710752666 635048109 915459482 163248244 822561400 933063386 638823321 60072325 12722397 857196707 56706486 915467983 587807127 678227701 71845033 524498617 208782497 493645105 167255352 589642691 547506152 400699465 515971208 430544469 88183688 354449611 633547438 373004923 860721243 724732848 504933709 547749022 455819721 273053835 546152715 654157826 436395004 707037666 159282326 522537157 516190618 492150600 919491305 308170995 836755972 388969196 94450831 453935460 948259935 404459087 171767147 994602198 302537949 602462616 543986990 822145033 812630551 341791510 42843438 943228622 993471834 848505218 113752118 702413195 985816481 898556157 220012804 20910162 297414558 554404706 319854079 422098898 468997128 955362445 600345483 868268892 576493829 583948872 12555165 699795947 314856430 148010538 505513925 215895937 54440290 607412030 924524960 992199279 20588470 332631969 367648256 959782814 712463570 630323829 395625347 396055474 101797593 359704481 674632720 988225094 879931608 407630612 157874806 953061906 30769793 279017313 746325319 812025170 243799302 537439992 745870693 128503497 918534066 514846793 719655799 142890568 591320074 907278117 168192442 699660905 837624579 19600594 675184084 983650607 253579150 163116270 916259883 957811483 986282372 198285644 3281346 181052672 449543174 741635987 278886888 931757938 728191068 363512533 132220893 945376902 559323443 595936954 642110890 881975445 765358994 529318354 229003670 811844336 471964247 523147685 53582891 539973243 449213148 620682772 854242643 434924525 890761441 958878657 148021459 774413591 932804161 971423909 165000710 147842545 592411636 237228082 862578449 252537046 704822093 911784851 274927547 326236524 113860758 10247733 385466321 44267849 597562298 140986057 930286298 115191091 285227805 578926924 198675421 221277877 594346351 30564276 658479712 727057198 843083478 382813422 357906724 546083608 28182950 312441054 980965798 475004818 765067206 923739793 84691422 279877040 386872069 550506502 928026936 450595892 979034690 54120829 729004168 399040184 678113978 175129036 280910011 200482734 221716407 734460010 221066022 376975262 244822306 279977262 230813117 696380439 771606340 223887752 173687859 789941763 727589286 163791457 110790545 97675418 858870337 965759834 165495602 183706761 677346523 345736281 153405906 957704426 594196352 977045150 133228176 791609690 698528414 315576989 345884213 344698002 540663766 958991538 841239273 747587327 545712199 786797078 354995010 529920450 459133289 722546732 873308747 523867389 272759974 451697938 957292857 777243440 811046431 836061209 352771418 617574123 633766900 271075005 837756673 403807438 478524855 690801150 360609289 184819614 224869438 421476172 335478585 78365785 551975195 358641313 447585197 839441400 897846545 881074403 903255181 311066296 848453947 135625691 47959605 655675158 212937768 79583260 183743853 360165841 90109940 18739115 546006608 983697475 264802084 334123577 707938721 491046512 122195599 385383962 579991786 177440173 571935326 705509587 608973332 177696837 985626492 737916152 368143520 412252033 452707269 999804228 66126733 307068817 636640074 861230932 440783461 549386489 149126245 758413256 189611457 389596832 875817537 792752274 948271261 109729390 931294841 828045534 963509145 992749240 87430776 619264076 500386160 82671761 883235100 561615437 855269743 814989958 36757920 707637644 846698897 954659579 914535471 846520666 265476588 918279102 224339255 215189568 621084969 356226632 206095938 611560238 327134301 199104095 717362010 434999536 157762778 867776563 594910987 767981670 855107824 476837952 857131524 425496443 64690081 944728613 492426408 690214321 244743648 373534448 11113523 477091261 877324413 951255978 418038180 330405183 771562925 215530071 656894086 938828421 214156912 416856715 235487080 810587006 814044024 239693995 399937986 9607946 48312494 286501834 34679286 10640455 302322658 802659166 514642610 919466456 859364549 888385894 9830298 820261105 550118899 851206043 5078955 580102672 665822496 530633872 272122415 402174844 262532384 219658945 805181745 556911163 466195324 124522174 320632071 222881720 739979927 506234980 394885036 116247909 864288371 296850290 44009691 64779588 265713347 832106609 911682506 302133051 76467499 808825187 270416783 308210284 330396797 198883398 803576747 439165885 600540205 938296146 907033676 226288945 32440921 746412804 44330217 218183961 438742003 446441878 961398075 645141010 17482400 325012320 248895485 751164753 240600335 197214288 822298100 606305232 634837177 307216201 153770945 966350298 725707613 232659298 211196551 344025253 591482092 686262829 309429695 745720688 853608437 267029993 767856798 619609593 347096333 565629367 131598954 241590405 138372503 463618888 139830363 985529538 363954174 507082229 97390576 957850506 996456716 855138786 463610708 610059401 230044383 713134043 927887380 711457674 792109026 513986572 16413663 807805141 201307063 859633302 936350017 341982358 386451806 70958562 228351822 985412131 9495778 189031824 505337077 553883170 859720398 441763 614983209 411879684 154154336 399905079 570227288 986739412 884840891 10273434 653194801 326129143 693284308 327096580 619237088 599542690 375778567 631203950 733779940 500797357 453405279 789703111 799907493 326520755 932770620 355026902 817185037 193449175 589288771 225623475 139313394 803983329 963909767 98963052 665713235 745082661 343648006 392558163 780009866 848964800 666990060 654855513 115092411 893189745 745052405 600828846 687498791 246235702 991651620 733855553 226181622 69848793 677307119 165671119 718011366 180742174 704083752 825480648 160781962 918345046 424475601 543290986 316480754 689773676 520448736 317634291 249893194 782428189 493815982 158041411 974210624 314444883 779042736 430452106 792469343 412662561 760857558 988676825 901248392 617580495 819908018 380136446 770282305 629243300 691489396 71744073 745653645 577578720 25606477 415200262 683627880 163289954 667756226 479669382 708068618 538022610 757087237 256209666 922632359 678179169 659013389 66792935 432395919 269758418 77357989 866546817 912109733 417868871 241046381 924900028 152984613 857694818 422947719 658511398 961913705 963089795 748560462 903285494 724762486 59285668 596043928 165754983 492540449 182311968 277441617 754052040 663275394 384219101 741055572 147000956 8194950 809650596 800589134 808240997 610868978 338080989 250156461 953388152 858712004 656156903 598228672 416589467 22185331 17806577 643305018 809408003 644986886 867999340 734080931 923825383 643801438 883543410 44360518 945912090 916451149 986524137 60488163 486424018 454533738 847065241 301990861 697907691 608531334 860457758 10941465 296220377 780166344 427165449 169038614 156478989 438515187 127329205 282321244 975403091 563558165 833054738 980595273 278078260 769665801 339161020 873990821 87002836 879430384 386149555 977691531 30870267 652597945 626593261 518617536 42503298 132981383 764604406 712852503 385568389 440482273 820435734 249945008 529531696 510284297 67361288 636588370 931913533 839408904 936364308 379246093 152332037 127880505 18690578 372125303 565009588 498764059 363745478 912379000 239215492 89104845 614710328 143229900 410612171 886990425 601728437 529065798 510380470 174288111 134796830 410194907 90340037 319590362 731398056 416507098 48711393 493724322 227813172 705923790 121420120 484920040 221809571 156890907 661885534 645006525 369685324 247947795 834831362 805011941 188434249 294493788 591088116 111155098 236131054 961771365 462968631 168179084 388543458 519696671 549778832 273203235 773331655 733493087 847883533 581801587 890949248 871655864 188990154 502775658 38906022 26672507 304103825 153229751 496665781 360528507 743497595 854877045 652614517 356801644 228632406 339658022 560008214 382583589 914980789 589407606 230640989 299046726 425531803 76229594 855233309 228678538 977406479 551814603 110583928 121295690 379767760 481794567 746094812 314665671 575660178 830748605 796757023 834556317 884734174 87858363 395488612 767385153 388494778 634905136 185933934 106034624 841531293 508241157 118811482 727091287 773696187 654988624 551805345 260881563 394666684 224863462 161210837 632742449 720274219 113196645 614621128 440121467 787322460 465464752 768043163 223380087 475915509 96339820 91815030 916448234 866260940 531216922 894359202 440317395 705772510 17447372 384900937 371632826 36370498 554120647 113957174 455780469 879986140 678496438 607637910 435569842 22433599 885715896 883315441 297703243 264379985 288478663 206218135 289948582 919769568 246164111 221141869 855772692 297002769 962322922 969976017 430778163 58436225 806417607 214304664 171544690 333834423 397943500 150787742 933994173 473657527 747152129 63418596 242962313 369485157 600616121 586489829 777561075 88892540 188304318 584577106 109101262 855359613 82733405 712284971 729308305 247549730 160380761 573865602 246976521 261239575 264065999 981122669 709393138 22529952 72894276 43393420 10415267 336030345 220004395 929092156 79176368 381219483 101345965 299070871 630177237 426265507 595335565 17614178 793827652 231782795 706235361 226315890 957972680 547415152 268762362 51654691 592293038 757857943 944782262 679914646 964812536 399493163 616663930 778901484 749473110 5491780 588774312 258369240 767728501 632266844 351459760 408884496 310220160 820598075 533097459 183814582 765392309 999550354 137384844 769666946 667078666 787725208 484724805 982317335 204314780 760633029 297469318 960230701 998984543 694428615 824706148 444146150 828215085 138210285 470383366 17664551 458145676 578938669 98192634 292606535 539529896 81532154 929319402 239457147 290958385 506122468 199728306 328782409 896125273 466309214 260683450 746576690 858363907 701313211 397026031 663367574 303447474 191517200 475414350 102288345 580570266 28230847 891238094 299806054 313910233 487755986 646943767 568047697 492082400 807087860 774397440 450982606 404168994 441887073 728862623 605489285 271130771 120719843 666351814 81024302 645122571 665295774 590047856 752137486 504173469 951423011 639350207 240467378 504097102 976759783 199784371 827897074 367062555 311463098 101196313 829093688 635993700 393105614 595963410 100248579 433372257 121680923 510899403 906841566 546787618 662388998 547854871 878799942 401538144 213656550 486710577 474766926 844532752 399271281 530697263 215681206 594783684 119682489 776840902 422414585 248959846 821785131 623311662 581004859 526320925 204512085 511596658 586413051 384698484 176200332 975903611 851976669 351641279 808599751 859207902 791987588 311442404 195727666 347657381 62570843 302735341 74563866 950967088 643834797 753370420 222759302 602694491 885571558 395808853 556609066 933228203 651699747 546305602 413302449 482961231 939406060 814059345 245263249 97461393 593050870 126407852 343742075 65395549 939243795 620509134 473651526 972170049 746979838 375030029 288885475 460239599 995619750 906911904 635655624 421586404 93599559 390390635 548428396 888646718 162336168 130043622 774430211 934893115 360643087 328757023 26385624 571317698 735579135 726759623 58318437 250465046 318928272 932966435 167169546 541644170 127941444 342880491 536970488 894154683 800462926 654370449 243693322 135918054 321924046 992447328 254083713 666387947 787109679 273372083 80549445 221359364 785783929 609656223 346568712 808678440 929324739 298718784 901235343 299475713 243924296 770356102 194976735 518501416 829969700 825034380 757669639 323306563 414622171 325517015 304556619 874570532 294082135 399192902 18277037 274787701 441131593 37126284 615575702 430082213 246348643 232541637 822085903 508334902 333969476 160145938 94368638 949337419 518822643 856247264 395526562 771033150 699635023 870172456 288816470 929922771 244225055 232905304 682018988 454704816 315194257 862583865 673068206 286204261 900898678 718857669 875913372 143886324 527863643 360050116 869036885 405583963 463323499 518990940 707831385 747955558 446849775 537905242 433534347 466437114 509723442 350986337 491898450 404352199 929283516 452552055 103833978 114665242 290114679 375864277 672397045 324985407 492989985 999833793 894968140 673506409 411835744 335073827 534982436 933148298 712072579 651537904 602340073 816808302 380341970 867071066 469078029 593928348 630504490 578796331 873932373 634989155 353944548 999048955 169092428 973919614 217387084 71192666 175798249 614019792 657446422 529711718 387877545 463128243 726088845 58984278 808155876 451841903 164894707 485277417 796878960 286404039 305826865 856856252 582544602 660504299 218900155 153039367 450932839 469736653 794029776 890920205 704568558 347050095 400650730 919858882 791921152 946785678 927154596 454948544 562134829 492319767 614663332 839831528 100141826 790604572 593968647 47659754 299785185 466854151 644202075 126722204 169672680 230439820 721436255 551755863 916382043 78676095 114351970 380273948 81739429 263917986 297872465 173778883 948720682 450687165 926380544 278169186 191683939 922464018 632850877 849580138 270007096 387141276 239568912 332605755 914925484 870049357 203397675 403886350 573533035 339012970 340746052 737427683 679034908 639143671 651347747 71789171 271148238 240929442 314171549 729215866 319634132 37725628 303085058 36185068 813843388 322473009 486080426 565653960 295953836 710840188 987001604 367884568 890379567 314597392 35333803 448616511 207740407 128254415 705370550 172532515 999319938 95394845 262212846 831287554 961707683 506417137 284266482 272273156 213428000 405220820 641043603 79126213 799822485 815916710 912473399 713128614 387124334 142198053 387687962 628858544 691387292 76529079 312103890 431792749 352954185 922416301 452824315 244698764 677416491 203821980 893982587 112187442 836776539 605346182 797382839 212617906 529424179 355164734 467151577 339293086 692083279 120140417 425428138 696126832 274878175 490866389 826562296 947631584 497748753 571768220 608688392 60094596 475197732 739091325 176308095 703481146 136528475 223750902 606300398 150724724 773155649 119407345 151114718 779841170 30878775 549583869 223059068 173842405 335645027 363428528 766988256 300892737 761937871 338639765 937247012 831856778 380155694 421426913 902848578 105723362 640173618 889529752 701419732 840226088 126874160 780907556 965955716 749331268 461960034 140863212 964638181 398591323 141674710 568089752 476134667 685550118 927301205 342947208 310155135 991612399 355278165 815264932 123252529 77647185 453213111 617200002 84486060 926448042 933868208 712357622 653042829 830421212 953973402 912112501 850638162 661087655 749659673 91043018 741764139 766451807 149071545 483277853 394432275 422792902 875187411 957982871 850741157 676175467 587320671 39325173 72147974 921299221 376995527 705005648 802454021 574076142 881224231 134904029 166376611 537297544 112789032 73768126 385288421 756887408 644901663 285505285 95727105 834597804 123425844 667001910 398254846 992304408 437509193 478616129 67110329 893278487 951635540 60654269 299047888 834123236 847800892 588832004 358105429 636625617 592172880 119293611 880969515 677430927 490897045 60838470 691336761 176767273 789904941 761437551 545946063 666264642 210646571 599556022 115871441 631266804 826221870 803939945 774313722 973962573 808107499 909332377 760500425 139562451 264924042 919875242 39045452 2448899 52311185 53647124 393259650 141110253 509845630 811000072 749450589 12074235 348181932 281716560 428826612 724525320 707159692 352233364 405959945 41983458 858879622 804706147 782422577 451695232 752849761 304383008 961065318 682699485 541341838 824209069 312776129 498152178 285235224 493598232 241262566 975908003 953281891 244314239 15292849 997661803 630527324 220956785 915890678 138585732 3709305 973920898 50959260 132468773 649662384 708122896 962214698 858620725 740344082 471797690 586617793 141809155 465448809 61986304 269703504 269654653 921069990 418802191 386416296 469141923 25334420 612195839 905496788 430880333 360839873 350316233 122053014 723482768 393633324 889156425 621313121 162025981 553473332 15695656 211981768 547082573 484397478 340939909 890407305 892574427 95584561 217168648 982808078 314416341 178547001 770898366 679675874 173973772 1247745 740082766 491403171 289703858 77961986 825954988 255698559 860516100 667155543 885418930 26099350 493446177 996847468 684831191 68908768 477079603 268074409 613802553 724170609 416092555 188497406 449381145 635819241 415617677 474947053 839665533 943081316 457641505 24639563 820076625 50093349 480869480 418909218 727653661 725591508 917634647 971753377 795448674 193494587 727532271 178877818 418062063 762161774 898088333 966317418 399452071 651247890 737032332 939354981 161888690 909771001 788293056 320140954 752543308 315194808 944481381 965430603 783662307 60766147 620184602 666685086 552752121 132575809 64256059 593658524 425864962 843666674 488904293 498499241 702785180 507008181 273525370 967553433 649093851 734149687 11617744 97036620 366729241 473390329 291020392 275010062 503114593 509340459 597158263 379582461 897055678 137822297 956200134 151205182 208233451 184800611 765248820 502535053 114595794 934061616 57701088 163450510 807529494 805088844 835613063 377896099 721596992 577603735 94595828 629496894 951208323 793768904 114577101 235819874 875593497 146119774 462612062 637927296 979252989 510031652 378803087 524002510 993876607 907567653 481523265 316533985 33759578 587361225 671945605 641368011 918236084 735106809 403991937 216045820 982220735 623394136 570790654 559110862 981456586 644405658 856241922 397482455 503800601 32711823 564569110 258113296 863024415 812460050 274366123 103155531 841385170 373439117 245767736 573567046 963754919 452707985 54357200 937233502 731595119 478830145 69387710 976344535 356354437 202489171 829535950 373789190 414497775 406494296 487797670 702629248 496064869 788170045 637377783 603341668 452707961 813022386 856694378 17583373 640210136 96865647 798720510 956619098 694209751 224022922 242256241 910115470 855303314 617972490 684065902 68968135 636122613 744185789 671990417 564431730 677029058 803255435 35386977 689398443 933531204 363638076 55104807 406257692 59722550 759129615 530039852 167637123 836315268 653462595 295577136 883699690 588415965 879033243 691648955 67037980 302978433 658602386 546660082 50497447 417235714 994250543 623476788 179013322 833055421 187417977 760864096 914268283 988516867 143406118 306525014 591291079 932898268 560611635 790071405 447675766 284349324 319774750 307970775 406958621 502190875 938438869 473164253 582233174 328912493 276237487 139614425 208842516 90362587 253688779 791352290 268001033 230999153 907912109 402908469 327346270 892003601 476243238 78257476 693138883 923041916 197669721 964285779 490273637 901204415 22321906 228924735 804020264 265291117 453609530 991104508 74422476 196346088 469943102 745097123 623199361 864614442 841198412 491768803 975676615 785823061 910289865 40291242 211019293 46861974 956007151 725572707 287185769 39269865 649207517 508815821 988140914 402206853 727528152 571751382 370668683 428487859 956801227 713517593 277874217 756429944 560583795 142448274 946500150 787453268 297068854 535160305 766906390 547944539 842135276 444439255 135225101 816574087 432010612 613167443 338382232 993051108 314355607 422874103 685123643 252783816 117652643 845887164 222032546 455998720 672316295 928869987 970323785 423372183 664358853 273379855 22368387 303616122 760636729 140993325 563475999 262029382 323304375 176180489 548896163 811335007 563421725 898173468 627756222 530869701 797255737 492693000 936994308 234826004 478371022 310149960 787185983 20889127 155438395 982442357 760293443 672053694 845038693 543914060 263838803 246366490 326357977 937579342 716030943 935219984 583971050 37540704 39900051 624317010 453194810 302249968 184545206 559687234 441801101 941149413 168193310 730068901 672802233 827869668 217224194 961914192 894594146 552372278 382461095 908986404 184845052 450006353 259893941 325587467 160911653 648918238 266295217 625638545 488221942 174060150 299090658 323574785 992490162 287433399 739696019 823137500 385415047 699872861 824424641 950761714 402818462 645934581 541967728 165841669 564273316 209607019 453898963 538764636 828647801 194057083 374233458 572227424 442546424 284048078 462361024 468943553 506846037 800177654 780057604 801258397 770218347 526039518 92797129 428128050 382330877 248462535 4303252 799733528 210640008 856099685 992320108 345781630 823644570 565378315 442090980 592698734 602957870 267261158 454942062 422287940 169108223 103588130 874241307 160948548 186357288 912490036 767406751 794425108 219082729 330722523 411043401 226463540 217531888 354237760 925704549 415841068 411339641 127010802 485720986 209631160 585945344 92116199 79777476 337394306 784321330 344190108 67893844 409693319 10084539 348336963 581237134 35480569 909472829 825376938 256540907 538576780 226345294 651002922 92660361 681160126 532719220 703295496 80995020 799232284 779886758 465551182 296893832 186574469 813521131 130220734 522066863 561307511 281329672 536617032 484105576 29651235 94563830 151941274 793102915 166214978 498490165 326367413 949049270 564818225 309291893 923538217 223801813 421545078 76427441 203309288 884794959 611349540 248163033 752417489 870190998 605867340 924428978 571285522 557917893 157133898 676340124 129736167 475734787 982052144 460688199 27669443 100240586 118445309 916300160 233662939 84982679 886849367 997764169 967612202 937518552 918487280 789080671 21751518 326594237 540202706 678522456 299121489 557471731 554445681 914709115 90280421 859276703 946249670 780672679 970043012 583563403 383894596 525987860 36983637 273044303 7852947 115188668 41303706 690085109 780813333 143253058 668231500 209252432 579250110 428933929 102664761 720467617 57141556 987609538 165078705 124501506 328702445 204613280 106197238 576585850 496464425 591777167 656852397 561803941 425964213 766721523 840139099 805409747 795062507 311475013 413085732 47286064 52387612 782794501 112151330 173629181 591540052 453857223 340438079 970610819 756779189 333015096 2369217 206034202 825462736 745907637 632634630 374216288 6692788 289465871 518619692 310319246 480019252 879254821 33133273 663882295 787494710 748685119 896476002 473684731 53699510 202715091 3023633 555326173 63139100 167905156 111083231 709798273 580632732 438219514 863007004 928081397 477578723 581922222 522129068 697740106 203738214 515383815 782213715 634081156 546932699 674369491 633658480 508032996 374419711 437671369 989829734 118404430 84125315 248333306 921647171 795514880 298196232 891417980 235809610 995219636 257882288 983165086 880731549 629944293 483707804 467785840 318427055 614270147 641389527 974083672 281993398 845362812 819016255 220489571 25644532 204365480 688917137 620279505 279058560 92284947 387324349 818984 956569158 306580547 816352929 485668740 690492354 565299163 281524356 938348243 527037139 266925506 93900056 999494280 589747504 827440189 612573289 962297992 937190996 887807844 764454379 972732982 456796408 141134091 11854831 905103818 972392005 418336212 249940190 99943488 440442686 795319201 441415004 734107800 46491827 549856227 919946277 842587267 103621313 893192945 255625528 800662550 802087534 579770188 420497641 230246730 891486703 274542062 668201712 491710986 386591319 877342756 27673750 570744168 370680198 834116610 307071065 78923951 484712150 700185536 589922424 847064764 6562849 906589714 628896450 915566281 221683509 709402794 119832264 193181280 462669989 684645007 736932152 869342176 905686339 754389352 151162099 486948318 248103381 500847177 430655435 386234632 331423235 627739799 988380397 238936045 209631746 199165726 644626186 967275206 761826974 855546837 98133250 731460673 742954635 793790770 740399192 9347363 788260920 928179478 606644428 570942489 558123354 716770390 705488988 897402038 110938508 219706959 939520290 821143915 741201434 635483771 793960875 509142155 908612514 447543110 752245620 411138137 224995647 856588847 25799932 236411192 685644512 829281353 90224068 969319962 162553664 377805333 360867685 964240326 87138499 542057611 533591521 820097392 292476564 809971523 564506476 23913097 14803568 243693142 754314003 102711207 200095 325623182 235672945 945367808 111862942 234899485 275801580 930704692 314636301 961973619 896132945 900541181 34034120 80720953 780800574 663900428 171975391 849131176 748921539 512912492 739661556 520214717 221069024 138099391 927445342 659227016 796307758 473294346 137047394 506663260 31856266 365028647 56956365 550797449 374590436 940037862 306828233 369302271 234705581 374080907 231714095 215453397 454997365 698797673 789598110 349260176 256618100 808967510 941078326 244218758 349590571 568969223 564317719 749032673 854848985 437525056 206758355 343680620 524994895 92273706 663318192 441322863 61155930 694395268 875585170 652399770 381455456 467276464 876390777 481111780 321843979 723456404 329101999 494687535 423699509 892480551 122660901 582808371 15549003 971865979 153690239 889199428 335574428 86684089 290073488 926239935 422810003 87860619 268571797 484181937 15307953 881983872 690724824 220206081 565945464 220366493 872753010 928106749 41438911 797371822 240167871 457125682 437989783 572819019 163725932 564790446 742768429 596875218 910610370 424287832 392925568 339726575 673943313 746797523 898040243 412490477 98895118 218788168 645637513 413542326 147754865 290928789 415154270 997772041 331644441 659479520 587709505 655014618 95687792 2711166 670566250 542356045 144886598 720796725 818177458 911725396 742893313 967443020 518709935 693252692 860446958 575627775 87618310 959252039 77876621 603481239 267525859 992948094 940743536 967176626 941224309 614463540 560793977 193967613 460530319 240984896 135835013 216762874 473674295 818820189 85000251 156883237 243778973 4456169 200313845 94855268 658349595 557632352 284051206 640073087 225768494 896369825 527809753 568531303 215545085 335425517 718787093 263038729 509868630 942186016 152905877 688883579 379173283 959425974 434146454 440499361 867807404 285539271 807221032 230653566 214814397 745363858 793831776 276353219 999950573 731118046 803992615 96229368 570577030 771044066 587650166 500613125 231956048 381989533 7326106 541247966 716130064 793058995 4540262 251855942 751974570 662778614 837716789 640805987 973403849 556172566 983759846 408668612 400298649 132997748 86294057 423945282 942007639 448990852 164069536 344689793 566507057 831646221 534891717 194341641 481258545 457321692 35269002 909188429 912412804 307701321 65143417 222354152 140611303 702323757 6287721 481132763 15676951 851349960 2498351 570186086 176779889 603245791 824625386 162851140 187082445 339731610 841980800 145828170 624361412 22396377 89027720 524494445 400612720 173332857 24999219 173135961 291467565 463565985 588212266 634563140 953507436 204420919 956698919 731087010 785260798 946788389 440107206 453629447 592410637 547765333 505047803 856250818 658194236 754297841 52325139 391673393 573899506 602544237 807079897 489072764 514637764 648661296 102655074 877895683 831628060 65181321 324963270 107646784 21434212 104973930 48287458 469383870 632069674 780006448 239323473 128544916 631954360 226717961 690757276 411198064 380388242 100832114 404450629 269433035 793223816 471560663 935815710 638154601 239613936 795668411 77584051 523496253 940253102 305262078 193381340 993035959 490426353 773609452 444248684 35738563 100852487 74686954 538569726 932837351 898444684 648718825 786219575 789672513 277357862 744124560 508511750 729224634 23657615 344562806 22305778 330783691 538604712 668289283 625447188 40206154 513935556 200493240 311086606 7332057 2469578 616695991 764150830 709797531 859741339 71917572 38704790 794162388 973913746 922978861 545623398 425573401 389471498 761511056 507236555 544654459 872380486 802086186 483248388 61849230 867271062 844774200 711009707 739061854 433189330 663872477 590534279 176757722 72904088 760497997 580278974 665655808 40012187 750186207 548281035 55057301 359138039 222393383 320865455 467640739 104945832 898110060 987914405 977131842 54265386 742084685 201297608 877898387 864454813 914055979 902533738 207785182 486666985 579224583 63738044 194067234 487447144 925115297 812221126 358404533 399536633 26082317 324995180 885913383 807472057 202841647 577293422 382638784 626536902 746365617 144132618 590033406 494406223 135070785 2267078 620503053 10170652 962200183 536986890 648463744 520165102 40891122 515458442 817887189 73306859 211625596 359782945 920832156 89017367 904189520 417486303 944114167 713869817 174207645 566402974 887157020 907821773 117865135 770294151 650783739 900175284 646304797 713655914 667792635 664237173 309941836 958798013 237441134 204257455 504041912 680871679 719640195 35258205 652913696 321494559 451856327 965718437 329473424 703468208 832839387 208645668 579194470 372887300 416583469 697526086 313336092 837810557 295084167 142733413 541808101 505314766 51025584 993498373 52225715 15731890 224696549 95044949 331479766 464250464 175160121 895597162 638721204 124841994 593958063 928489319 782412870 559800189 34280112 263567590 165600793 831238291 36504979 347283673 955201490 635559654 796637944 426993551 694372761 826533450 941686374 160153296 456370116 943407877 92529219 266979385 376717602 87832991 389219034 553117703 714735466 792600968 397581667 380053624 872062700 562859763 752840322 640204380 107952838 85531049 500513338 746147987 709707219 782251798 370705474 654234399 263935226 686178750 902750243 470314234 272782976 259122271 705535719 868111863 572594490 227543047 868693724 77232534 318308988 96892682 424959346 589468498 606891441 29698433 916478295 129718246 440463605 106218141 871440905 437375662 99880900 167316516 206762053 898751430 187878086 111701499 330362638 13553262 196090731 752415287 409218751 590448444 854818943 810433775 257504044 654275527 49300618 520464527 450612095 553065186 845988699 628313964 985160471 29740076 836876151 75792603 539747987 296407612 479801008 351842176 184060196 807274135 301274835 946429958 882847066 43544583 651835421 770342112 354777401 799367625 98281344 212436685 419801594 987641125 421999311 136297209 410259530 836466147 453794152 248717231 875591628 551197188 530018053 391133942 715425030 515404667 190565264 977107763 857860529 510099320 913161382 530341744 230441244 596208146 92130406 810333177 455528891 950654837 605141448 699103928 154056379 959433697 859853476 371545635 871689882 212516437 69474754 904175183 363637908 729036524 921065452 703433969 734508512 708067597 588374468 490820165 512598397 170278359 728198855 884616014 159979970 822994018 986239449 451475481 395480346 827577469 822154242 975495868 645809054 131451767 947998799 717777432 853216514 891627321 900973758 831576128 446649296 759545059 658387226 81122518 779853381 446755799 752539524 87193556 602863378 523087240 910533322 15820783 638572797 613447063 415850643 61673152 931379782 197434374 81706332 31944657 421284969 518946823 213482680 73490903 641162707 760076425 126651854 145524710 561016397 648477413 495750444 503995872 703069944 736881374 7268712 598521377 121985223 658528644 74851973 51441115 429723472 354637580 470623760 800244383 573894751 959530958 283911523 219722996 740792618 751716598 89903991 353869096 796928041 39109403 879483890 520696562 8040750 826685467 125255007 623394386 113898689 600588323 331259269 392717327 699261048 475684972 155197476 19671724 803330690 328398610 477005141 708638558 582810533 915248379 526678480 751369102 139081663 437816489 248114550 549537099 882995526 313629839 318007360 683792411 395706584 218441685 562377783 706994199 718710824 433377524 457474555 315272078 11950325 221851709 938954301 566098481 747960794 298382465 620312824 288830102 697945901 697560823 667034324 649024965 919845144 908139992 180257579 908766087 279553260 747600975 431793500 27561036 425313769 431189786 257154653 973017188 549208937 782267632 97784986 81800492 299355110 75530542 999047111 894897389 429500614 789669193 458674518 858054881 257855936 182775128 439549279 13013139 885653058 153289538 950719378 649219061 317903629 8935162 360518325 424548524 791712983 12063002 763680921 210356614 669049186 240875987 562988 105207266 232905659 704216832 50238129 806658465 650991000 657111479 994182808 836772325 706418672 389991113 571322415 697179345 170350371 588579191 145445486 720894794 213846125 718844949 954689043 846338337 647792785 294485621 707769996 510123956 494415735 85875222 780657507 302519979 427487149 514048054 656320020 284617999 573214101 18482327 399073261 966881086 729861202 881898334 364413443 337369668 67107914 91955459 183674030 401741612 446723927 88981248 231833968 328087853 684232957 749236236 369107282 291477387 783469958 668597241 828041473 702346384 37967279 144201929 200711366 295620654 44164259 318996571 188001223 210350227 471465810 95499418 962459188 460358701 921217799 824294237 383758972 654631910 154248798 472250033 727072358 684142412 708410247 678839295 159249319 579089871 962307210 234024227 59575433 245998523 364171220 91573132 836413022 684051446 690328786 975679295 218522277 214706827 648044170 134036029 767140201 240384080 90231273 152430604 61727059 929229680 118005460 320547489 339369454 318163915 484714875 396952123 37377209 888840989 627816513 991572004 472656605 617097615 544284825 770254037 236708273 31946814 216148962 804160022 962726359 231551057 555674666 315296747 17051335 797291750 609361694 26654018 808857765 623256272 763519959 288938269 529260355 912094568 279711297 309492711 373087596 207559126 129521208 363365471 418685770 567408246 603779425 636086877 665615017 104892386 608942913 762177113 376015295 454520689 636178829 163899377 430194044 513576912 839447954 545951673 118762804 658935798 288212546 613960019 594025634 458497258 908555804 262162545 311847238 268722102 552265371 129159327 488464241 882144134 447702171 851731822 76337755 502142489 354277690 185777667 785178657 699123932 181774227 93031349 713622863 958269885 735674909 30025583 145232377 841418276 6939995 416245237 152518999 674594893 278416636 676264967 643375834 977536747 668179166 151794071 879403349 452693550 11829487 721397076 480949058 159685636 532655083 940516870 683988866 136538919 132166539 924945692 219743275 510219839 701430631 507625423 782014562 925188557 415758412 10431086 418573640 398795829 622838822 119783235 31599521 779881547 843975882 190540349 434867084 394785666 128188460 33987972 142834715 367163115 434216426 178960611 51976332 974155590 975480837 337758423 757115739 44658170 571478430 153135119 121945027 14122449 753012949 576358864 781836626 439559104 647546417 436943830 602043951 213717544 8525543 394339829 77899352 546005375 840534645 204766380 68338996 373238391 912331404 425095673 529857502 515470798 618460825 435785136 192009068 565740032 144571910 877260795 361373408 774226290 654903272 543822169 20165737 921620957 10224963 216558644 933984200 980038093 525663091 531960796 378908484 159981767 306430152 562226622 342281277 975428509 351449242 646757734 47818047 608106161 737961185 26647297 838065177 466642675 60489444 512323490 506336742 95760366 411041044 96831710 785200545 51096126 964545439 751657655 843856108 681054496 121672265 413389843 866366915 483941225 925618400 475277244 400826692 901292803 192337717 193056195 908268342 325200114 208762723 876886236 478503664 474889764 770572025 734307494 240922124 673428041 492885266 4667939 659087469 863723982 681015197 657292874 181325271 16059988 809932056 141752779 642738291 677847681 71422825 510140890 633651527 267191525 571450598 762109022 325989196 775419564 847100088 423024119 110865559 769367102 64061142 18825099 951135148 815457997 922090505 449367884 62357584 42328893 162838991 325457884 246067888 654582550 775295671 982986399 510993035 934730985 667195703 812810424 933791511 129953871 918147196 922864686 943404992 925693801 90364393 191137325 736754313 556531143 427932693 47446828 492466535 107392293 353830329 391533001 638004101 226299148 570846580 276982367 646690518 476781982 325902837 12652088 393541005 776866141 825239663 571167224 810447532 122653288 451851453 772897683 65346774 760950311 385675451 438368169 558773109 183769518 378707263 189403182 227057434 249575342 533975278 422899764 25003132 779314264 863078852 39799524 124040970 985384745 85019634 265474828 682016144 755343365 375029406 342849152 385915081 650210531 70720802 228150635 530554360 426009939 539300411 860095565 845868141 124561462 948953201 437100792 540397193 740653079 299956083 677486380 327701845 994783782 809133809 422376389 611444721 667980850 993132759 521855003 151363605 996740170 102190608 17090831 331975312 610709871 97514894 676608273 590831729 694292741 658262168 20589224 689804613 532039897 119083697 278932887 244320056 870218415 55060847 392838897 893213993 177541305 538514842 523399567 753402721 936321785 908632624 544880346 891804780 785112573 528978413 115372474 828715754 461910457 861876217 609992210 528407213 346762841 168175529 234846662 143187234 494350840 170010811 456984784 817484636 886918397 210787299 216351074 44148945 908507940 379065460 399109883 920293867 428794096 591266741 539336169 723075385 283425518 406448790 50603492 453002484 248015705 927093220 206244295 699356049 770631560 502321543 443940292 75331518 857334127 14342299 876452282 130309585 115255866 801089597 111962396 832858946 167749035 691486831 553537411 441102667 356563879 465498611 108969509 137926255 262529934 190429128 811421553 373911140 35402045 407422706 679386355 359246999 105927293 485023428 293108001 128441565 261234741 256328928 897649518 779200532 422254154 505644281 361560918 572352415 13497375 301696339 767763754 730323594 291546920 843902324 723371766 486395127 387049025 81967953 586066557 7137319 652316595 208830871 641457147 183318916 97437757 101227584 488588390 40346077 949911839 942427889 183711615 559207560 57335013 23636783 377621773 767793636 91163501 842669087 306010331 455189768 797556299 127818908 138187352 25105863 786744554 207576222 23916088 576611638 969032795 219844065 189108329 821175228 779873492 959842497 944242819 244641440 655387128 463126732 353592437 575404677 359920208 322456121 50946037 719047582 815525071 642903366 736493864 90200791 166589840 154570399 156009631 424004174 413499945 672000105 835217995 458694919 733494597 910649846 25781457 905367525 428000157 603063929 470695122 226549716 556479394 814003839 679406335 943751560 528752457 450817703 230619093 796873098 367851614 840587735 827177890 632067363 153511683 284535062 686827990 811482601 432965803 663401485 309888093 491559361 612670137 402495225 371655458 474353083 709145380 484968561 33298020 358887969 57655826 907248805 107763833 189698013 447145500 686203803 296533311 645712927 427130774 568219926 200830299 431465276 908307889 578608005 486830132 915233671 253636305 855073178 582620251 982806692 779440481 764687072 78916361 756243132 272372649 808325722 840835159 331290417 642032662 476145531 383757045 450009894 713839314 358036256 686660578 941065270 115638260 547092631 99761995 454363874 955714545 687258463 606767505 297482215 881105900 125466933 636917934 140065645 526355199 430111539 319512402 333274190 340408482 563466368 139040839 31024835 770926565 655991050 15557885 394331571 363968390 519068157 477578947 951444687 927287939 60513961 939721765 158353991 771627036 808084381 574535237 489290801 902769840 580238058 235460119 478371876 325900209 501044303 719736738 985898633 488767611 182948611 68699624 94754826 217790311 796266688 698437783 91069087 126715173 683151054 962073144 470443191 648382747 65754048 17019803 526957763 239642915 68804956 530670791 190748541 10619375 888514234 892983022 727617040 663898872 91779741 640950128 704042424 829151140 327877267 70090803 394881791 109304142 247864770 742562533 427656912 920132639 95561436 472009224 631854808 952345041 117666191 433043458 155233329 110567263 714779439 304637628 228361085 983008673 44554230 288258181 249565583 643686255 32661498 796422390 349534461 598565319 764223733 712604244 834358961 835564626 356960572 716341915 436983879 933618768 305238354 90825183 909952476 299838540 986404696 256246224 931995972 147797648 840636028 474384384 357256315 779177070 533493350 770285477 900029306 890402681 588374411 650758112 338835097 693840037 835098786 588085188 252079912 980493643 954526054 852590631 902151618 108207674 821586243 317279812 122883439 596872660 275751850 455517496 576945863 467315882 473282760 503239398 448133624 689880203 502392462 197666446 312378455 566449968 356450351 422347900 124641588 131785460 677420154 623049045 490405223 648570351 371066230 322714218 387564786 226000844 292810191 883703052 510140902 695181779 382379530 425390197 413589930 588771016 489115119 593501067 268276993 815585631 814988860 538789404 134748698 815234049 133573206 34447922 123252547 247691617 938732839 399207373 740555512 85068438 806753887 167152782 532553573 965444422 745568236 657629838 146273413 395580466 771590070 506119550 458546600 197446510 971112304 392211392 290876018 299372536 215558983 778267971 247706432 315931808 516959820 379141588 573077534 417559954 128709774 23035260 426284579 974696949 499960367 334331060 122188847 140084977 729124805 944367364 854270385 451112672 201059966 744218922 535745831 107122987 700882640 172364531 987812966 478390236 304514214 59070796 677555261 794517863 24061686 913531006 254916500 460290253 79463792 919451442 160218087 928230346 490899219 909074534 655265758 707437333 71689337 978119609 196992694 42256795 214826646 72100612 853724983 147548433 1497467 555022079 788577431 175243600 627385640 991297619 219062949 778113228 898137500 222224199 399808435 872637446 863963623 504140532 138389463 431286885 82821247 144536319 252714447 886173514 774128108 798091069 48878818 320978581 928377076 750804432 111429221 522240104 459421665 698054884 651048804 506848980 713090619 601723082 202438074 104048205 795277113 739869606 61373588 921531680 66855772 656535120 831380106 724055162 292914427 660704020 868973517 436303477 814320183 526541859 717538257 266650346 948916341 663939992 724599384 367713357 285416110 406485953 138244717 925893329 252958858 496269921 27515746 549332768 236451409 874856863 529876462 19165575 155138452 68226942 884047273 459807884 716530893 520595694 727399294 516325369 247452555 423885677 655180651 723829956 840913472 957781035 635800344 649465758 635900721 812596540 293389712 977219299 94956566 948759576 138420650 945018407 799844481 964519098 523200788 157802645 705063643 115259220 593425854 598960014 727984174 403771336 884133635 271735879 944500478 646681515 986550821 770811314 918369674 732164670 917654419 441059943 48306202 548879114 203330037 134428737 274718318 386178140 736061309 506475238 524797523 475633900 165570678 946526539 440862806 115058581 641725772 282057302 752930064 434759990 641869238 995790116 773800450 340180260 574173696 416241629 811438193 300258964 537287190 516424484 601513722 229867237 702658858 592587096 420021829 268821974 383313441 129175377 188322249 339940184 6178898 185492111 558237432 545729072 800679706 260471123 527108366 88946449 173372909 616441241 672681658 527215809 187743912 874384934 300254931 885522953 798217492 829703557 444460594 872821619 933873951 515706325 541646055 326097683 489608877 36357331 677583053 748178493 413087096 909247544 306789294 66958405 850631976 365018412 656317094 834853637 156856771 129864647 856694799 397292326 774110055 522910675 37996679 200171754 895751971 97530284 495876475 984011140 942884834 226593102 565417290 775976400 164372275 220007622 541867699 331391139 910195116 673826687 222930884 631764538 709535693 558565544 429262602 820324 346082488 899579104 860726493 637957806 439085210 919964945 334613343 788054508 586592494 91421823 736566673 993248183 597244558 237096078 15819533 421278338 26292600 841082743 445141556 239514524 235977890 955581968 785480711 641969690 848276353 939591444 846574426 177240952 288954042 633921718 607223378 107695353 78960741 239167972 245356497 788756090 371527975 968119134 132008386 123861499 457144385 536913878 921054254 43632917 203981019 486203627 67523878 310611200 7867266 665882319 544044183 234437887 166061575 767017113 328879365 860684567 254972618 490337956 244878442 922471406 163760020 885955021 836383699 645268015 889311569 666572308 765395991 267202461 558756937 707899451 620398680 43455264 412677539 907050422 154413841 877971259 910845273 66260051 479528780 700948914 621712141 873787279 513253539 580710427 170528359 815854880 3345124 730404663 342939019 557776780 333974802 180410771 953144589 461269737 578722063 116045958 247030595 179226124 631801334 825317735 407225025 750739859 579986052 733113500 680354351 755217017 970810384 122189733 893298714 803343653 153090189 508128670 512652529 714433996 927743735 629658723 899327719 382751887 216422095 47383876 392224832 400023832 744577661 450545623 209313941 205554975 715377111 391364717 499798750 260638061 336432446 706986523 523639354 554188068 840050032 446421065 177365729 335863317 733944648 256845303 162221862 464920387 851428318 749424659 907998140 889064666 692138572 22286654 441213703 377895423 723891872 300171305 756618682 999513459 666941311 91391139 885027648 96394650 640890685 899839020 122683669 859356275 893641602 998706344 272196128 889525339 170047134 862658039 270460969 955396639 314104306 760525203 516196042 89043435 47481911 335810435 82449739 575010893 497278867 148843895 401941093 45227957 797250904 505628570 255004911 778523692 258987354 356052141 4730939 43743309 260526063 631752362 255912056 986030071 309041218 20015016 354031370 123030279 299588520 384524519 32844668 532402076 335522511 988553311 882172046 703721904 610671663 939822447 554757973 211868254 194290746 430742206 557126798 72681204 420533951 178750783 494129178 663491953 427647787 984637804 382620700 325254585 124229587 16081919 569309575 678520953 869924047 486918481 162291152 947827517 505096894 684566672 896635647 642770317 790052773 312292635 500317841 807140523 734614641 240241029 314165908 981257121 178929850 917139526 272642771 620718783 338086874 26247416 40827624 504564820 651470620 706156826 295375700 799786811 242570313 50824021 485506382 236847748 208284760 638845671 243211366 184698759 955154593 845800100 833123063 148249715 850467115 140964022 250336793 682948567 661189155 338679819 54014771 23530778 411921821 459137663 220336975 398144034 769500396 900134195 107054468 645285983 502090891 166202699 411079114 316583829 548541800 525851681 373399265 411622050 39450396 81154528 768040495 87485001 596189110 691476645 382218333 301934951 234011022 538548855 21513447 117204297 819385886 519783556 154670220 349357212 734939290 102225827 164513940 30633550 815533987 771416395 178235634 964334380 126032349 378774009 370191517 293682413 53333380 326628064 779427783 766702106 334973592 389261586 112202681 986778371 748340123 401441028 298289354 440345420 916401529 344910204 399365551 229246077 698515364 852294245 699010829 603853915 843428516 719975708 810155191 80621484 527617594 914121824 304621234 76513558 151916524 429370888 154720746 549651051 680829526 199766448 493892463 33761819 596568783 442382637 777237080 85983452 127099278 214821622 337402138 377323196 113693476 521320176 111448922 193877441 762318722 362984209 648111682 62337038 486973541 710753352 500038700 867903480 306837639 219547187 745563225 424647682 176792229 990781646 289631744 110221451 522671446 104989737 735636178 881627232 502113612 213505033 528082710 687870166 212173435 315731890 720207022 473647378 698488616 691201952 238059857 725789950 776566400 867366811 804876020 154930716 400683856 93572460 668872209 751496057 686045036 830936818 187195744 491972894 694319749 275595146 241073345 725908133 323007439 673960383