704 304
933248465 610155946 400291387 84073455 66229020 847152534 708553616 446003404 623413279 69663668 277653378 876766736 684795071 441848824 201869672 446299853 276213595 27694868 65505338 601966989 441419863 262960492 484371455 764889440 201150483 73635110 89368171 417971204 845181501 828353489 960781887 189666543 699028402 974330385 666609435 16961375 266544413 315827129 525059989 80184974 834216953 692760951 21740556 619277411 796163658 870250032 172454077 868551845 263728525 475765540 223028095 26649757 488473270 618563018 709469025 651614573 675742219 376960706 978045803 138901776 840766349 723484408 544597774 683327112 180058253 352225080 829220431 632835043 408502815 615266466 370453397 949627059 138964445 150879067 71422558 258673262 918993433 342562583 56915529 284275434 932701498 813556335 61171164 628295521 301220886 759027013 824610677 758524065 984771981 76851741 846477601 438672706 435810887 290959601 456365080 34008721 33682934 491903968 890284951 942236467 204592719 430659473 13918434 742635309 566419116 30356784 641989311 872005096 263000789 989752255 756032353 347914371 525968487 844384427 672074486 320461011 522518269 729252699 44059038 141388790 916391194 163872665 438951235 14656941 82606603 388172067 294661843 480776232 475000221 784841077 628327742 91672278 781112435 966801848 497381532 314800472 19403299 977833489 869133157 496361571 350468630 295493646 221598435 837862668 419786455 30492276 311392056 199254581 10880419 789127276 632758826 542669751 801951637 949610569 398093223 360427849 635066282 195581910 881423152 293770326 371527682 996642851 537657531 406286135 626154405 716979422 483364215 865305542 14993633 397363497 253980720 231883301 510288619 145313046 131595093 585695742 44035324 296405525 443045996 698269416 268485640 696596138 861382473 912727566 940900846 84256518 633858916 270410717 883293391 336052711 343049049 832549410 98274639 177528418 62694339 15070819 272754696 500077382 958481436 948124478 50827141 894872516 446934261 792443361 892130390 683936011 127358624 504829281 587778505 274169772 590921180 725855297 324280353 941877096 308339140 58698369 888666340 627960090 372373812 279646049 785533649 745766901 781543391 813674773 250168874 59818395 556142046 441281379 207105675 200412020 415631734 727520550 870793755 10076753 443860599 392240564 266314985 954185633 839594659 529131595 248470391 91894063 140067434 544783468 194359063 669524057 325181832 703731330 428925496 169664453 215248386 408718443 29117977 324822093 759444050 430002109 348162296 661447865 556777700 277649955 625947452 671579103 278828366 699010254 587628305 611193934 788555598 917416167 573268365 324397071 482358416 918961579 713590820 852899635 384212568 233192063 532711789 797096148 332922058 800389288 162300338 145479351 544123550 294300229 402604411 874692618 151626467 531173482 263784448 609719023 590872382 592518979 428288395 871687079 556035380 386170992 709267996 386741585 498013103 23824864 299737941 907598394 909322429 568963442 107110896 988875133 305115632 29994398 765691005 913660169 279970849 457258304 303444821 858862952 260279085 692289208 310253207 745136090 112960068 507190489 964849020 616146968 270894656 320281874 723625524 505855034 848385759 815921800 42169958 124447302 920048195 138691688 507097535 261788772 752321957 846415098 195629317 690913200 538402900 330722346 630683949 84930492 450322750 840791463 227411026 486414843 702290149 544350008 894452579 735963586 244726143 932812717 187166760 656658620 747812529 662672746 326075109 458158583 491709005 12322966 357672804 598698577 216696550 328102195 188701865 331424581 683445598 997179758 550852190 999545979 646681723 404289478 275247702 647142010 845778572 402603286 664812915 785335840 928235612 192507449 983198900 596403804 321894860 928092675 422377745 949917503 278966136 720341072 251747842 105294555 325374563 21574582 905845926 926395598 939431193 386488421 304646618 24089018 882941075 302425197 976907217 11589715 584588734 560364505 67051846 274387940 201644587 374354101 127661030 643023653 193756993 998862156 387210213 333811039 205565619 857112839 738384663 222774428 471278715 137901843 946258869 447670648 276924840 658819172 975737581 41353692 154709876 803280073 541151658 898090432 595093549 383570575 272881904 110248506 46281656 527633648 940429727 236952885 520635749 390466824 969370453 511224464 132783491 641117192 210882851 86856471 301033819 234044880 786255095 312809204 25069836 628468269 920818012 165984109 471301723 742075556 423965808 979884078 909965164 679563280 496225325 767721267 134208909 52897500 292139673 32618096 605201029 233907753 193796058 156745871 52325308 377287002 954918259 827062404 486518572 220145489 213787280 521538730 82399321 792623288 414012617 998788320 416156113 450110215 24916972 885446379 649708578 189549078 392325629 336624053 605592038 907546527 373333971 859148281 253026173 59635327 327657815 316833724 886218621 95208301 596660068 368594036 575585498 515979636 345280261 756676381 46856474 251949389 180165823 749686996 912376004 477633537 963674328 876205741 810147988 74906660 178143136 602218946 921423715 756470719 752394200 670425313 937758651 280894218 124802261 801169126 373498137 3286520 272837902 758551855 182673556 55567342 212030175 632608366 42086338 471889686 162526140 643136503 463030465 275042141 301462616 171620249 606509787 154471894 724613291 257287807 371472158 838830530 533295979 303124858 309286304 747638425 867344574 73309551 844713057 355847500 369846928 702573479 822476117 832989485 958241908 211494591 405810229 650449468 471190408 911282746 827324935 999210708 118940640 432298526 389649838 651950270 130055928 959191298 846867525 187404330 411125317 290209521 98170473 395439923 212954564 375924113 180611872 532872996 160133568 593316709 171120339 796287143 414871935 318732439 989220848 632254633 26183354 873500538 289074214 795165667 533438332 237756700 785301511 801427672 135391952 820001775 767265233 159387455 918873709 684687501 627521689 435152698 457927029 784269141 159605169 794806784 795637509 241515257 225722563 74916869 206088740 651354706 562630574 927249293 576893717 671418615 9500731 246038052 678582140 459055310 291827775 296661705 640072102 549323460 565881640 877963655 253439562 147731805 204411369 555201300 43348068 608559914 838856391 544739004 451832473 387557090 32443809 898423184 904549705 22878234 527498105 53847046 646341568 237834247 537867913 239430818 638167208 590534089 467129145 14850388 38133565 681560217 141843457 127182643 471637848 232393110 863103480 366905034 970935088 998208702 641336896 522427253 927763886 447171049 997837476 799406898 523411682 510985208 265274564 106962632 601468225 677300000 640546138 280448551 950941020 967630583 220062509 865423756 593857601 251511810 182959631 818684961 74664171 232940837 546456515 319201608 218256863 384085302 254945214 818483529 563003942 232426034 369430054 523243120 433407570 816515920 127678518 130690165
694661549 958046746 99886569 361447995 637884464 995589837 668813130 997237758 558819017 194406523 501336311 288761032 923690233 790876774 826804634 963098922 273794608 813741538 839145560 148168970 325348677 140141113 242688679 162672462 129861197 502887175 627742972 827466831 429216823 859528364 148617965 893362420 74306761 636454214 41031196 514487453 918793347 205255202 796334626 259806167 158583854 130250286 545246180 663784839 341388196 847277826 559015354 534602337 30700834 543208267 160114736 923817629 555134184 763182263 439099460 451965443 686937981 25302899 824269186 233666437 434375838 339259410 775773262 94647415 152878356 393130653 992858877 982287033 612505191 950952660 840544161 156973223 385203650 935386225 239782652 853560871 76200553 120268235 705715435 422777541 180541992 30204007 960480431 911659543 51510731 164438006 555662794 297654521 192510066 241287415 190968861 311754266 393768639 146907555 344498276 332696922 963493340 402971229 436818640 522775293 880504142 115462114 370311188 319312447 220729246 871953937 159319109 928773263 694402813 466769052 499504528 240053717 758574178 563569423 553484163 675823564 158327077 71592430 493978717 821783203 989452408 208132618 926246941 489262919 935250899 280289474 535526953 675894670 164689233 671489878 58139457 676712921 774475398 619325521 890058405 183114099 898361717 914257825 298193992 988451631 329289162 208088945 359889651 431602833 476474097 781194677 695778828 981244021 883763824 993309722 420873668 254014381 345939206 104192798 462206293 223482527 841838609 373771487 460572369 416658056 117272827 136748189 467475779 523869749 400241700 449467341 773578340 403221773 571487329 463848625 607911762 692343129 461975348 39118058 31551110 161946854 36985417 971857991 484522045 261952590 506268474 662990428 975051978 272051776 634586099 356781518 358223085 152434960 272446211 246658530 997157266 971321570 983709427 51272126 235131983 792578621 983305067 256795471 737350096 796103107 663787376 899771330 614285052 312043307 906996307 67143744 448867774 19759470 316207968 730732756 896365733 553804710 473609320 778460563 850846911 628508600 141369711 22827791 261389585 6724032 341619942 765138291 738587361 359670030 640040856 307478351 349803200 381178784 817923450 539507501 594935469 63696231 311843375 792461819 350557082 989824605 950944153 601906107 138976076 857714487 43058845 505811608 688573245 478842764 766350113 577945220 291403892 646945106 93819741 844265487 470242249 742935068 778308002 484586748 894292987 457602268 274503689 824994650 723963495 427855285 667729943 281338553 816430710 213455158 545745845 850756999 990275735 509214550 126854495 439528706 784290544 524439527 403292195 817030778 625268123 521007981 321467193 241344839 455740189 608084437 775632035 776687556 1457840 892718832 57250990 173877685 677124035 269875314 835383620 220750548 582408145 327459204 964324060 220344182 629460009 201554488 206082489 893316198 793247585 210781214 727906757 76815724 928801526 849777337 684092104 488607479 206169390 983575769 294752116 104444137 150137734 447633875 248540589 897416988 204338527 488497112 371934780 685568846 566146778 918330959 15755649 86431289 810349010 39467245 549516725 503463212 635390803 400299907 962448909 207602721 14090640 759264095 582021930 883514491 496160393 7829668 7300225 431887072 1669478 869079022 333564423 477458353 344669808 520394861 613715862 546450706 349888250 357803473 116310925 414931828 431365961 347998543 968991742 179854437 120384752 445116549 690996984 652340213 841286409 236734905 53352999 993864476 32379434 954154925 22933628 936373178 983962185 496462306 191762171 414689536 297549051 430630835 494855546 695196564 416902638 213918948 231793459 760022092 101092952 543033507 124637310 1289425 76514742 496174169 326741107 736091344 395544104 660625715 517893954 366754777 490762971 204102437 380802145 452838617 676439740 892958486 68954044 16390394 357049212 251909462 807395698 857058303 138521410 484984036 650162583 29454864 726999893 952964642 480867658 466422076 632940020 81402390 661163923 220561408 844298898 60716435 179875754 167016790 264091600 654910250 625652456 929294390 401094388 66055930 866754317 410837840 876897871 334800676 491625841 299929922 649438032 244001653 786065065 27608428 761646743 144042524 647466900 497727223 640000048 669041546 753954992 85633642 988541917 967464634 970851996 450844250 535564531 740286987 37358027 715059880 212642471 949922334 468507853 423182621 420353096 542164023 216214125 258744173 358912203 308265729 665306756 802478561 378261631 250482566 984782571 443261724 82193074 730991537 987506789 469819528 972093685 993117005 903742088 648737443 885804798 607076700 932114867 830775901 759442929 465621591 694217451 705428402 696950218 400795208 648519443 704591372 898974482 342694826 224352239 934242946 489069693 704199593 94585834 276035947 175921828 926331391 624455197 981673978 844282765 860666700 190008985 528549095 761201879 213008144 858317731 675336513 495166401 556685847 609240174 403851133 894692127 484871994 16438815 681073253 389026015 756581906 327388304 892091386 62409931 25758268 171712176 285294391 605300969 399711729 863427890 330441662 289027298 961212445 221535770 904146424 101226780 324108124 44175966 856329100 328913256 718703163 74821520 475708237 493555953 914918416 394339226 589390559 364462284 674581420 466382324 207120502 204224269 65559533 534163349 598127530 899057668 1076845 325420513 375802624 932596327 264268664 332958253 935320759 418773476 85409952 247447050 476968951 711437434 222042764 539215277 688040480 578884047 457748882 614010610 242727424 655012288 960977473 447027920 262668474 315097629 12078772 536180988 885646044 685976641 751827878 640542399 330087521 158348259 170865431 85588242 32256977 730844021 845213807 946235085 908749117 526692800 473532346 500816485 820544320 958951948 127068841 837571299 468519240 30216851 36377788 814250320 293263993 882353031 301196335 983377406 548253415 907819096 105330229 884259744 470220114 258681175 571223900 246479964 472945267 410179336 44658067 836659110 171016759 16059762 554949343 407825243 651432829 70614402 965539725 33248680 243580183 675875985 3427291 512458354 677882968 831838564 755544850 527643720 726007208 323761760 373135408 861122380 810713021 764281435 832728605 341293348 893005355 509839499 442269871 419767731 252013206 709038689 491469057 193177712 306821880 816757788 652992890 452933499 244066468 670046793 186022112 15082358 573870562 10337282 678743633 577654235 173025106 661247328 964848613 147529788 687996096 14386866 365646280 625148903 174446757 524339121 215369267 67550270 105073495 955212451 520957048 616258160 216581978 49872456 576400760 66142560 616876576 751691700 570428198 972890696 883751842 748565387 436159047 672910954 132497503 389543009 1656508 338222275 655570581 133632291 852997220 599158332 702424455 632567830 699924338 98825905 855289229 719205001 500345340