45 100 563785937 435226622 556518373 909512560 174032533 201165846 139505338 349424713 564827343 998448118 501339027 512834161 148195076 760362387 107809934 559042435 677095829 2214317 692993591 161270066 198515694 37450659 377211970 756737479 493395736 795869904 324407604 826528229 902433448 8627736 376999809 212290277 255452837 113237233 608562802 329428855 551566273 752394587 113767719 80864862 591528841 904390138 422103135 945884376 137083256 402897806 79781435 608672562 757724696 807374074 881729075 468553129 137870842 398332231 932225354 171081183 640827605 224154061 169402290 997423443 978667941 994286454 727573468 678080961 540892270 179088525 785852683 509079118 252942722 443666615 339908903 998445853 745847341 415923454 818142652 81110701 251448255 981469826 918248713 358949156 980906406 610923082 959489961 854297545 212156784 878435846 417779305 745500411 50488762 720159736 247968349 289477523 202013519 627002394 179477137 8981881 552859002 383558886 959048452 935601218 100 303596003 747824568 98194858 884196373 46203983 170683122 754163545 922780474 13415141 663933689 194462087 440107111 943570011 435256155 700671521 793775015 562810012 825170981 130693050 1622222 366157668 402029785 16656203 874454760 741394923 56145872 850140376 587127792 320018807 886363835 311753945 843772802 720476509 42363908 196702569 567370295 820290062 705029553 580784673 933033652 971571224 374693739 532070696 846542104 25218292 347058856 287690084 417252567 180363348 951798089 575719717 786021594 440674153 479968911 287243069 293941017 173263912 354102796 947019568 304914793 191975494 951842367 120526090 855231928 74004425 366402851 879171827 110036746 289153173 858759661 959607570 281984276 456200118 600994504 817163981 305294148 973356093 636697950 657335652 774777032 620613127 431628093 798456405 345909104 896409963 209786024 599730916 333601554 882505218 507380436 523906484 972136615 594352419 645627550 756802947 262496343 972038222 796224681 996624171 757653644 100 444715238 848983547 594610081 483117447 980787242 351062522 980235586 157245492 834862816 260871287 427651517 110510401 20820167 442287865 224104345 942246003 34534215 485990962 830334302 644168192 647601599 91786961 966480042 911087108 530622694 752440059 336120462 560905203 312665699 527185552 944999537 352574382 626706635 560435690 383129226 133088423 364437296 381898106 538125989 616541077 398762103 781470018 181885548 678613606 553124942 308441108 940547927 28954854 17546283 886696381 431810459 68944449 597733319 659678853 914221724 76585503 633857970 449258018 394722473 351259137 531132325 547386781 253516397 86854958 912201704 561024292 26162950 305581224 630134352 176354326 681415661 73515735 126110803 245859031 129165371 355030270 14477292 950920204 962622686 86998090 754752120 667999730 442413234 111500574 575969455 180469227 503466893 33934683 370943220 33517099 985133104 544511133 352021228 806959188 23523986 93173433 458635696 650729470 43898122 314705032 100 134223403 284783562 297378639 477701683 566473181 709449350 53777482 734476563 338618692 970860741 1782187 143265272 172636544 483608381 526083292 91043505 363990891 175941531 945077685 206847849 354130945 64149516 127484306 73839569 672172872 523027912 984794133 985236935 679688935 761408436 496278658 3865485 527342918 120466606 225950987 723659649 473881435 201413957 634829903 617909752 61086395 441969881 818556460 26987911 857857575 687389464 760582690 247906455 64390577 607990276 563874124 450181940 276393538 837716421 679425192 960721403 175776883 862849858 729329804 783051083 135713613 775570185 199962681 169204960 624166085 366695268 128533904 587451400 711833719 596855002 866281121 193231675 100178255 228431378 294941349 628721957 299826592 11265816 312242100 515728643 164595376 171319004 551203404 735708465 866981894 28401634 623884245 320933352 85742 306090202 816931106 337142338 692592957 236217645 978793141 118625509 164566900 319212098 123898471 120725100 100 92781509 893311701 961888891 601164589 381156358 41807468 857184925 968282655 362811033 316820657 675341039 925875174 726631972 146219496 38645038 285626573 924713692 116204029 234756211 850222282 489771636 81388012 511202192 965010730 117801505 857868153 739690435 186454849 451879154 56263044 248329724 128320582 855920888 86365462 818700546 635802849 240079164 475163827 223356991 88593267 871048951 607950423 405323974 421163399 588069188 621604314 924236505 636191886 463020069 285833324 951059346 584285391 586347145 24708237 704920734 363209785 747067576 435812242 683825676 665132009 631589547 193951210 331533996 3303379 912614503 702274546 226832730 696544344 982052184 256756245 251057532 164935491 235227218 626980082 474768675 494473340 417143369 244180673 599923059 209874497 770953546 478585976 450250555 806117860 261595377 911312497 400202363 926005858 607279074 315497514 772282402 244352034 681454879 624271720 163882540 371225517 142237051 497404039 904176875 85939601 100 994638479 653478754 507821129 784956200 145831542 443624526 800257487 72905262 811127816 560295825 816527127 949963737 537062827 575328569 456965671 634949367 558000832 878408963 827603974 413473089 148321601 487394967 843557186 641261975 757261342 57451333 745731838 843567401 340917589 392989224 424001314 706098742 748625797 979477305 908668198 842313935 565089944 306914767 461603602 94885863 375397165 268217357 618782142 849741503 182891122 352519372 559356982 711407575 71326341 665427579 708660893 268774553 867705428 885661804 977672691 485236615 854559181 952088239 254255857 814433325 940539184 540353486 215099856 983910514 69739644 324442636 366197717 44209914 969280704 262898067 609371213 512171051 598723417 138071185 599016456 841106006 491623301 72551086 508822179 104435673 207890091 909537250 596279227 178153171 242341553 313226745 87217135 703667507 293676225 56825390 680910774 827090714 323483491 849678275 985209023 208436197 440142644 87707287 254537581 941021735 100 620948258 688924247 114106461 732826515 71181383 113834003 55306934 327763253 51707177 678933916 890075735 265189295 708538920 470409368 4162779 323791396 785739143 550431055 257156133 179064386 263271015 834064668 361001569 757500842 116659809 661765999 169333338 802876286 817390000 525592042 579543843 466451443 843412429 153819911 30554358 598624608 368129365 65836067 770141998 668187255 111649943 649345661 524382994 213045958 158486784 421158851 825236909 114379629 597424986 881444570 935651060 242946158 939376492 208709525 41886680 896280440 304006147 822618541 376060134 537083369 381184620 846917113 998885153 717829650 423337209 763168679 344135024 680784159 47789611 675769363 685112585 499639668 979296857 27719969 329198709 452720394 179255325 352685275 624869633 297242029 640976030 990858213 455337494 368113102 92296109 302922307 497267340 972756701 544073511 511327018 794377231 641449233 779723218 437912154 337412320 134645593 494898518 854138489 443482464 885940333 100 524209664 248644919 177855610 301057829 208954585 150560457 15746859 94752132 285020231 714485721 295376316 930717025 777857134 919927968 83635052 866584130 306459991 363878466 834855958 812549074 156385819 260072830 305449020 557881981 543094943 964189769 755202941 351148683 563474143 381777809 449031967 682143104 694052280 914474691 625949353 221244522 631941689 608234842 8407964 501869406 108018669 823656487 820970411 116956444 821182382 416144979 138899242 245136848 86723549 633991903 505822883 842213706 698717006 140393770 229926420 127052701 441573772 868053781 627155726 963744211 935349254 383169107 991071784 910926656 339256371 427860834 889911619 825894896 311553756 196212290 203283267 710078933 532905118 51465308 368968845 615584630 559758933 394250027 739462655 279353681 940347650 180567100 279134646 214079030 192573720 2728278 893805371 315578834 203095027 948613692 731129022 880086146 440653296 350507737 795639508 225829210 989802786 358306274 14549403 341765419 100 589313776 389563154 678320723 145557172 955129208 736805855 127214434 849250832 506331335 858970672 928435814 391160 715440274 491694064 62458753 174778173 976429811 76262360 982439586 631529938 781593334 221587842 357271094 417466049 857771793 343691211 517068391 903336202 685092754 891022975 99940463 444437694 358844715 168074080 297949780 515629132 479059559 82666406 404687018 161699161 268801116 328512459 894711887 957333019 659205483 52531414 712487484 405702011 440117404 719443088 798611409 471395778 510367396 388108643 381173572 882637175 55313343 268513432 344429923 112534065 96134577 614201937 30020463 38506350 795663054 546871360 739269107 602607388 20717732 572255977 158617737 696537342 854232783 786221750 356715789 249446383 916882150 247853478 838887138 389609817 625784397 820701326 758262857 562277090 146474153 90308029 817380380 106438200 533879777 369232066 145592173 900008576 745612113 639094582 524661170 506126561 686691792 184508214 715284060 202717843 100 415874517 715291232 806886991 720491402 337710800 503974732 536443496 866875676 287201088 992273116 53796248 889199626 732635649 632796256 31025133 226148865 445917773 121912988 668507641 580450527 668214809 17943898 462877422 209876774 899557668 379912190 453650733 279252644 171281423 421701619 199196208 389594116 358233406 418138961 894280430 28483914 454421835 338395109 14184619 724165022 987358804 146733125 13627766 495505355 512508110 71502705 544583025 219274804 784021194 738588126 388953126 72303726 190043834 297477369 214024570 294777982 291232630 177071671 541766423 371667769 846796149 723397805 671169308 199078675 727768108 473290047 559589410 309217763 848151522 345818367 972084309 950591360 160861182 971742966 378266779 630782323 4389028 476737395 568536272 119597130 898901263 915536543 192877084 688606139 652817282 659188050 788748132 315564160 930647366 107474393 545239895 675932707 78340440 67767933 156246632 817888233 778873101 479270649 373762445 2394882 100 943979184 332336442 467857925 869486690 408251008 787152997 153380966 140163489 258493282 97906363 661486084 87586628 961903982 455001098 862305696 524254737 924134403 129863444 192830771 170722259 579721205 757490301 707856599 993269306 398075018 22053838 925487243 246314387 577475372 716853745 895441609 689203227 255981938 188702204 67231023 669221646 607932918 53632893 805907393 497292106 422612658 977153520 13858368 253785627 115926493 381934475 381897732 399959595 168866064 986269415 414951761 406538532 668253481 338483741 97586591 419194001 822820093 2173252 526172425 48682810 110485595 2768600 179886032 127019691 977276032 950687936 218147491 628315568 947988878 9878506 326718456 25590452 430928178 847553460 324630439 792599459 721645518 805861953 175019168 517611875 285553801 499669358 390080465 194844118 637564080 898714223 796124646 53671333 939519719 423845243 658310761 469902999 315606538 561911192 955852254 794454476 260838084 687076099 758296358 288449425 100 721907598 57025142 519889606 492387578 988532391 679869443 702519606 111746811 724203899 436594095 392133905 979514063 124255906 11976056 257302304 979203381 705054540 410054215 255795381 826158375 244412822 506054417 184976982 898212757 65544050 373369407 525488515 259455432 842442222 901042591 640892325 60534401 459435224 618713629 851582063 529979317 77729787 613028635 752608437 803867805 885944905 9791375 424010256 176204230 461797554 339516857 11201290 134438433 165387302 24736961 936077026 410402692 252198846 643003430 141376824 659206015 681962693 130871701 80017924 299668982 495713767 302853607 30788349 341051339 936251494 541821325 972989671 194210006 598306120 441167982 214734848 382375373 495941683 68514739 409458241 172110934 656293753 997988968 291021616 666443740 464849187 559343121 512884026 259003158 841462941 630403212 599572084 296180588 672458823 17286778 784650834 501647721 248745468 87716979 44329326 679070125 399996240 815338290 482246914 29286090 100 652043551 321676561 752067832 274766554 895783800 686806872 264448011 494486632 834918195 63579143 398859681 978487256 482749712 620735705 238903686 630489754 269009403 179572763 573318785 567230619 436577279 845369632 791194901 777635449 698531611 261546165 676136767 753993856 428259039 87094432 408938917 429337508 636077056 513855223 883988270 232495707 163843740 499696883 95013977 901118667 461832735 647352962 774994205 867194810 758710964 83281866 144668320 597559398 612639392 441771074 853834727 294014246 144538521 885529372 408302560 186331359 293358694 809738375 303647799 236514143 713780320 239068314 195519342 711613535 961015142 44359006 595963123 104486991 264012333 637875322 295669891 953769294 5139579 303093901 868104700 397546119 630207682 389432333 528136365 357673074 512195443 291521695 45022149 457408232 526896251 767522412 971623426 874027127 544803393 370396765 83048124 232605919 368252086 983038116 703700994 733935960 497099255 895045275 857392805 58636799 100 612555188 507413130 485711836 528832750 532043632 989508314 480218833 765009881 274017913 488495602 830884288 340642149 599052347 837191572 107943170 825734722 687669298 851955495 119835683 873245092 555494281 480441892 200323166 613620671 564827763 17967149 713476624 358220194 112390793 19372524 843234507 522055841 438745911 997836495 83275504 956133248 401426288 42677510 653199193 546485367 867246696 96586118 319465863 511670534 579611737 14974877 390306560 149554751 223385294 275441396 32821864 803537946 310316698 237038190 653128798 841589750 967293111 705691214 945104587 249339929 338597951 798595841 319527112 594653934 318424284 351504881 753840696 680979391 856525359 298869431 80346979 736090161 868874942 932204119 157877081 357501191 580327673 330663710 704008133 940259746 618424302 158799477 329991635 43775006 512697252 484912376 864831653 886214439 983244343 373956743 543946855 397666774 269962743 501180606 129746982 764472339 578939400 816635124 927988609 545332113 100 196065992 129114800 586528338 753527045 572585383 801194193 25797230 476634968 919696063 818863193 440268260 22729757 494439800 894414606 347264715 753006227 508805828 346883635 1847993 692833056 787068417 969914548 384770992 442969082 567606914 877035413 191536835 736769549 16437845 522006562 77569949 710194963 446995337 579531386 772528048 71740707 250394415 199561198 122148635 374535338 369514516 923150938 565519578 105560749 689663658 333414494 888436215 104487423 983186056 344207911 274357023 507141870 954842883 897571956 72030260 964576472 918205332 78831373 275461020 200689609 500744048 111241369 971881195 988113743 312119701 19748391 815160967 977206022 427433859 891048019 735367407 731399841 155858016 978283697 54126132 822404164 733142801 152220018 417618983 73678830 350038865 534989984 107581848 299033302 385427986 691705888 495532395 328691201 63138629 709225664 496124874 683480678 769501011 715628591 678963328 899826807 56514578 940384353 828744002 58794686 100 389520205 153960396 805312838 764679278 834254247 259210695 538686547 830085395 912775773 507949390 596937360 617257893 686753583 964128752 157577535 311278265 320896237 51729172 660820451 495856704 834975836 865784015 103777388 516155539 726095578 96397701 932830472 366323116 85803054 811984334 117927054 462437546 348447115 586214796 985717545 856589191 998112120 956744392 767196449 210239174 225852737 570777783 687699181 258683988 7856104 47909825 708166910 11471020 438166186 201639845 653967154 88573084 497913461 155447657 595110318 234866215 954096070 518783931 4544124 335896291 903555792 832710088 643962387 701794086 431215218 399792672 749994396 819943636 7259821 810743934 555024224 782354180 955350827 17237807 466361752 984537416 930804669 23194662 303359245 21005312 300497983 692875853 40766268 214058943 259663564 617975240 743016710 749656385 680760363 866537829 335024133 739151702 956495336 505861812 322371952 792765677 880622814 533956492 850916666 142404650 100 396025853 525310751 68071879 541190568 507812865 995669144 650686289 945675650 568919672 785986664 885900915 700085328 982399026 795412938 629986429 440337596 857049284 828683662 6715940 886740187 706156867 293508893 114711793 232985487 60251410 91890296 797139838 548497330 49974604 177927262 451838084 46977354 420602706 587133993 590692385 67489627 369861486 796223364 131499569 552868675 456584380 880527617 663948681 400368890 349510805 677314794 474442406 820739625 410960328 974326631 756853078 165948880 302513603 296015555 487544469 961314897 580242143 137346408 680271237 675039194 892596948 841590078 127287612 971418626 889072848 311075266 108721904 499028012 733463110 77371551 306891284 88308412 777049047 88450440 788385808 235143761 813873433 229521269 325469248 611505832 686290851 481394151 781628106 235462113 138675328 147844867 386796861 70608286 665823017 495549767 584186925 23085690 817621672 974313994 985565503 579957086 39092772 61441692 459736451 635920839 100 137931187 220165061 100655916 549214556 477820467 476917411 328229836 14370997 392226525 338284087 851904848 470018310 598048481 857175365 835082398 288939051 786575574 197657755 700701970 617047409 330185294 799758537 277491757 361845419 870840569 128212782 209539656 154202953 902285970 554277240 46595139 903533023 239101406 953747974 675762617 639131944 221223819 536673742 15682254 594249724 7575459 756752040 791320542 943181380 442080574 893584178 149998144 405342807 495170755 554210498 172397371 943788807 139463567 62313890 229239421 978205118 263814329 649790298 13627579 249455623 292683459 319898348 751845110 300661636 935020623 274758548 869258374 95218797 874761743 742422541 860323223 85936183 257622183 59365675 399058274 221506260 594432124 778380138 325227100 647336078 372871583 805756343 861206554 520526971 927739926 774918900 876421957 927960061 152844320 524536059 67474037 427171265 787688485 705475019 901415469 54137636 123143412 12952870 484319919 258066729 100 293393652 927402038 803784801 156709481 93153532 92178400 768419185 479316968 987615281 817743636 503837620 982132719 746501360 504498712 636074151 788383790 99301566 750900602 986740113 709003135 7351417 960719595 257472399 276894064 411717822 943019757 698609414 219560140 280782918 284538504 108113689 698054501 409144386 916973489 240370684 460888976 222850532 580329228 313875018 258831549 485583634 546739104 696312884 778095220 918990993 121410340 623090787 376059979 803187273 755378780 759964838 719787534 770234038 345284202 459015257 126928563 399044593 337610089 97703798 702279103 885465583 94056118 919011911 231345956 262570413 302545925 706365363 86340964 221251995 206644530 158341075 380726457 599764988 890235778 147812296 613441762 543550103 438475713 284200082 56067711 827596367 999399832 255940866 62451384 622108087 248440912 567905626 350660353 484872226 92470535 236810398 208796623 927646234 965131670 831661604 450061867 414015610 640181612 753283505 483780184 100 344744600 943561042 301997865 205098697 168868330 850582210 305463789 696234436 984460194 901091247 132443468 63383984 301715593 91989105 592769518 953433792 849549653 607625517 323191727 848464079 524138389 746793610 458962210 829805390 648359775 501540692 195265656 478677463 29211249 25921845 467934939 101816994 798475213 400700720 994380383 389156251 697911143 217704984 987375060 866654243 74872330 33909300 7243813 592240435 39430721 833251193 391187407 549460615 556021927 717115623 925886772 9749708 547334389 999663396 589698509 496221839 848261854 418979046 968708743 11315547 103880326 63571483 490639893 787094181 234703778 348754353 643043005 20532747 965924665 291653563 725035347 641474586 851155691 177031954 490447732 617926138 424331244 448541306 145192508 774147675 272803961 110097840 351077685 254917462 596845486 114181970 741096442 422222296 116820882 630623272 757818827 689633974 172153189 814283138 407925161 418720883 831199760 150374920 845751124 718081767 100 65267586 969488181 712959191 539646402 467742540 337351326 82874634 549992567 680584338 642253666 631841795 631240762 941697103 747455820 128573281 735659088 326267180 40779464 432189205 481560126 893079187 58425253 129843670 609362196 673948225 821692532 169486523 126170570 723325447 877506773 387961773 226934819 540825190 933876381 329701023 856958306 772795232 892626644 23693069 575974077 176668227 36530979 965339954 510363377 49366395 900777576 353526499 947716627 102526552 909071923 337289578 631267925 257023716 524269293 659820132 52760558 894650267 964718758 294086899 978817334 231125896 713052681 910727170 138821882 980634936 113655012 674886315 488978699 953357977 557518661 152636831 180109867 6312542 154712647 603230225 81944966 320971133 872922376 533490606 290011840 728328740 197804087 104473967 483617773 221264311 702875555 681075942 746715634 419413205 560948705 247641645 683401879 298726589 139045904 686775606 558676267 650686161 4790776 663031166 614619282 100 475051401 749862570 221940892 346196515 519562153 456094830 465194132 874673560 839465507 150773863 288860916 877995420 998942751 996539340 94862791 344750195 480458172 211683009 964311293 695407353 323872741 358380365 494172297 933801194 543604088 27341074 104096014 843809097 993798915 79135751 451574070 119654647 376107296 936951727 900255127 278515015 190557378 66614103 610084733 991035572 395432517 555965280 2409635 135163652 647361359 278893448 953868094 912322556 646106782 299540332 238686836 72621489 327183155 86063745 617629361 140476410 641216552 146845163 438516004 951395880 220593390 418616657 466732336 579500317 67495013 531643868 337342032 364148588 292082422 895387450 297342011 421017251 773778729 487250652 107282131 155174909 674191718 415806421 767611974 615823660 782928751 812583146 153395391 771137409 358240066 107073193 657209411 520254200 960958109 875776617 117257488 376474439 275369057 983011950 715904271 333312751 471370344 513637297 340078555 167563126 100 682292913 193393239 508425807 938636414 602018477 267747612 774547716 395969908 580326003 441417586 647410648 537778061 197786877 112998158 33696554 367897280 520554329 150520333 995900148 834768118 581323838 354846418 524636361 423591195 127290620 453979827 237543033 756164602 431351603 249535456 510991771 53200584 270351395 684249144 258992530 629913938 944023683 742974662 146906524 744237822 910591778 71787428 429635056 83554638 583447861 301789764 654498558 784147240 568672054 764097387 204933123 710707205 411483309 888024128 244679422 203166757 85196409 548345274 692914097 119476219 298311355 395328018 473200463 792740805 205165087 628566145 302108800 502114366 930551734 993358147 821033019 431245897 407728727 738107285 209473185 569915465 507793171 397345915 347197880 569073162 482689867 211441433 264543227 421839464 949357222 117639790 321740168 854522828 618715714 144071456 660345384 476132221 90095993 732194027 136801927 257466702 825186595 662542958 134104250 36589698 100 700493289 451108628 173957039 975848470 11945295 34145068 743479720 663577663 408297945 652201075 431951755 736473794 873140288 276448531 834731704 595212164 783420360 794198344 242924506 896201350 740984566 253176465 537588386 537443523 787869431 757121384 256102951 119323110 194526526 373471817 96069588 46028667 25561462 754757865 866446218 15347466 482533025 739702597 659247217 255335591 789643676 524938939 862753482 315562837 818704488 1215333 764946660 789761220 625705345 161338573 834463700 905161780 718051632 23189484 767920351 913810345 364690999 849767021 649299058 836735762 513528360 570979046 221535289 30555638 620735753 213359247 411293585 95432040 996654748 336719982 653603213 605828844 183708983 526251431 241445835 65310317 107057427 975807332 649147876 840484042 104952517 687728570 402183972 393980364 734548288 809375339 448815442 277874894 84051087 429972279 734053874 689998871 687242207 448059912 787342788 574984564 198171059 307190622 266183663 47102313 100 306307751 243466921 111534331 333109093 875780688 721982909 279977338 211032783 61900309 524172730 709019673 321484831 393068741 715132535 201802151 219818080 934523604 927333048 398669208 49311754 165437555 6653548 201297247 519973561 402273016 994748559 831090963 974996932 627881516 995404228 52046931 291990843 98724983 175286864 595258506 168318681 535585497 844402739 512613108 349594542 884889157 559448414 453050630 158477415 441978033 511030616 979257456 460964985 722448804 288760284 472903174 716657927 613142609 700293507 887300931 550243323 956402385 891031114 86364621 42228231 541299878 38630643 788171813 359804549 439574633 685596079 517343152 687224949 731092744 140993541 568668502 215399066 34140137 464213897 647808801 558019221 243826035 528940696 691339747 680169221 574594081 533361867 338703167 894048476 776020233 540624480 995935725 588716776 589931785 877575816 983679432 222343140 986836111 68240970 799772409 711246549 260167368 990826757 43086671 982733457 100 557618427 789433976 298908488 799372288 320248304 165687905 157890412 931534253 876041540 157819900 184026243 713293960 557175362 447021752 517046597 844293584 628478243 613876452 615192074 649636509 397741890 96738498 263337027 230325056 583198404 575312209 968981460 979068946 755905343 39150266 863387046 808462046 566139784 37776409 734455589 73812948 128679562 904453298 543111107 405582790 280784024 863350008 389921799 21409200 152578366 943252385 768096376 25293243 482754749 818119071 769509268 944199299 301967166 71540093 944088301 867672400 290809998 28540291 941001535 861573100 612268350 815775351 836049100 475032329 492639435 755183596 682307524 507567797 578776361 106495024 39149570 242864979 84756180 908377681 890611929 71798554 33902020 571176745 907178429 299139343 351950065 238953160 936613115 157993819 718583246 463013239 447182930 199271684 622265213 265546513 481531789 454904502 643172087 155370373 234216498 631862223 802420465 866926108 702240039 579569429 100 767132444 708170235 363563025 794494468 73293902 577031593 938681028 401406006 519605743 691778444 682357649 204426827 774986272 482331127 976032019 204047646 856117592 128752643 92421935 367268459 916172753 759886225 416701706 536523335 104340260 784498844 751168062 295937395 128674779 448553227 696471770 344721383 94875097 507743538 823765584 575794168 963162444 209938730 800142014 837229867 580845542 38362088 809931956 399444473 942787399 100033507 231372712 189717411 284229698 690342632 110286015 27594360 503926222 875908424 406876214 597030178 557203868 210439558 40273868 319125970 468473812 92478967 710589740 138245526 512447581 801338583 736768311 501023653 471341255 756867726 16825198 938081723 254354680 389091361 962638215 236359814 277659540 640626709 665587649 468727389 269173379 45216216 930841032 843221472 320972767 549749047 455033613 123805806 311849510 707538228 652243912 189860351 545325956 861060528 785939474 627253961 147586290 138588746 202140562 587275018 100 650586851 536968849 4329215 75822373 444580518 426835627 783520025 482628307 693603359 367188620 39043323 545280438 91590961 282392312 513453583 198345468 50769313 584500637 942977569 34437937 476207872 615839823 391629546 567179572 958788137 824580642 44372721 469165577 105899422 754806237 724531064 693560205 507343920 920896979 746165943 45656708 222057410 197371023 178857666 499373737 167180933 652881073 253799686 446821885 324552334 555997802 105086320 402903595 49428086 759647787 768247410 323342662 931863664 328824163 162550646 854829114 890147892 232214 621573204 992030461 283548930 276119044 695875666 647750275 762395609 94115668 829325837 508267423 338330270 93055027 596363943 475622869 956586662 232230064 738434220 10273709 490511327 508968706 695181374 856182460 333157430 777275203 960070670 305177179 847358104 444452895 824950366 15117411 842870644 271816912 588471925 663833518 243844802 730183115 217480907 286906411 825315863 438352329 993682058 482499927 100 590546875 741190244 872967375 68859432 986318560 52058064 711415760 397533783 870311246 220574908 174433670 186548091 730756059 675891958 253553227 577746365 709270271 245420927 928536864 32952688 783603068 120647201 741683032 20964060 447192333 93628156 298443485 937291030 943608844 323318080 755379370 634209400 252064005 94239068 560878376 383861997 59106448 661758933 450840899 850472222 676629678 632770890 550283732 973173241 729834494 347192438 855374777 586452804 800141409 281530207 892183152 787852813 210623435 167257393 643060372 929652658 398484399 756939247 135424328 708836371 251378964 600128256 21150653 914972975 997001782 146788818 19625151 828477996 21910982 131270521 687313387 58052919 965883097 930499131 436792199 177122507 195201919 663527795 52304484 684042976 934235118 392995985 695621647 890874815 128419218 941897049 102463342 664456373 859704068 35471484 214532397 745837695 799474089 103191490 109369363 363022634 451210845 330051426 223793767 209445884 100 819477208 754693518 522016901 748193499 399458391 510562599 265200836 34344818 438517308 589440855 303686608 404773671 126009595 811830193 799584624 628727075 969692628 724729345 445514832 798930254 328956247 211070774 313214015 791837227 941996903 728027318 228595426 608866644 427390700 26174852 153569656 241384699 359779287 256578822 44166342 504968080 253148889 8013521 695019151 728152233 643306204 393116708 487150489 546073744 135564105 851139899 251005572 934647689 456604324 288511525 952675485 827524662 658442716 198194915 419794695 829947865 733514175 702563272 705261464 895293001 915478756 298168401 440483076 79628059 441615473 18767161 993730851 835879219 952591173 100685770 193059728 94525441 253159849 114905194 202675202 189416069 868347518 115593877 958288115 535641690 857721923 63822266 236466736 320633518 734556707 657534805 902454665 245010910 493256660 72327763 227026245 724934042 945343519 234063607 412458440 41343785 980787391 900548923 56503208 208316881 100 828988776 53678658 857749209 117450393 227853440 938219941 416633092 93294442 418286564 104329185 998542471 394971050 5482583 383817553 233446757 388923207 696693852 105804368 51707319 813623307 496736000 624014188 687418299 417292158 451452069 270030205 486980195 721790452 379172733 911115892 658831085 504728669 207994586 292670177 519675458 189583808 809179083 644282695 78195671 5815930 141010402 289966356 339042555 289786980 947528562 95553554 450025087 675335269 488431600 528788782 563461223 704119477 476223221 727733041 499668034 554478258 963224983 952548310 13070368 9671804 127180571 180224116 900979785 738444198 933440347 149714339 653785683 410372664 460687480 379846525 546705109 206727295 462930064 462865316 548425238 823479946 714522706 77067166 375759807 663167415 22957630 176764763 981106381 29100749 259161984 307143401 861770218 609813355 777346055 323613738 378179115 835809569 151512234 410422008 894716123 568511891 738888774 9268312 723562932 295507208 100 445475570 716769691 582962076 428845784 491716844 540166830 993538262 296496965 365984038 491972857 840264223 73843863 218050908 843268207 119168913 889733228 998362703 723844864 364097229 621788313 267112903 300802014 690158458 968801210 831194620 167280828 115714506 820341903 966995313 537930461 429272001 305041666 750770983 441643770 204738757 553118712 774699074 320197237 47838870 880888624 360369750 318523453 936489480 670068776 529355596 442600979 623292501 934460945 1301636 546371574 971978469 649516235 895319586 146494829 814115721 959294405 575961927 498905938 504135876 964770155 337499098 543264232 768187646 483651314 390479310 906580821 632204826 888809327 45088023 612375103 501100699 701767983 845592840 328505430 578341469 427909668 362678934 672032591 38283279 114887366 245688158 660958475 190263011 836693928 941313474 460165246 201796076 339657079 178504754 927144306 870265689 469986500 422014958 817512713 808032123 374494053 43753769 791444804 965803733 984041937 100 994482459 655495268 588225323 115654884 362067217 415530238 342199510 309067795 15047423 232795959 239775559 539881744 521480171 990359705 272533700 414060759 497846081 2601764 445725195 540947699 426133704 518579292 391427487 79208958 603027173 249471955 285882254 636265660 2866594 950421893 81657381 426032479 871234092 764632133 146498749 474014930 578191166 164197017 949000067 257702113 817024664 869059012 960354912 215084429 77926029 541474870 575599153 154667151 739335134 707553531 448211626 857704004 106275588 782495550 324131550 178939372 883955411 610433720 919802067 323611223 71848840 431097823 720722345 407021459 326622558 257111638 379022870 331263925 453175945 527061367 933250247 37077971 182613651 283956838 947448479 612106553 283536405 484838860 431395638 267150335 701312861 950242802 196229525 406427845 708658925 690364062 873394572 804103525 726339015 44656162 580604285 230095039 440003129 588021342 615607333 857098806 238487689 526926384 437329244 103832222 100 391914670 515271014 356983597 309036319 146401710 991909959 533403463 174279451 244907736 482443148 997098567 546203738 3416487 878237267 15523376 256106229 398777694 595833349 702771541 153978850 128694147 397179605 431386159 221131778 363298597 341105929 910764946 583303433 157920662 394164473 513209050 932047612 618374724 308294407 772041716 14637955 715126713 990760645 700416012 519858876 741551478 730987940 894103065 226442007 575142850 417897941 138652730 932906209 326945474 63696197 775919153 652120350 326923510 156371118 659766833 582274877 82690809 946054760 130401184 969558376 190949598 466551538 427912095 654413172 591294503 857064926 749939170 704217607 742774469 983737403 543061616 304440172 803286455 96719801 352534587 307406291 437554192 69091750 751446600 223696607 6164580 706786482 324981030 159335554 652569016 24696421 793201788 123405236 224773006 595466904 131483072 536342875 943570022 800890067 319735201 574805543 231296185 919903257 133497233 410401200 100 506317238 594454045 911384064 128358321 746375229 15060064 972735211 891059292 350443162 325029603 867303273 913284600 589067183 509176734 28438245 380506651 165111431 437434384 206858881 256908262 433999671 470333255 317243841 712937766 329211008 831584540 413664537 335033756 366870932 49694348 315291661 170160570 51475168 293287080 130542375 763787108 916193792 172621715 61951084 960799183 626993142 373624315 884634011 853718444 66295921 39702025 344644687 317560373 229492152 15293520 277391156 530255186 72721453 449595357 582909187 634760455 191467562 813111295 41063789 322243782 435247875 669340643 582650385 186826107 371235756 112176260 857825786 263385179 522022123 441419644 987107203 315889067 686785031 59952596 389833373 418429496 149311152 71087947 922360407 80592087 211764869 918504685 727269456 556970181 104484513 267896940 920192561 987651819 617967293 514559799 929064168 116506036 864484925 957871410 985355819 971218497 697214280 850099416 389914269 557516685 100 546317701 904562546 771078160 127566989 142116141 86813315 497236775 659640562 205656090 82065656 675608629 614290662 16362585 257511455 542062181 948496358 449371906 225783378 937685380 695779004 367741977 765397176 472336941 308020606 308109382 892731651 170035161 255659033 27219017 628005687 88231878 80302102 356537778 771187988 123040588 280465696 993888738 75643638 340034421 962262240 753979494 747935938 323895697 281679509 320708442 580566498 74735876 598635513 704399055 860600912 668848617 771753087 21562214 140602889 515784848 750712841 111920174 758432699 326638925 294706177 772040376 862886719 983296095 992318718 790091368 163616792 311248 875872357 484878473 235492770 222145767 646202761 246565549 670136630 888915156 906328113 446998518 248507742 272758256 624390477 952285057 725823134 808924430 990451664 819896261 288179649 601520574 664477662 890248561 756394590 461759794 302657514 863678608 127554354 15543456 532925547 991706913 796512181 411490322 131463373 100 473010312 225618343 152794404 261582477 117042359 57676366 771009965 240461143 826181526 511992211 469822899 603144136 190094074 557878155 646810547 501131929 215738894 167176228 250299331 31459514 666759516 746102982 832354122 44303012 134612533 428101797 861488813 887349563 430792370 166032989 510273803 199188934 768628957 230663658 888254730 203937519 824939606 423842143 285685207 615443130 988988960 187977251 329667674 579416315 469116894 290661400 483876127 765944419 994536940 419781153 522534740 242366142 91596919 605619835 561583271 552935486 644937519 353955072 81969842 965894799 254087102 848764128 800048982 296608505 215635681 156556452 319213599 729616865 898694716 951462370 375999912 103656803 407916058 487345871 185990398 123217634 435239617 267675477 141402667 35264783 343165191 354219831 885107878 31215621 852535410 70856317 868736903 116930243 376515572 895882634 332448683 374412510 22971711 283788650 827741333 132424810 401503739 121010762 979075868 503096246 100 785604280 595302461 473797960 38079989 63751123 744879447 563075205 937749022 146502740 5463214 640769335 251378177 849432305 460568247 257403041 331392788 973771324 18310252 312787449 935750928 716361743 326875703 477968174 448068257 144665623 629155173 31008180 791115955 770766210 752088745 134138758 825558910 3904714 344004842 563513839 651807762 836354677 79402195 411057104 714035262 828885677 970444184 663422996 230391133 472825381 448054270 331389600 135666428 51165640 893985082 902590166 50663144 487328761 698559572 838821220 418974194 996498546 992963891 399220224 203020051 904522984 587599049 127057473 737723793 309021418 325079164 233919063 325081301 453829558 542813705 313459504 173670382 536057722 202347058 902801527 210073128 596809909 217932434 901068448 298522342 444839082 922375265 498293355 259699340 775605479 62066557 497584814 480285600 468996139 968204216 141295078 383585309 682658267 723284591 746387538 850788585 581700533 705568302 527210488 589529249 100 389459027 254508817 390642559 240568445 409388850 316564048 813057588 917952128 811657806 957813126 358256939 419701312 69789370 662167993 139450976 567257043 525987199 594291350 956457079 806097748 386118374 902963374 884095297 370333829 193092765 136166439 123093080 982558486 442907755 967278410 708890084 351380959 873918974 160598027 233300723 399208381 130705622 456224229 442413662 396463314 68663480 195154446 59799282 212003481 240266949 347859413 118536061 45286029 586569128 425041318 468016385 429948719 549493881 333525580 623950658 841875953 720775302 567328277 625886511 135217493 657662105 724563839 982755925 561675730 929173366 733660045 748740195 678442299 47812596 73058917 61288852 526726973 424238731 477659588 97738186 822113746 471775537 884681829 61102311 199152359 369366786 719898117 290407036 605078380 334787565 248911966 611198581 961350878 112791347 135362257 257235183 172705549 423805293 232645599 424196029 797056927 747811721 744598667 741184200 276572745 100 316640884 409896826 128096886 655599268 239599896 853077768 407234025 110443874 611998740 87137872 713930653 359019752 448959077 162423224 454096769 188444677 794811731 675647144 620689884 729585852 216077662 372667695 366474939 302159324 341870499 927470896 608783713 339877843 19947795 292851536 264169123 742461922 613281079 711037278 668002806 380970316 664902313 193452138 157348165 855775858 996069614 373792119 353463253 919810965 626969522 138718451 434570883 233497907 622150429 585821400 914312214 529377426 570062287 333497231 339020260 109307513 370293652 71333840 450401426 15834884 909398977 278400674 311044038 254062159 395424215 505585209 416067823 233502452 413853060 988896744 27307981 423789432 678816554 475009970 379399602 306051937 312399167 947678185 161103673 321700070 209045829 631937572 720861300 657320429 500524482 791763769 418652047 704529042 105595895 422224331 538476371 8128671 637591829 108623310 59525197 817578695 521720870 384879731 93672504 522072753 100 61689892 633937198 104759698 371460405 658456041 875926749 537957745 801973751 745620894 547754500 880037685 54913185 517459760 310520384 113247370 662465028 89652536 756395733 247561551 560347171 465650648 631089593 784327340 213040511 138373176 458001633 995343762 644708895 29003763 692650684 562700382 583408391 91837723 208213608 621523333 689848957 357154287 824905933 719686430 149215002 723164341 861415250 113718795 800352756 988266118 893383056 18975867 582362816 504368387 227010147 101946020 555724508 2662974 210453745 225947313 579290105 430541774 211244562 560320356 26807165 222320840 882839646 422182858 783135765 909398845 588225189 404214681 240796295 865760238 547970896 780030990 897097392 516807997 301656051 645227359 416059086 717635783 528019157 89798594 119529322 945969331 562668444 820708940 885374811 514595692 562192953 582516479 419650828 23671691 430547204 940959763 310952626 954749427 286010740 321948868 825852948 752012533 897705757 630553408 680674027 100 711979936 328024139 765522838 649561650 641000979 342318613 368961 404579730 376257549 96172813 632286241 431592621 18369889 969431118 58506806 210993809 298187503 815446782 915517517 212267935 204598534 191034035 719428065 950636610 215944187 189173138 396274054 62082699 77708437 279652634 940379060 604897428 375300748 714652494 909581588 939489864 526223277 611017489 683640589 258887508 56737841 89373468 69899013 359567692 697641700 50324617 981748193 198853672 849320439 546202705 668678750 736185735 6645857 228381310 323283302 766540519 590388906 156501987 491572471 736666011 565424282 272796066 870453244 113036745 964249311 348065066 402331691 279010675 844073617 129654686 996896235 147902245 170892514 441614344 520724774 360844059 118084870 354191657 149652825 385987182 467764323 542255580 74901318 899648131 658699150 986791472 736963999 648815208 798280649 950091088 17255472 899223809 424580554 510905673 226474465 362349795 658857710 248356737 504789174 227535437 100 306953915 183057682 808780275 989430461 891768752 274166511 805795611 159562869 362569315 515449392 614748147 763458149 937106257 275741683 941888653 9674900 342162366 426879401 593532314 484028772 994846886 957335881 133797099 455146936 356161921 81784539 358177049 716929557 18158236 505885443 32557421 825041998 142115898 491694682 831846907 636285303 162221401 502896509 108163843 981721618 863122504 107037004 367070356 918979922 853819281 424313568 902095883 835558610 636225013 100977524 585543663 495936698 724179237 404027038 254004787 504178465 163187954 105718004 767117771 63321095 16426628 752416198 640873328 196389716 913616937 237632158 341366244 508327089 990785139 172054474 473091570 388924174 880214221 32364213 15736502 546567234 587550030 270844215 795566154 261386100 3244443 877539527 804059570 33312405 894133711 482789846 257515935 700280752 174255583 785261805 917951862 623507890 687545603 586177209 229952008 538629330 279964782 640580124 555283297 161569346 100 11291495 943142448 749387477 209365583 838308400 195660776 839341904 720604360 834505134 505950887 903596178 151439433 717267379 26572498 959937822 719710329 733106226 346527824 853429783 39263328 755053778 529175180 48908926 386276372 855688048 293233042 878029894 758343654 365297683 578306346 717519321 919215139 563968551 912400235 201989007 634327961 610588295 946712185 273395899 314671303 549554063 241226253 8480377 596912810 691818207 938044117 564796240 344686024 812427300 910234628 14760872 193037159 89497422 333929030 291255100 658830085 670216878 944076444 737673553 138472534 660531480 34654668 697967094 189220161 111459085 106798676 702125044 960471171 459715175 669725632 521742573 855303033 221020801 41640333 29799921 593432882 29716198 69068430 971981923 805892795 288336384 295203197 183573921 78184275 822174216 206469579 650104310 672240924 267034597 625331398 199595295 35223266 705148764 398637461 120871380 911482643 266176846 874098783 763796212 76251977 100 233082153 797524205 708164227 363771096 502451403 251474076 762106408 26320046 203133900 35092566 918616953 8845110 137888898 340690829 319357706 973667639 298395198 267715940 43740227 789444946 847742465 207488842 94773562 507032793 173709915 969627599 267272776 52325900 756386639 260268704 352708651 362831321 292255661 252221606 491718061 403554933 855284732 28954584 901840407 925245371 173996179 654728431 481223652 30050660 368225340 297163102 506162646 152157978 67869366 887110631 67034198 970266207 234246457 849266648 759142568 47047972 186346865 917271391 301458939 233020435 629410064 268446805 569567123 594757277 955403365 278170553 564122892 252779156 468953126 677237383 941721481 148788565 431754736 345273088 112440953 52166584 327311201 727981782 497107253 35379562 413695698 708261889 128299031 254968611 292903329 344345744 191280015 969588266 115698061 504602062 668041064 992557316 152955161 54685836 386157403 451901974 592543489 947762870 548052105 269659806