844 456
215433269 591113864 936071459 437477634 929321717 618375913 693257644 612279819 88077360 54882376 41790640 91614730 467999726 565470245 537721704 70519141 453820371 12869677 874049677 920946049 660016549 399909261 889893606 64795382 580567084 28233359 680789670 368364223 963489268 269486143 971803012 628337149 763264757 559452660 223490556 469052987 908317457 844557211 423143121 384483636 877685697 204643968 124663789 69930265 236200766 658206719 830471937 84579940 767372159 7665753 634468627 416862229 410461092 704126210 780412711 336620546 773473286 365111470 587539783 52632517 20565059 746371946 125639330 844310016 939059726 914624992 705744939 643078177 264277183 456337166 443327141 773356890 312774017 318512107 326117673 369405237 554622494 968756630 359182089 210565376 755593721 432918263 706073201 896398368 531509121 947112535 165173267 391300330 517337294 721627734 265093238 944611032 688375453 511510725 632666431 16483497 853972007 147771811 997479266 522861449 973409388 279822443 848589876 845764195 470016257 580028324 216447752 676038166 529683595 280441600 991504934 334271370 427048930 108828191 54262205 750351928 747232521 507961632 530980325 90366517 907806397 841943586 347373929 446970494 910615509 775537827 423559302 151475276 93896532 326149173 597631729 891156591 158952800 71770719 679160554 209240991 324390619 332927753 396275122 252032964 353268177 400033285 367947533 647282743 908639212 432242225 61178831 13770340 204397740 682927348 749573529 8496041 869659307 929723186 764886299 48597830 156945239 192766037 379437308 89631673 363522561 944700560 683404755 616027989 98775646 846829177 397579283 77596989 410837320 445014222 882271452 64388084 736616730 857439439 729372390 603140446 915110295 125052655 660287033 685475754 242667403 518363568 833777443 595285617 405293910 56802145 254121592 307455310 557625939 613543353 678167503 764878523 192533377 882154573 13127976 78207277 233729826 306219594 535496165 984325260 760453921 24992681 248625919 546066223 508407593 1121103 278779741 728206165 35930783 758708619 364455280 622199469 313983798 10148654 916641646 579416553 652782497 923315227 593499606 941258858 754311492 220345919 696584147 771326895 271381670 796051108 156845346 455398220 868135664 220121290 162637419 543452636 180776340 620819654 258744301 826231155 468550422 744950887 77216980 460325617 626885030 282969853 519369273 678389063 362366003 230929518 656706486 478677309 612288003 111448821 505819489 100536217 367738549 854062261 896624574 385470440 186380443 218912665 550616638 823350006 809860383 346428453 813834603 224923068 429771503 995454986 133974756 833017343 277630024 850341233 979008649 860049906 923060878 166822948 555692951 571153354 491933795 808608207 146300769 904009886 809952171 984053376 744203574 92427534 805696783 431298480 326487723 841183415 968841676 91763327 208577807 336266303 520244240 39580843 61762084 917855794 203764654 659562090 205247088 168183682 87474243 302244223 413368872 782448164 394912330 825212302 728856610 543433666 31146785 617812442 649735724 679250709 876411886 841124642 3929430 662258749 645781442 410837240 138299611 653304017 277133543 552389777 469027897 990265714 49328764 164004380 448560881 966143235 452151669 298075627 970485513 43855334 388612633 897502942 936487828 208988399 759439749 395599685 409812343 162474689 603427251 311343102 271126397 734515666 96166669 979253426 370680962 350915890 194924906 140094710 36090892 145378264 919873372 613732513 764513530 18374132 688094910 589436124 190657312 564783333 971897952 212075352 162513952 128098047 118088162 209623317 850984174 824028798 565962900 471528668 43773500 500632625 831276604 35622923 624299272 57683852 877613929 67087041 334825245 734787621 256170884 159745342 543398651 715577566 997201298 633956170 352479346 77224456 736891518 388367102 187717208 22694714 379741670 288735255 613118031 139171788 179141522 909608788 234747620 218775340 315562938 259259825 556648048 433612031 809653489 385403588 246592909 170263835 140796911 828952275 217401552 778066730 228197939 627118877 292481947 885911518 109183935 419622283 7613713 378841682 396075204 327260710 208215281 46242959 301590633 434999239 403526032 141520352 518298915 480126607 245273200 929764176 914534767 874108802 854937543 791358556 765980819 638111366 913730811 799417951 561190436 344907824 549919650 170647713 506685568 128829487 532719173 913258705 454464110 165304819 940019587 676107303 702496105 891499306 778519760 526953083 439684393 970792735 931339766 110911492 167675879 735960832 877302628 642720 233972005 652411148 708036920 330884838 25540664 126482224 114459527 774907803 78685161 203808390 155979339 360939210 118408350 818030190 75108261 132660969 122971246 318340525 581024287 698306116 253456267 153212489 724662182 278068729 204023278 660258157 552348520 49233000 375153395 690851800 890736810 512503036 450668647 714734594 661435995 935109518 919898958 19448968 555948616 77571875 809999789 805044160 441361449 892982082 306571112 100093122 312314480 679353444 882073154 421039034 340396550 361186522 167911621 283245784 811640046 240998305 810858681 639834779 314477511 97941132 58707283 276884631 229747199 305999182 151860676 648718088 204828856 521025860 818155387 32728932 44607216 817543912 931820326 965617124 545408545 979808511 236176885 303779371 825134893 176015338 811899826 594394983 672681076 642919385 352544659 428049734 871814261 678131960 22299004 159865669 978004616 825549273 789866807 16221229 987285444 261358506 642811487 837841362 44161695 306036227 182593689 265621768 536800152 421577249 149842377 974729805 101599118 126018632 567018747 431006168 535379578 341039202 877392837 456976265 719268565 361462466 947275986 205497630 894267653 54061340 665976544 319069003 368892686 485706466 306916354 205243750 936379930 916977084 308258870 139411404 468514538 671607863 74371332 741618555 884223819 989426141 471085238 129844652 423557466 568006191 424285930 541433092 850334989 537588192 160539933 439804866 52134157 85676448 556387752 488286002 803185691 897625172 625678865 587870531 438389938 937301234 212154113 807135404 149640422 640197223 799502069 573449897 849946853 451524049 877542083 448030033 552672322 215009620 287209389 233919396 126568888 176331594 543045 997791651 168529609 127227307 656186070 170040306 932198604 47873633 705666802 170836138 935819696 878995211 428486891 62699571 235077340 536813897 210451490 968480836 433099565 963884039 286326485 663824650 463453358 677587380 333717695 508026977 692140621 556081380 836663342 157019738 540393041 6275738 367059580 848687870 201785197 208957860 788911604 883354450 550349941 706138253 449282417 797420529 235700765 465758354 418300055 733957895 719426323 638305026 784227120 660077726 400956859 26423236 65354644 106637130 468838746 650825044 664833235 450353439 249654175 711258109 839695137 855311758 651929349 345877159 979054210 224290157 819855010 843348295 603838692 236113152 508823545 5522797 985277525 168458642 444851656 295021793 264520388 391265586 407270540 973420018 671984285 123296213 662786773 934375913 478996632 12360902 840809222 839252536 427498113 397575128 545309720 509431361 15289771 475395674 197846493 78968421 259515206 686616226 481555592 845141163 122118631 637893495 863993926 163438390 710677600 476984358 309979475 738028974 813029801 993945521 533985793 488709326 568706929 19172852 233698388 845996751 267937545 271886929 585932591 932410527 489920177 515354178 506609504 557717081 564368559 481885731 213089958 205844988 226948471 389130847 446470163 919942045 21832795 836469435 311108162 694511616 43197006 533682804 49759128 145675322 146028712 618806748 988827454 463296196 176739999 496554822 494241815 452990445 251698103 733720812 157797942 171578427 722456215 99092615 491302742 649939600 688785643 64072772 802045685 574853763 864270298 64766050 979463013 180617899 217202347 965615426 107648283 451146018 213160005 279983140 292957240 852133343 725379225 494040952 866064741 956701620 674387406 912970974 931318812 171945350 367570923 333747791 535335662 502770227 477432604 559182689 272477519 341668484 598746377 744030469 700110316 493117064 494741385 843565889 411641249 801635762 848756551 994843815 75370033 829703299 198216292 95419125 120399579 873511759 706720268 320122909 78503733 672961868
292420538 686954470 230731113 312345023 211305753 590270047 362276004 605504242 844495029 616506227 615679461 259882404 559554109 159886580 682230381 896957873 467982175 154997087 379897263 897414124 655190924 568778625 673192425 636483476 890633859 387876597 36328367 503031931 461074802 790041301 874506573 649271439 408144257 138458096 383166666 141293536 848695059 130595276 436541568 551467864 86691670 938477472 734866812 358356205 847799948 630744924 651123890 151435681 749307856 502290154 6773706 662122463 395295685 212089297 488564139 512068823 775716085 24773267 55255477 62475892 897240989 996169199 733884807 294307997 555750879 515331155 452825765 619664212 566314417 228851521 751765790 15669674 979636540 378311601 212117145 769755323 94164899 253690080 306090989 854437658 319980923 541079412 385088058 822577987 645247373 241342580 393406528 180979595 835250868 427966221 130646888 890610377 815507680 446692413 260214075 932269882 719909879 320902211 31978477 963149450 731835684 213713888 324642846 583238344 801589062 949785496 638571618 883213308 812205513 831085282 611416183 785146188 16506233 575055845 755871212 971015255 606868981 792983828 612774568 369784193 880656232 404215477 11618872 706479123 551845808 110289149 193647913 952366976 838689869 340523792 203320529 582309739 344955784 192539791 668552005 500876767 204349566 32178651 462141276 922477403 21659449 763891519 176230291 513929916 45263450 364733571 268779864 996358180 787967399 685487787 134475778 635224112 251414088 841222315 12102335 29399008 305406270 267327329 803844 278922595 3382344 722219605 978022131 981121235 246906346 599355373 675329157 384642628 533708046 200651019 156835419 224895389 165685743 681634978 223551842 152029928 236722816 294470252 995212812 831246590 692080093 477547423 897400935 868357885 727283160 651812054 173998875 567575795 621408270 915273742 634141080 85427972 852116003 160304947 822601767 246232453 202883252 763915867 915845861 73188895 325874075 664633618 701186697 619780709 777519708 902921784 677030306 856065337 736871490 480958475 371028116 514298558 852333976 2851935 182769439 574792846 649336355 237974555 649229595 980784440 347447174 534308427 437869312 769323418 472939703 791447570 655072238 210966350 594293599 19811313 350877831 152090752 299755950 870155731 788701147 449498903 386683837 616470128 118100436 97228750 463094014 441210006 807752197 626519095 28899447 980519052 851160329 620840508 943672160 763506707 148807246 482537788 894120132 929493015 954768617 909112915 92407248 276819755 538637705 836891111 645258941 392769578 581905083 46921957 364998894 122756783 248033053 426478876 80828259 571002684 539241689 897174425 431591960 699121030 470904219 999327264 341663111 628594181 474476562 859671784 280113384 221899101 333728157 806538116 218409749 703009144 680649983 56737172 569994501 2857472 955007587 321962676 182099620 365860326 263852242 678066849 557198441 310569506 364894951 141184859 590908259 479338954 235048893 381502854 578547932 129815482 554251818 603156482 562098630 787955327 75441928 582693568 823388860 747772111 27539169 908466052 626360143 563750419 496005190 559861495 107068266 817831279 743870373 205758676 593912201 175796503 416546444 571152045 262598891 450631238 598755909 950284062 994967743 258985824 196090144 490747125 696860771 662417253 280152817 564415537 596721334 405160537 202892844 178581950 137416160 492507680 620538136 299955837 970201668 462813769 210097784 677952350 193387221 812815742 243690177 431448361 622674906 616616413 748974126 980226750 826395249 250065914 729855672 246849689 636981979 491338855 446290685 240658795 886807881 353832250 376733458 734138378 911727035 101259896 125526340 658950937 361951192 550191773 558269738 170090002 481229075 899595750 517806616 375764416 184152794 649602404 721821033 4257276 866150077 46808873 483042112 196274698 968289891 567888753 130799905 592722182 800915151 770728440 3241596 289224845 137603373 870710279 787899862 71661722 515642662 938522769 443181641 684684476 756997389 809225353 239609058 540333456 296899523 817133393 196198888 159853565 565984776 588991430 909367317 911239375 674836442 366528784 785208648 589520527 612616666 291765371 593577907 636648386 564230421 426706034 330487531 351638346 832201604 357275782 584566310 777459269 596755124 546453980 271502675 688299959 371309889 280084079 80729213 143972431 292932879 683948869 606677582 275460421 18989369 179422400 339817884 21598582 96211746 182659621 809314419 872942830 239766221 702117636 142849507 377063281 589237130 501438200 659442039 420833682 689662017 181305558 353478328 491413708 518953050 697026225 304276035 794848019 207054869 565457563 855434152 974430307 764040335 625604083 114026927 874272465 797630524 350008091 560826065 661724420 855369164 800995995 610876508 987779518 608712559 204465890 986621668 840005596 261324337 941459418 461523955 599327114 580711354 389996684 325386086 189549616 865952201 260634600 922177294 774902676 371296487 130733927 573974110 683166356 384478184 385267097 133216957 906253380 308301508 560849930 616818611 666111314 8086662 348601072 201761360 268382346 895499128 260179990 273004445 555232844 914604954 552539051 779868984 474976195 597452174 956362766 30552026 670861588 620116655 959145336 407751081 729100508 640059767 773694623 777708070 286844483 835451116 938000454 210965377 287323981 5364583 642314714 81650673 38830613 270297967 183485146 626475643 721564507 166906843 339373844 266012681 775964852 123790721 453259555 276977337 328136687 291324802 946915711 51897835 902594255 109887560 985396480 444319359 292112904 177893790 798905719 480867638 395828920 96780270 638785243 57705692 208037913 470065193 929844019 597914281 121303264 453171779 258167498 352768472 220524612 603328891 198421362 431826109 962176096 937182803 736127065 50287863 117621885 664949195 623595946 476386311 687174796 618360274 476297912 219877097 195039984 247317073 458966658 535362687 624733924 865558986 167264964 412947332 523478938 605943824 129933818 345117277 628818859 414537765 661040503 297385232 680342188 11944013 324006264 206339248 245595910 736444564 287147826 510193472 621005478 545349049 866879482 862165041 138892159 411150187 550753232 874583083 28522072 801031466 440928728 100794385 523220021 850172814 812007315 504162419 129794547 876916609 395896167 4843306 187806357 347398630 873138661 114651203 968061660 169095709 204815650 771167812 121291670 743781903 87016109 923963007 342854409 140195024 189107327 17891751 495389001 56108187 320538042 369524025 976095367 53731390 152863904 926515684 632465929 901776259 547343655 740654778 865548879 592316578 987683735 486977950 495742303 42253523 165251848 206568940 27966928 9241553 474530963 436261436 373177564 538451016 898887177 831402143 25182710 315144849 812735771 754816895 164434025 84131007 588888149 117519591 737587036 984744909 818667898 268985125 430276847 445738207 320114826 642334688 491013877 533093396 728107423 136369971 149035824 492753258 267439842 79746864 931961583 374432366 236193181 66541226 763738910 382197293 58652246 983673732 297933362 521011787 779034032 978896104 962701876 281494961 795469647 297921265 498964306 503624490 396489306 217823177 735221108 988255059 651708217 174262258 28959145 595091310 213877123 939474908 575457598 955601009 171120742 899243723 997484821 576470608 497533509 38847365 755545203 101413934 712129919 442783295 454249929 37032311 226286653 683262144 632513462 535696398 302156704 573782329 144861301 665059336 231000829 174421169 421004407 582446500 594717894 722619715 329258129 660220212 290060716 69116977 570004406 680833324 843657049 980271207 636336922 142872827 554953982 189691996 570696484 779641506 203989531 295287245 241505054 348719099 371084641 234384602 2948460 255455902 632570342 508031324 902662788 888237374 221176080 466548975 615210640 516136675 331087341 431347404 26728113 928266294 518582720 554964522 289786004 87589102 901617937 428925048 555868578 261314903 780903209 351892297 988289146 98822165 60332470 509633992 54502498 109819172 92402776 574795946 979540400 309285663 428327293 234425601 779894145 877573756 76861457 59901574 307968962 453324881 909845384 632377533 341434650 161395968 583370865 76851595 441986588 267034430 877012175 591386522 739689638 278133911 47607370 100722671 361497664