1455
206423432 307315241 102472897 479070986 121358829 889760410 564044186 249370828 552997901 85454846 90029833 728718356 786067817 280615998 516777623 177841473 157648781 421910210 308664363 833297813 243973209 30540894 123757947 459083398 143688986 855793472 434552701 121054587 76270804 463024513 669106534 497136817 742249185 310865424 68719613 857260145 775541214 517412082 37253326 630902896 966641685 234763801 360432577 966557395 336965070 431786874 808357331 985248916 200514716 419482985 816577531 976327622 164574300 488854309 655160651 164201445 206776122 665509389 940660114 520304285 533310907 189822375 399137081 803247049 57511869 440553917 782138372 618067577 391609694 808692733 754189731 160018456 196671976 945146355 765587242 255196926 88571510 314805128 993529775 813877287 465163467 225496337 306567834 761738104 731339956 591922436 914467765 964153526 909542871 260861081 692991877 915269380 609372052 709878170 987481366 194915244 984940950 853131388 663933010 634857485 105783499 174404488 42570986 977741187 7328508 469656514 590763000 957624263 659304259 304179857 260335436 294147781 855954443 485835391 650673992 473318292 399418874 698987932 223593685 622953074 867358564 347610013 631183277 345695526 352042049 294638031 150385026 390785579 844951919 219524878 951137797 126473026 234564086 892838163 365452812 616786494 216942181 940637502 992441009 553943780 812837504 877242445 851402084 317033021 820605079 838526331 776872649 670153099 914486350 248719536 921464155 916810888 21660719 98069438 932138472 108080869 805635674 578109747 503272536 120707034 937792430 516473618 111986466 169972656 654467522 28067112 200189086 912329553 355184703 960678513 269850368 592915547 296629287 757069215 688478373 30370384 294423608 400020594 4613609 385810414 619665262 32607852 201351766 756780937 360121908 190267791 162379455 261505242 155790487 553205297 663364267 230693151 23938426 555544513 951160320 340882790 379900652 246674301 782868589 941314294 374327080 713573360 26322836 73683506 328995800 361331416 803162108 333681832 465864980 860058386 584100616 709347248 425319276 291187673 456878421 498936027 411353378 374916400 734626049 621182137 965173468 565585963 570640643 603128790 835083391 43471698 669430139 958664382 671225549 227825076 206929482 531469654 786729701 524308818 115449906 276108408 727683094 463662582 409622783 787240680 178305363 759035723 912491351 819610326 211631613 832540377 604925897 757261830 162872431 946693358 111997765 911663477 246189731 872140796 960901376 501179372 13428175 319436311 626262472 298712867 294983603 52550387 105014544 771146086 671351521 306572727 671882486 398669657 849315708 987618955 136968526 897037807 592062684 796658639 172626800 227470086 398306251 736599948 991877683 478661951 529520244 930654239 968203305 215106047 800078493 954007792 713727932 844981510 953639299 726522715 38151056 913845018 472980247 547136228 993681117 525040063 528227592 52550010 396502164 44258386 850315706 558598180 387651788 413313794 101391234 49843180 284283338 676578582 384550630 75657871 432141372 164514685 769411632 274124927 437727892 804945403 68447833 349475901 633129958 226035400 783990181 444934516 282035027 688789887 240478411 502816084 782571893 85194365 458866969 240839443 102722911 183215924 138317922 960786644 209478241 969038404 629788990 730388242 353616396 557802236 563778004 370979923 743547756 444683678 774067095 419038010 337868812 558413979 610317710 533164060 676459942 388922194 965099486 767973392 883613810 436262812 427430433 996063207 270712238 211822525 401436018 600210680 538491066 263452309 632152978 702424661 244505458 439388379 74847577 990627490 891457321 958856124 162553045 927682574 225777024 256698246 718471772 419450842 266321850 205293844 556247673 137535449 100376351 51154550 356231433 883098057 280601512 126432327 67214581 829467431 301071827 18784433 391079349 533258213 552581555 737241923 429125898 457296695 482292492 149949131 451918856 797691598 531196217 601461405 559645836 34718387 371835930 626259465 379673154 37927606 807734725 747732034 719319728 80867271 785953970 661377844 911846717 885641582 792899777 33714016 751897390 731924299 862897926 879877679 224101971 382505557 757435128 210372656 143328754 712787499 721209877 5193642 626417532 51932102 519064843 889164391 872486811 283624900 179781555 207529235 790722736 68512233 614432250 52039471 946821725 114169769 998500604 104078241 351582307 831189018 321459465 293044143 238512671 61078734 916374170 618075855 814380978 498822708 195162712 688787896 311792626 494441864 45404116 469298850 966934215 870985465 225863108 823158940 87328761 469829249 74913035 923841064 410247467 277143293 461840823 514313144 561244202 238219038 800575331 904869105 672717458 787430905 294122374 282172906 271003821 517594044 675848838 400784516 956479059 174147953 889352270 714744725 387048291 105410313 313555769 267300045 566527921 376865804 506176339 405063785 462373098 392041488 885378371 894998739 783211256 664921220 226479401 921624236 859669482 740680942 343660595 149702461 67555480 616741877 189629128 866508177 705343460 757001474 51569358 9647224 150587736 484529129 490075426 165113301 208300357 111703499 729697479 455797553 668296622 393952958 799284947 659916996 352094733 51411107 318320666 416526184 289885440 46631493 154211776 99865879 80457379 718242294 352437592 515441059 684440576 321570369 312521852 208408029 479844528 131175869 588096282 975490994 577065845 130803858 446985540 948896824 877604949 447976496 40946696 340871952 498058072 442555613 415612764 204817368 9396665 740467223 453243290 67373385 581684202 512986645 530300226 507013251 161172007 854329964 130329852 102210508 102962921 18998372 68511331 32794530 351520584 240242619 660565215 535509685 991440787 553766119 92708154 571975680 885387088 599165254 926417885 485382304 888874507 512329588 855126965 703150096 815740432 555805745 400780552 929260495 446072987 713864428 780229609 890936301 628740951 156701369 30816975 793640195 956155284 136665896 637875320 146396119 95402852 269760836 829391471 517122750 313489768 11176353 965836179 765227802 877143515 931358258 111550655 474294551 321821808 835307344 926263005 939111702 419047111 299253036 221631799 654807795 598138258 360132672 345331445 227847086 391783710 401451628 512849476 453081205 873020802 540093855 606151761 446842548 121008150 77186552 684619568 42022018 842615235 80718041 949820999 449192602 70110989 684290066 41753292 893313480 388797733 124873617 267929454 855553183 656596883 424819470 407248246 123339916 650036406 64368078 423613684 906696613 836091103 995112111 158039623 40470504 92481642 490854006 789586863 507030046 165149359 4541720 259294205 296125169 458943579 800739983 833692021 878960805 332932877 493562450 578265920 257760360 720521959 86827471 429996688 746257493 443320811 989773008 332609188 578188974 271431970 144615623 30497979 653000321 125006936 895845987 789800482 850356552 490110452 824777266 137628207 672483013 813853346 732365121 596384672 756080262 501284215 54117335 729564780 781715639 606540033 963782506 877362872 253728882 354249054 651322384 34638879 337047149 857353287 548751719 660666345 888574575 190768414 372990624 931299546 19047590 743480311 692308498 270862744 282404377 34136176 872385320 893734982 576406839 398163963 80387112 544225957 724800343 287548661 254538395 746719056 926237522 419256498 180261928 571362120 171994732 110084113 101728092 908006621 521695019 337191433 95003885 455081152 954663574 782453930 315274480 802050029 818920167 417256177 63524640 984387186 556718603 822512098 161786138 3067212 141853000 125524557 685058642 53597308 241066172 328717520 852632546 431513616 995193180 128137539 278475018 636294350 691269403 990472736 187272564 29162898 718959934 48446308 364261012 906424419 159528420 592305678 579471307 640182680 624754187 676250798 133322676 361512713 941251992 772608964 954158661 692507673 89250570 69786407 576630759 396571116 74306609 695496431 82031201 137624385 510178022 145601222 592147958 869150360 27427061 47472694 468056275 475816350 440933776 796773608 905225852 691314325 44126631 20369817 745495327 239044977 647908455 108951705 153299116 267434907 299411071 556196709 462442507 103744766 967527981 610806363 583643770 27888058 621633341 458022256 566017738 114288291 277799840 836788633 301426225 899117804 782959197 93929830 191303815 346682380 640670368 849235992 955808978 335352630 247368860 885073895 965396799 205797044 335876590 896267945 587700195 689218421 323424676 641763348 360735681 600503449 1626778 194684440 940743130 963500294 103170999 214740503 690610679 133546625 449998700 43605203 120858652 408632005 253679331 75089288 180213605 965928000 454706844 400846237 321317079 612368760 759883484 397882575 961659673 294231744 577869652 92000184 636374375 335615672 419913973 14649501 594612199 877588539 325663466 705044111 624408547 314348217 963319753 695580387 977143621 957682331 429806860 796658275 99491866 151484639 913376582 873399503 794915684 411110955 171401079 95575333 737972290 665463619 818949305 932134116 819250934 895030579 584925106 696006048 197741533 814056559 443447373 340097642 592629217 319840660 940910716 511609933 999448266 170602250 755473053 272803832 511118351 443295013 815874261 414905596 295014127 481728407 181030008 999150855 870058712 971762106 150670724 92338260 751822743 223346005 864193817 932357628 860850731 223233018 130338693 821124628 396485177 360115332 893035940 415238898 373296104 458818163 612365807 193959555 915309910 906003511 217809050 453137242 546923156 773220286 264465887 729193876 903778749 804356943 993474582 612345778 834659743 875906505 156812652 425362913 492563069 342735537 620985211 863795861 838645802 271667027 547146480 550969109 155890223 278415155 31123168 805406231 740564068 505609599 836493423 422825127 922399062 296283690 891741276 890033730 160616217 772518134 527646277 628620244 630536656 934452062 686581375 207667984 806100062 436159540 117984456 32131243 176413569 862134330 950896072 986994071 187479860 2722736 678369729 18209692 372439746 624854032 915439672 101495491 535746819 505565756 643232213 513445925 248225186 211373887 826636661 85534450 189001820 373076321 796699497 227918893 624630535 586355386 81992308 305455751 834852381 415687579 865272269 223883724 691947061 543021069 438853283 46847694 5829736 722757284 436589182 360725576 297690538 934699318 186427944 676189259 557086318 776591719 321899080 912647310 138228632 56022224 44133808 760072308 790746182 798973801 796047681 192126180 371639699 937953165 429617005 525408734 927931890 724441736 618879971 131538616 399702416 107978500 491165718 340644093 675830719 146850707 863959722 390327080 795370155 168125722 992454720 11486342 214002790 754697968 543076206 830097693 423219494 66877675 980100466 78647986 703212929 376310322 324437683 480375168 525183691 745986009 667331903 319240029 195803971 477411019 469997478 839150423 626762018 118518295 825862607 556432223 142088161 909127950 872964783 719948713 161236158 443658377 446277073 465426361 83746075 919643293 60772612 722439965 800748833 489114790 221228649 679261169 342095735 99159201 98521178 13734789 780703846 438839365 214270821 829898764 703101988 656205007 817483647 319719009 223649246 738485662 553357837 958071661 761013561 475893679 128158088 146589025 960338120 198237100 527435852 138364563 38162965 268811750 223470140 780386229 664176516 752856221 740311296 940783800 850855924 501143332 528850552 240821708 7440382 728634785 946830514 250070267 222043571 13528542 11443230 82366722 912680746 637606265 193684075 502001057 607821827 183905238 89481055 712442929 941664495 351956476 858463499 63062665 195584209 244563390 481662757 364411946 246362995 344913150 325523125 966117337 745648070 434328365 329373991 809046716 574777706 885959187 360947651 792222003 898919898 969635707 329772415 399819375 217925660 156817500 380945647 914314443 761550141 14893825 383074085 984747209 16868151 391405559 782218553 560874784 128191608 157087006 887352308 855990246 159742340 763864226 626282994 920145079 176491506 445790818 148457318 733446078 202949520 143823276 73166489 462675888 872869465 425566133 994003124 880701049 962121592 73226731 378537946 514228519 665529277 672889617 133318941 443514686 130419729 902122394 800006140 331994660 655207972 169919070 756270851 178715284 913289755 112924776 380421440 228074712 322336594 640397610 433882955 917520228 355510230 188392055 845846044 142461090 41148931 98001047 623544796 680040563 427931587 742502483 834261023 607100138 886693886 367213548 38227403 978793155 128364276 590355389 209851711 121379970 586775553 971686034 262433607 443088499 734282007 339957112 471832816 92051752 961185943 974149083 838524212 682235184 838475704 818212732 282227474 50550136 894043895 749576716 858247779 519637060 890381892 420484320 755597708 881610668 718735678 996759434 58232514 170494884 404818254 248996763 249200471 890718747 200215859 420372012 456751576 566782539 942931692 424956945 641262635 504388655 314129775 552349421 808444917 807298911 430966215 275183467 420855787 629444888 631057948 603216019 765340552 342527504 323238009 858166616 858852953 81847241 498249019 610249109 96155253 686581992 23904975 913470737 493812417 746992006 833805534 219433256 991876670 257251702 878259311 571095585 675464992 54064369 930356216 774712725 710127754 646489717 720705524 281106658 474980713 336848045 362162529 179294065 149101400 483627488 165209941 844336888 550820018 41048805 198560964 826119567 283359065 893161388 975885957 934580976 112548591 896275134 283449100 626843000 835984195 119115105 855598798 89439133 593940383 355888333 440462862 917332864 448249649 806744614 608265394 130586325 378117201 10618175 923153593 606756422 722925788 96490376 882550066 108845441 232719655 326343557 131698870 729921239 235154372 38361775 542073718 649517096 411520904 408742430 979381026 737417501 661868905 311366454 336322192 537372244 460006760 204963194 236731896 390348541 718337767 561091579 885203525 135748211 769020053 310266678 836079141 568427591 494592952 754863833 282365761 65182423 73877571 311692330 315088856 901065755 373419132 139595377 235749050 187997589 295990872 174339414 365186326 34668366 978572073 968482639 571401378 541090848 414950373 819481583 150330401 432746925 948111899 366099301 237646326 815654612