1348
971656466 936991836 830049406 40043157 373066467 602263839 173973571 913458976 832436993 712989228 850873085 755179436 261044213 639325672 274411716 460442394 812099494 611662973 394737720 853994594 606796034 10181295 715410362 72449439 652317052 681741447 332184988 514284797 744613250 910382213 95294640 305556125 467407345 172943511 644417638 513914409 942680961 931595536 461909049 5774657 466504222 7732950 455641126 889218613 614086799 763185968 482389391 209067843 297366208 967786829 564377377 28961888 947296012 813184864 488839114 69485974 527826597 198044996 99463919 439687317 495526126 929916995 94683167 210036195 117082863 240690506 772162835 675122379 646434394 62053285 895680028 964255201 891995195 165909145 493503077 552100182 309003070 45328653 630725737 75087033 997952221 832070593 201561196 852829330 533280214 968438026 607172856 308616421 692547705 468076009 255013012 774275277 679015290 712873241 990069427 472957836 470051216 620788454 640841428 240646909 53394006 724084269 749785608 346521120 531909091 589303072 827975090 847581008 670183594 59835046 611375017 471405916 516622905 393204745 507910806 513933090 793816523 379204636 848381813 150976280 351340402 158169005 716130737 527805782 462944188 987890731 743353969 731443360 629087334 976129420 313617438 376809675 400577175 296289575 263639910 507209978 704007809 941482783 434509473 448130444 287424031 435331987 307817958 10426068 642639295 202216146 824835056 744078182 943324346 19832954 102299634 994822341 51236280 449999232 339095800 962256297 285998067 882525518 394081493 852246736 546962932 261363249 515509975 450646353 543736222 89364299 601192426 921509048 578933307 394293971 435393111 552489335 471741172 985546831 146349683 907540714 103127078 982376882 4024264 237496425 517181496 343083565 352280152 424109084 537504699 319632105 474997190 873923555 710990776 707007413 444715028 283852844 394981511 9683102 73699865 888925815 159451930 117623248 494663392 754801843 736540207 156765923 336073756 495340952 433623853 407854223 205267364 597562796 719067464 796987166 838709512 146384876 301861885 275372422 318056965 647877513 839235426 178926575 38022924 319877371 228372868 146104811 880775738 159636642 299343878 791858645 452015333 806502364 816420770 15543746 941149140 300747346 128424359 490012196 594367686 620892423 954650870 358775244 296041825 944554151 162508899 112977094 106786366 794480188 512334217 896204093 638424237 449409661 920047090 870173425 630851395 64194121 341754337 268191532 721678446 611427446 900452154 124920897 6661915 996582101 414929051 170926058 567460860 423271384 167586194 758492858 953935976 868249137 181434350 51660538 181486945 208643528 262504483 322526847 919079764 399683642 875332338 816801805 790424010 984096379 488812903 652607206 99634536 253053414 534463668 767943557 216379082 913977083 182626513 583891878 68804497 157061978 330452651 741022905 639752189 517092292 351800037 176608542 375420815 79887405 259179405 610025682 418770157 458811364 69047499 527828729 772705370 265055621 77779160 403431497 530393053 92303298 596716584 189707378 879364490 969273383 2401880 975338811 30986500 780536365 741030612 292104553 466628437 161733252 629167922 760634463 92947403 520824044 459805217 358452819 546520904 864970839 394901561 836041886 666983931 853035977 253123068 425124124 728843290 488718980 429116058 655879056 618671021 533212565 75485979 680315329 119735808 882770162 34035226 881539247 842623548 851450602 904292499 595213167 408451575 256651250 604017641 937235832 950218440 101481431 929794468 554233236 396945801 813057414 139925810 640143248 571331216 697742660 646926101 264005617 539512770 36315562 807709625 409523653 150359979 40336381 121785768 371908326 850044652 549812190 777543511 937428924 687167294 451488595 267432439 204868442 961658220 849910113 81658623 686006742 158103213 829777077 440662299 206286368 780155230 534429228 983036660 982658602 544627015 405788064 347550296 765026248 645817090 957564812 784243069 254197505 65086538 526314438 691326920 625141361 987848115 691667499 310699276 162622325 31745463 797136241 705501135 444454655 526721243 884048280 909544923 235426384 83837764 794210073 589303076 949660940 660060361 729109548 170557763 689210719 564015158 192914581 205303828 768683553 314095854 84487846 131771297 405688557 547824117 493824312 491312249 61627555 131638296 988416717 193919949 406993351 351779316 363407783 138623667 876849004 70541059 227307020 769162305 48720239 173241324 842400682 702728994 243939747 892309875 404736417 791083724 407397224 467838192 41042856 431757643 574704389 753977385 737394828 58344763 989040684 729298163 847141967 689903213 626659059 239950525 214837438 859805896 614915740 229414971 771032285 436598978 732916095 829916790 279030570 30152443 647813579 238332890 184330290 451652376 726895192 345529616 367545270 109458049 812786520 916527941 903668779 577892637 99539435 106670361 499172837 423646251 635402204 677056266 892780023 659774891 183929767 454939123 911113263 808903136 223209120 857512360 179475076 412655817 739230217 682279051 680699557 687641394 796055563 587502160 585465150 137135722 72328907 10394833 483856949 513334902 488299730 31602578 31765560 509135614 133644331 294633511 408997890 906859335 843158067 178243122 805287111 903371716 532808583 700096333 559213826 178874030 40751280 301483234 234691241 189907357 73801769 245899992 585483158 533046382 400943851 875861096 63117458 253357709 599702008 168813978 250113438 790646573 758043595 428244515 522479529 89632726 431444877 271142995 822901337 390707173 71259510 157378696 461488406 241431650 78989121 938702339 188828955 941218725 138065723 990282188 543553327 33202012 280312892 517922129 671228944 969854965 954826541 697960280 330166309 842334442 830645110 724592710 733507589 748054461 758578262 334207618 469699811 861178023 133320426 874998961 870790566 611836489 606701847 873078196 927696463 750183518 192018022 41134750 655976931 264824920 31536098 966622893 658933126 300282320 519531816 19364852 605126036 711076909 493174893 195912236 860312754 602802387 322733923 995711872 682251889 969803838 16521264 273616634 37239592 684279095 799010026 294139540 285363299 87287279 75711796 260889090 670766140 30815080 202222155 15901 367916486 778337960 249568716 197783286 772922894 645072452 211209937 692583382 363623123 375775831 383575061 379818963 998294765 913086961 666963142 724497362 820154262 558964064 140256480 928848234 906224720 743318818 978229852 322657987 41523249 669942316 424250775 13270176 852791391 327923387 55007596 219413759 18104045 166295072 48591446 464572059 318817262 983969751 204557072 174882162 471400686 707811650 871339471 920894621 399485105 938735763 921778413 39187303 133165905 843525343 919957561 630812271 494741794 720872837 963512976 644929240 345697898 662610402 842311189 647712395 932825826 712246229 192436524 228585407 925447656 670860958 468689088 55678985 156356279 223437444 444432395 536299221 702857551 499212667 593381969 452229563 59969774 620178158 285441134 497416665 639903638 658250613 110893138 168167689 162457304 511499890 217600166 633151255 463635597 695181250 726420660 963419817 20824341 675849634 244470532 752094112 407511830 602626292 612321019 244768085 957773303 515201783 346173592 992643417 719454849 909862195 352995172 808614236 187940115 536336832 287631394 656008583 107999337 628091678 22156768 106628869 342370121 265854030 125252945 177714112 794150929 45206754 36566747 988353140 781253405 552189558 880579343 168227223 156464820 99260492 211277883 268895292 490826455 323268531 4658486 613156226 701188048 468847156 979979582 321083773 249242451 423356188 853318621 326149210 269087165 80579615 496464704 150588104 234760683 520559366 925012251 158779673 811174856 617216374 942086273 670372859 293585459 107716012 431594257 410113681 276675571 295082974 23984498 883161126 544151930 498960426 796051238 311955270 3494360 40446518 758038324 292785093 317506143 498167990 285106181 132499227 691292772 402106190 311752944 458380984 113554733 608024054 309049759 455165801 824975438 80908945 675720281 621009464 666649596 680264381 161098086 106941881 90155826 930565669 183541670 974220954 414370826 489488216 919536062 555957706 191207430 626246236 999075224 831680522 609486285 814646968 127738261 746812693 239533416 173273459 104767200 321187705 33516820 744438162 970203878 522045537 342557486 492210902 887196244 697331591 329858325 453829708 47934385 674929116 217959939 837617777 616287451 615920530 32673143 518029652 885872145 611378483 509897285 894917769 912013073 427768179 736166433 602720518 106512708 414874071 306676098 277298423 43085519 175585678 124105155 55990818 844421047 100906960 654392075 392017162 823476662 999979910 502908715 569158069 282969318 770871653 259265654 574254481 670383534 204665510 755160139 58615627 198220568 503340987 815617357 427617397 88509050 827311608 989438385 39568525 162524624 19897065 89626510 770631393 253283391 733833098 816935265 664213888 245506596 192238129 434251948 889619239 755536819 58492212 697120280 534861059 751499505 641454390 706469455 500123439 665496726 307428855 415085246 414925786 325377182 511374907 707246214 665356851 751742049 627700831 813646166 204390340 606755844 438480181 750136421 463878731 429723655 952198761 385360182 347345974 563111215 286008192 879584916 437754815 54724429 337355383 890926272 102916366 906598672 931014609 597416479 991616237 933427574 886838986 871887061 613717286 428088377 471893560 683717326 355542545 465433985 129739370 921862015 646385376 132071516 47150326 229452978 950097947 628758375 608464296 985179924 694333801 762088221 562010440 966436795 95410921 592385060 773730529 777888369 130249260 64560007 796855438 799345897 779266086 994706547 763838752 712479397 350586358 257635705 534802590 378027607 798016263 428489082 121760793 438605098 833481660 744923676 290811809 827690478 832460184 250644581 351813565 617534491 279565781 509683575 441963411 729965181 599604216 515632509 80441002 27971341 118050612 602259495 775980699 143589317 400076287 801359486 47890376 71623009 353472404 828157448 876062700 271679321 677734356 86877371 346776154 36918758 869470064 11589708 370279906 713166517 497191828 445901759 15358219 489212737 650085554 216748768 956563249 832245692 962891372 775882980 628763790 441118047 802324407 744123311 573661964 272607554 636758618 884100393 59752441 963397822 273724742 159039167 183594275 500676497 576769468 813659212 978492106 710567666 770461105 235928961 178917185 490635262 232733444 972539430 396689543 594851013 142009770 136891627 816803575 362478492 918153473 344383264 379660561 644199646 247470380 703538635 650911163 841702521 121272240 986015914 643207960 752561750 154452742 653777 104186165 625603980 515906434 433874971 197322901 800821490 451238837 380836418 655220077 84476081 534915297 513761649 727434469 703419817 268428684 835999451 90286814 147072397 78158525 222578930 202488650 946877584 778211091 336048157 593748629 474507919 860274593 876474418 30368143 40962768 811036560 974595166 118155381 760617580 51893778 499858811 255317125 189492058 797175619 668039276 940749898 507650701 403269653 886765092 100700355 946356756 746649604 289301099 892337024 885968187 42703547 180560892 555953109 1736634 118610264 785302214 664250360 713229708 713661428 532648904 101242590 770149063 27820075 322623089 708110821 177361233 952994916 60986033 14171210 273539352 210424503 113527345 247082222 373849907 505145589 215495474 209413946 338542189 152175588 58166775 599554063 861481833 221279975 481196662 266964452 572244777 32423414 287020784 255993959 902202756 670143518 342884827 633217378 577984414 175766197 269283994 197829716 761549315 816957673 20264967 7054777 825295138 250198893 262342893 666887998 729204746 151524346 607148826 561582611 497937635 877753922 858609114 885955796 272601187 216603254 363501857 659467433 816024475 118656010 303080081 65320433 897465629 153126087 522293166 233919832 119635055 906339760 408737468 186207757 277347270 221740862 746668565 356031049 941572233 244621264 828342230 948793933 82707008 16602023 707054703 874072814 63454900 779335048 802041271 886011002 156762087 212466869 255488137 92012143 643632192 457192975 62941374 158316089 565047730 467918209 301414545 45962692 995025034 333545881 706479046 63011946 650828435 736045399 658372013 605065643 142271238 386163143 279825279 131521576 501571101 39713599 717829554 443762544 626418267 893772602 554261873 665844753 303204179 196598190 916753250 943841119 402963697 399632798 405759787 97198965 764467250 636412939 942535879 475723698 60973233 179993367 541007373 155155490 381981785 118621571 431208597 635263298 313926217 455500840 564382919 891931844 758665295 926631344 589319 529889023 710820097 826646451 536387199 26356692 356842208 273472144 37923465 868144449 487536666 7303447 433455960 619530871 768022503 166364542 769591114 271187918 686763034 390572322 922117920 408571741 233511962 749548557 271265231 665479313 970128221 128621000 916472424 868152987 39635114 779342385 201441071 500155142 969246457 971350408 309709060 221145311 276830883 348281180 272210776 337650489 883824371 39949509 114922374 596741490 713859049 572083548 288129771 902189941 592478798 937804739 329006246 998174170 770321243