897 897
377770864 350749884 587358167 807940065 683025683 482717859 763854824 316624575 893082925 759709766 105610829 543328284 947596742 279990908 20711853 658663281 206064168 843684190 8046067 59197816 904875227 852860999 377099846 151957545 647207337 243755470 360139536 664024765 892362650 386363853 126777850 575014829 855924472 426462045 126384621 458962610 999061835 333278422 872555283 236733125 75776348 388503506 137874131 812940832 770280245 381643050 411128279 123589691 301562911 656707830 124587528 182664655 355572385 602304656 553341583 309870294 837298311 140809873 715423700 997484167 508182743 38689489 8729986 990120285 738268637 428123755 553331841 627008784 438217503 969614261 91075322 741562521 516490600 783837771 180311638 708656689 959341761 351540484 128144189 524195666 287703666 3235834 447380378 115007156 489565956 818705542 641491604 123179599 771894337 264377665 104245398 101284191 50688818 388057091 461854023 559097434 145320990 570713574 62475666 748266235 120944785 606736706 23756190 972464185 188325201 308174769 279813845 666597967 635331690 847211020 218453473 296767157 285167906 393115756 728249513 997347365 280053764 864656937 540956759 880687766 276644057 419535837 426077012 264325443 492849321 796863329 237942089 865617572 902664637 511661006 553124639 111438962 725572511 754591612 864906495 365592999 916797719 324107781 188238418 975534202 476382255 83633217 581462977 25073766 971924015 41424458 866601781 266102307 700135329 955006329 151143895 18582442 324679757 673648231 580161552 217664565 660443965 775185132 88950152 50966587 835817145 465977378 924620074 5329271 372520011 775641186 218900254 357202145 527589562 193935173 99795660 71751346 603142162 718171043 116514015 997688420 321071514 605493142 761811262 652230318 427844571 747347062 518746900 120436619 888969887 684209886 465938632 102587443 378892014 685386405 209154052 698684703 918009106 943608548 928885170 161026569 34919571 32314870 280046073 530995689 993734715 575184754 471408707 243822327 841030674 818417714 575431481 503478958 305742689 300431438 313088196 149697479 436281010 456559393 248270861 327634489 647712205 666199361 982585725 355281727 768874940 37478538 202862269 245188945 974725320 159533075 465195702 867398696 243354232 34624054 947685265 28161213 288332696 535318668 644902583 222967625 15729198 41704430 152523985 126018374 898971525 636054132 567323079 489494892 846093350 592556408 533860548 223847348 573907929 129464210 29640752 559385943 655975847 46374556 264481715 979117775 126516186 918664111 727860280 412953043 265890811 145063716 826159078 432370014 236933842 731864723 224618536 150571432 247820904 750558934 599747493 6625323 778988551 974921734 128922696 960523166 187766327 517898620 127537464 97746428 788238530 289146832 653797599 856251517 865679536 74602204 145804518 336658842 51612234 140980152 321285687 381524748 928145178 873415871 109808889 32391629 812604905 527121288 257381526 462624788 215372479 159992556 816279479 23905628 918696677 679430918 192097349 998871645 729432293 595015469 75995497 532970257 968639623 950094843 606881164 829516975 223765717 927041864 598622806 901548978 723014679 631459886 292198578 61785042 55602135 287339270 550459592 264446472 841060061 136197993 642532865 742930061 891516210 74820143 701526789 24210651 291260960 259625842 656253887 893211562 149256240 333787275 131092310 818353907 88374570 32319506 935814709 915369967 998071831 523704801 817376259 814975767 113823041 605049105 540038571 742470693 621492272 191648763 194870612 712271377 147784110 216491575 131930216 132805908 249253315 415118495 154830737 886047911 869748153 77837644 125700790 79927171 567624728 96807318 192300289 390085026 972895401 340668439 244873947 255096379 719410294 669471400 553857005 513159625 49522120 571693665 964114208 7285765 451365927 801388444 795030685 516988390 909404 130497010 919882189 215759783 114265201 985866300 75499865 750867135 479806894 349175954 942361386 142525929 662801053 393955918 306280553 536834846 742883590 90251273 875916671 579818389 360782322 431967643 854824468 579804617 355891628 746404894 316283155 292450673 518289850 479020523 397699236 114850696 930953447 93127323 758213679 280626759 459553083 1943814 510424671 54659365 946954752 878488390 562962203 222392029 407851967 440178867 372472718 842340198 76307519 790981095 285767711 178207227 42705548 468524732 324750968 303647509 153383660 786579528 790854019 34120299 647847146 734490855 754733927 89529592 911114063 761877552 398815118 911176436 110798371 973362429 211430049 381259736 244258480 733302630 181877385 903098461 775778686 745487557 142636143 595337852 93881430 805287347 816284860 339163503 443377730 141637641 157879577 120875950 267614090 907228895 139553391 373580530 960588216 930327183 912926951 877311028 61843348 351693490 35929578 395948974 41067816 115035168 225275425 871921367 344883132 423531764 698513780 620996714 592229849 672311428 663661326 231949919 473606474 348083052 71743831 646260208 683250965 813801347 253518839 467677588 671584133 470815203 261919193 894502662 134645282 428827877 771652388 619415358 61306294 372586529 421480259 23746677 75846217 84457073 303851229 110184484 74411813 311703534 12048861 664692484 830304978 583145456 687438698 188495119 188614938 76961554 951584238 388266877 440555781 847412523 363624722 780305607 43557085 134767956 57161664 33139878 143052330 740069863 82735135 899448340 882602421 186920573 454775705 525822793 335782280 96639471 346498775 384982462 405812972 55149141 874405826 470373420 315521640 135451914 260662147 901128332 359424456 354319524 502532739 1338392 688326162 604966143 387473002 199980359 504017810 114065714 424687651 78130644 811490766 78998935 893000150 6179511 351282065 304707015 35157228 43299370 498942692 513946266 400043021 279789988 164768015 721527338 185024292 474391008 21077659 396594640 282804056 658520790 664232786 542586404 624061716 69178815 399596093 743924480 371790335 457856788 878483875 918654333 411256580 613244559 260478224 103044596 101821514 523345704 587928394 940924413 61933371 12429592 538459741 993938034 363825281 83540440 324343695 820587371 138049027 112769057 919908715 24166979 653074667 44474861 76008378 4224401 215381410 585524852 547530628 331749679 216114641 842671663 992702226 763577909 768693345 927152855 168114158 174669053 608475003 739618149 418157280 605584160 581961864 869499411 279916530 751462263 989735985 84773977 857639532 862471706 337919583 674408176 690179800 233081955 270946363 200178129 420432638 249244907 28316718 281629749 810163688 25838474 672139744 790645398 967157726 306134874 396470332 456174252 654981738 508916404 164851050 91282800 667519060 808468272 347100370 50565403 843863461 296530344 324501791 867325734 442787751 209478709 978944568 595332171 452539618 533219888 35629384 709301890 670506784 640110129 257340086 593648388 308045673 188751378 786723372 590514762 479949831 761402092 193797780 488848909 546664066 763117847 965225493 866912583 161629604 764719149 404141081 844462640 55883637 991670023 120013129 867252289 52756798 224234430 665563534 459441715 32472969 434657706 699014161 8033792 799428638 539249509 506596155 662833887 866890759 182917832 459239605 678434635 504112525 639325419 207566184 608979196 668744247 4932136 761423229 650342635 21039313 984184344 504908893 834895186 594109281 51728787 570578609 225905065 808195378 269037235 444437601 407858856 403046605 152341201 455507608 385176139 632650234 456543366 970622910 72890312 312118211 518283690 441546107 638141849 12876399 302334295 337018554 105269112 994289034 39075814 305400226 877695069 71396827 829457135 548810654 310468737 726574443 281718092 280605013 674504541 387202948 1480470 214973618 24189355 390007470 196117925 56803548 424367458 143369395 607134099 253597757 259939773 616958619 409827513 927820414 610823988 979177135 260407344 334143625 561422721 348947065 80658512 791432325 690255771 285703362 662835891 582638556 854952893 131444114 749165618 296851767 501656415 910395442 488927973 876611199 744817466 966291244 928581158 254890717 266828103 157038152 648385678 402476730 660300992 754478736 367495158 522600382 180250653 81212492 728523126 98184404 118660375 705785094 344593256 971311652 819245223 342123910 141848420 505701143 609633542 634203093 111402565 518758485 996162990 55741245 241456674 328560585 858348886 957481031 859611220 243946650 643778553 646854331 795243894 463953715 415194319 550130594 753748831 272645435 782576722 439434566 216627497 823482269 360686137 37837103 635858732 744445056 405752703 361176103 333989635 69888846 10632796 355467318 436022149 845502641 741630025 796438182 916365003 617646736 801069568 336807423 204252208 923378197 696471928 438466570 410138187 42533801 255741932 977144785 78534389 77231349 706571732 879590301
127195460 19752844 792939954 596526449 57577065 596518175 280644422 41233725 508603096 177158499 7254756 437484705 652778722 671770104 590635134 87257311 720866329 15378880 746690373 799758968 343739212 394892506 41121193 643378477 189628557 706511018 527129948 288227838 421435694 45227982 792274254 348028718 628782526 489790505 153197489 574842940 727741968 116937947 997810166 906581482 598052148 819107909 127569613 103727161 687781242 23642121 804595752 649294442 798123637 67877639 241401655 533494526 277704437 951098720 500591212 563367349 70416139 676750966 279294839 737512337 56911880 447171817 514358602 408203987 397245566 153386650 19099670 361188092 430602300 274413227 120553291 862666445 459504724 367549308 674465179 559453255 649936664 114931374 734563574 967919274 226106391 666174755 862617230 964443256 254587428 275391227 912674516 684618098 954474830 53337495 931350904 717948569 924599528 14662041 352035179 893007918 600480130 10119393 779652832 881349041 38955245 773685904 595560262 835472357 260725306 674708232 594562382 583032009 707107770 502928873 327192298 674082719 172710142 810044948 851663178 870974184 294537943 367544747 371541217 490434148 862216534 393496078 577402717 155553046 750008781 157374942 546793906 580743997 258701515 469697789 233928718 618858587 15630883 24268427 664288229 455819057 169445604 297810153 276933094 805348800 26993505 39663545 823873538 251153737 805666602 909066203 155291500 884103756 565451536 637170032 971197586 759250060 813987620 401870297 458907432 533530888 995707575 727470520 192706589 102395906 834575962 384281838 770933666 352085754 233393630 878386330 568358185 207173811 353528404 941367583 667968867 857387308 629874701 429877277 466261056 625017768 145256603 667849334 14893810 634520742 382576333 788877898 953100777 122016744 124872374 930587386 669936855 630480494 682042277 429559591 531263149 236234363 53548077 163449523 337190299 564333966 7491614 40683199 401612562 15290986 980705417 310089642 9323461 369967374 978548670 83115287 200746402 279142076 506728272 791103462 819410909 900758004 766160400 379795513 411257061 62135929 110217229 241774447 451948139 77090634 124359321 820802092 656502626 465792169 525767749 806910030 321737720 34168856 505623779 920868088 405705121 363768917 71257474 961169034 542388491 121556324 945779829 851668646 416499754 991830149 57911627 835922987 368078381 18700856 883968215 262148412 587287430 652911167 495401257 335107898 46431205 504410523 195324818 458390725 662464060 421856397 124097699 576790462 818614971 539795606 895718445 370937158 527125716 883361910 940465473 599151039 361268535 595490351 699365424 145049801 207396310 246549251 671571083 654533446 49771490 61685616 903895331 140547413 575165387 82776890 890541578 767649369 252588867 543325537 210317967 194387187 938121019 30443557 16236869 472800003 921795555 417296137 50474492 95632298 154946220 352537292 755995588 928712009 560035400 570204016 554520816 962935170 667573416 969184821 810438416 656545589 811012860 365695902 993542389 277086851 616380854 425233258 20984496 96689870 606812807 824655516 484488594 733500598 282545247 627340659 370048044 904483868 872769391 592457585 580074576 652113442 235623721 254696790 538292493 507142952 232597054 676549925 679043253 715066575 890971806 495622173 494827226 694053881 40939899 856584385 173288523 819025094 657489222 16034512 496978203 174291095 55658415 126900555 890732186 485374478 232226728 991047797 353197401 724002059 618157409 696165326 209996073 597507759 158164556 515594774 455022362 38890844 768025369 545478991 93246336 105989298 119212474 604263098 39952873 324283794 833395040 870334680 905865511 28456478 87529595 633615210 43934539 410129334 988132028 80847728 744165799 154685179 733720854 899835693 281064138 341063631 546900408 211919392 402872454 784008018 869156883 471345931 821498861 228664805 112941273 807876591 964861775 987928874 593719803 73509388 318678076 251813377 135097513 332701157 64037767 757541003 508244 56409913 124388672 656364585 203272623 169964298 212750520 593494397 881001129 837237145 26347136 755279464 753102963 918056039 178919017 768675849 610156159 47737396 658002821 781206723 656187262 242111747 461654051 622946870 408565600 386795539 646185429 181384516 482438999 727151078 110602605 710823949 342980563 620369469 906268922 470091250 90086534 172717593 316636111 359027604 63139425 434071994 51810940 228809429 330705812 445395107 853580497 256220373 622554000 728170899 132200417 106061814 196900616 331553420 751453180 10785240 657756139 322457807 190337715 669993308 674458474 832053469 770906327 298145443 651338231 251281014 262372473 555952911 742612803 867312797 371070699 8411968 79174718 616258449 230318268 761297176 521297177 572502228 299523006 803735991 852971335 291015463 559503619 55422846 271604087 2218122 1925338 708472846 435363226 511381568 118833878 274996297 100227810 278359240 507582407 519018063 724784064 580062692 507849149 618691458 402275812 737348245 543982603 246291074 465596992 719681820 24502593 909869872 418916100 782648058 831994672 115964589 690381730 219771119 812676841 186482523 826754763 589925630 528449726 273300698 130327663 584517734 599471166 995906059 853687743 696953769 488460859 783052560 952258862 237730952 958045383 67917641 15794794 561094659 855456049 924824920 168896103 670260317 159808524 84236572 264986964 706750741 618858279 45000633 81438882 440225005 206902677 351237005 956522755 873077734 203790758 409814075 689270376 172784449 800014059 94849699 29008385 718755198 733822517 795056358 427768896 855007328 485791125 903242342 119594198 821953766 473452124 306140611 430660275 951428434 246320411 283975390 6097928 123277605 827878307 852971225 267468872 288360736 57527558 959460884 49717793 630108995 343163795 970238512 353582983 54485201 740841692 424085519 720130473 974616137 411464627 112091089 245320440 62908269 406236200 534341847 365196582 298458430 565604235 389881795 344863012 193940477 156999279 66279029 31288098 810564906 626688164 539520014 490092690 690030983 89733947 863346928 52993572 344355606 114398853 216602811 364919242 713120022 589587475 688158800 315994805 242905609 689184438 733767633 646534485 492286383 887177856 813343390 289091932 768846603 447258816 733241176 153059770 176394844 59445769 988372961 434530977 104497956 35732522 514356057 843349377 128604708 913901110 472407585 60454668 794252125 537743996 148714458 669736243 927025168 661532303 444295014 763255078 7090877 882131775 922245862 725384535 921608998 949027997 149923257 985352054 569134668 138598394 40796802 949256821 529480304 269104615 754736929 309865604 931027731 370226741 629606584 421277973 382549238 402793461 786319271 608394457 463233049 928480121 323569551 657105856 327118783 124506192 397104978 303368444 193024615 863202124 529751312 575876861 834146771 906903679 396143146 547983221 625109763 659969337 722290497 827493205 884311610 953641994 70080055 898847437 773555959 650386117 442398764 465335631 82749948 871659130 67372930 496015755 277118283 306855290 445877209 273452403 544319010 851273558 251166738 177824823 136657669 95061727 260862030 586985033 8399796 928602150 109294063 70926170 567690031 474168956 777300373 29258842 871577528 985822323 491595042 295482747 262869712 191589850 657343414 69561389 860059448 340746179 315048370 964841250 719342321 988183168 72862903 760429642 209478459 304566177 563771303 333277911 763842713 450606070 672705186 705329978 222737098 34437010 993921290 795900195 880441040 453928901 615469950 648625540 122392812 828475680 871409122 593777805 325018270 14053236 979149652 475477936 197879465 125269970 86538295 256262558 420757772 992711819 761555499 359429191 101031689 504730416 39431185 158570204 558047009 245017747 322506251 24917968 960593173 392271043 754733945 964264145 341535206 62046483 941442813 927115987 414929876 354300946 619133046 35353605 295854177 285475219 817460999 777157080 22160975 245675174 939068177 464482559 12413852 488205723 364213300 17137512 702380428 619465221 235437393 600388167 297574047 646159540 62392457 82173450 852787861 169704889 948859198 522606181 729505392 23736933 459960848 958703687 232787058 26193738 439508704 861568993 101164569 321300535 24470224 68637862 963789353 869627966 577183296 683376452 420064930 642462129 585316049 122364335 791893700 816600607 3786085 47672598 465858321 674181211 597007388 528750058 530272074 682052212 133456983 712448989 380204144 949379517 875569336 837427680 501718724 864238278 184565023 19012131 224482246 141678944 304689837 738828312 506166329 164892828 705592772 154499695 979661852 770729163 834736644 769345306 489649 116417406 754284622 299462474 988785273 644429190 335896260 901137775 918964021 949692148 308039878 775315259 219484133 711607578 745493749 952327070 557741259 888944775