1194
90889602 911995114 135625641 721335611 843065864 461435736 92966808 123736204 377007573 151728563 935157871 692960271 549736344 736206360 898665556 116633493 899449572 945325814 263305693 357660549 28236032 372916432 604214729 169756937 485740582 503616923 352346471 436170222 879855411 125154567 498800740 427970314 497855688 822197565 884297641 180843789 827819399 37842944 285940463 416152839 84079648 717595805 687235037 746396091 311367729 63920806 83046983 226860381 183210230 245863872 271039849 115036040 463273477 387854901 931135479 944250888 757466486 398513745 459567916 194192115 47995082 419042044 174300796 996333450 777945655 971705845 860556541 472368247 424615357 221067865 497789811 582711605 421089241 685382288 568048265 266535071 857321044 691506938 632919925 809216299 744102767 274729813 485219281 790068515 464462584 151829578 470550555 935013814 218484549 527927606 422842028 154696075 451804096 567941273 791950293 688346172 346860549 869761267 163532388 462601727 82376095 901458488 763563116 447748750 642224916 39244672 64370183 80304904 518750767 771408533 596841261 23877724 216450675 171291048 912258670 360283140 663108015 635331313 189890254 507083200 403446629 158538443 720416708 972386556 684871291 516218125 23954124 256114987 824741317 817477149 86600480 523564030 434297601 46888261 687897992 415012152 501922491 606271445 772371292 44585495 543922657 949962452 480021496 109289955 823179573 973022747 325528517 726943536 444017427 582451822 952413215 960709460 894228981 394564824 364336272 156516925 4328981 547574454 292666842 445168657 163018472 126934022 669635884 626171288 120523968 944294678 926534676 524716588 950451079 633239166 48200209 947984971 788901617 538525168 163058045 543888872 892765146 839445367 129937252 819589857 687502103 930978086 254151035 148958968 908051081 194696261 864966682 215828970 667914387 506227476 746517786 468487588 78096303 531722055 404796712 299905841 211496268 348639029 258276546 488626623 903463002 288126903 424437861 508154019 811973239 620454341 899670164 900195073 415646680 496205850 995809609 692548539 147090607 544048632 915944885 761494802 528577121 986097947 356975145 789673783 395932676 482244812 923807338 478800366 956050575 63002853 583925870 38387959 126431120 176137129 703216054 998909159 268595581 740302959 748532520 423029066 594235191 651501930 328026535 970319973 628827802 379512462 755349401 81454730 443594688 836393203 160108740 62711905 155868056 249936746 898148870 501614021 109170696 362832573 633875484 586449599 786025483 919899640 906109540 82929682 352508835 557097677 780050715 459128061 904579734 612760860 691458398 599692547 497423130 154277225 219772341 748390307 244279802 331982064 684884906 376086646 311730646 844457585 478001545 265134096 912666897 469303019 893535907 152616920 797053080 276339125 343025802 396552477 704634968 996894508 25321813 620773510 445955294 266905841 131382744 125604965 360464592 312060988 861508108 121759634 138133998 120931246 607777053 802120014 282589701 181095944 342644025 553999024 232363357 643033110 854962988 716019257 894155849 329429398 485108650 988767202 567713326 754975800 816708622 102394763 678178843 128738514 753734239 270396964 773198986 649716887 605685196 428492476 20813273 128854246 824259823 723016945 454762282 978914590 281254701 109873578 95851707 337690021 784325342 332207234 693338772 87552126 973423432 524967300 254545206 680436279 534134602 444492055 345578887 438179609 255281451 304936960 294024099 823185717 685770989 739922580 368353408 606138420 315050144 514823891 644168953 936671237 210617709 77629014 6174082 52587452 682149845 710686899 528544640 768356662 38833961 584686117 248201823 961763945 423183849 879981549 747853243 529164519 276103901 990126773 991659503 600323688 524325077 775122407 974831260 138098109 615854880 147835924 834196420 403919028 457680272 230113461 732424981 802924657 912323165 227657348 780385751 215910272 332465607 427034428 380271104 974120921 289551194 271277001 275747902 377215105 181054777 575311958 256578495 307351667 138792364 948069624 272384171 237240325 526587793 723171917 947626878 690233986 56319256 145948237 790736290 607566684 589554369 594076796 751322541 526652703 163415911 346045605 667654033 350884337 234144532 421210628 1518453 421650565 976915410 869191437 323788117 447999395 210765467 645699351 984813397 324803175 67107256 455196118 607523678 525875554 545184371 906404523 200462394 595322937 859135944 5310106 638632246 27518050 599363230 210809329 874324474 789101620 684522900 487003347 585181708 743273969 950607829 82238168 320482318 643835452 392420737 314997814 554627795 348384897 945572943 5171769 91770717 153799381 363347345 67711912 615062726 857493965 65327397 128991219 326527713 379199403 370887927 11336330 718361521 527677643 431295688 915116 684858284 626652211 419127524 375931335 22579900 706967599 624778287 628151429 95114077 36026580 623803425 794395934 886807882 381823057 690131614 957688404 120824520 385129853 901902357 171953749 926986831 580186740 604187307 674097322 531908729 613015257 892244560 156790211 739006039 616508213 248109766 162210432 61095550 153329406 377537352 5235420 902827814 59326357 397562142 108654875 451137744 633127276 701045997 702267597 197010478 982170664 872925537 734972319 140340431 713479951 430893037 646612320 689511460 79565317 527015298 379154971 915728963 185476676 457083391 720073498 950042853 954873723 950244533 500304272 546876587 274831521 980430896 902865287 726572994 48330199 776830903 146228153 908427919 934270874 239138303 937094572 296471566 489789515 528163756 782489289 553355499 606783366 701043835 972467 553636261 615087467 77999843 918687412 539807274 128510186 354282879 56883599 28074439 166873752 448721350 103786922 780519026 364909647 636917419 652632623 162539187 388291219 138482364 815621884 180039449 282755059 373561247 824718121 60596304 744007483 275945240 374091847 605101663 864966380 134371872 190281029 432751532 24669804 587558498 805870760 32781107 191069307 430773939 296094632 96543703 445761645 140582512 208510687 201084974 867336753 872721368 571036989 631860477 908365805 775713405 909799251 806465022 521148716 905048798 884828246 434552801 402909849 828417898 178261851 623891851 82884575 568684970 220803236 817402116 670866610 256810152 911474056 622695539 765625525 171526651 788503620 483986904 399418202 560664577 123152543 714658135 489271069 702403141 317139508 519561674 868399130 418798543 604612420 622449108 901464826 988449075 541003980 622830789 85372531 843155049 389542225 380024473 402909122 141245204 786405397 990899718 518204014 165394203 650305861 817562 352817939 4791074 761724442 539166957 367228344 276186416 259791856 923540051 563005998 154968736 636058645 939233941 788697423 503086063 237457592 525929563 177123065 833292058 713868443 457568515 116806499 646719205 556717816 664287934 783410385 861187952 393626741 803460104 55253423 903683861 713376021 49678090 714442566 798573979 821129252 700947474 394035843 964083080 69915059 11500103 401773917 35942593 611389380 940974696 357753798 844109714 283897047 493872899 853903205 245908019 944527711 985350249 608642485 408819438 699364094 478529037 353832681 148009685 7643739 509750933 733387467 227286956 42859778 603758154 249034806 931319941 623197633 503138470 996768832 730211397 345996210 562184556 268394058 454966371 589926248 383522246 280360330 437745869 185208984 360732040 890912861 242180523 877019450 985570262 74011061 327576554 77004346 669771951 342482732 284799062 731655587 307515947 976242728 699595452 555535691 717063997 215854037 995682337 325584909 103854202 303209100 871872984 472615315 775821385 369234653 91354228 333070136 840425202 812461385 234571967 364422393 33831250 853349129 95556539 36564759 952007268 416246192 330705952 994994761 821938795 56803013 657787407 906418564 268719696 706220671 292239463 982902851 161105090 712654706 633090294 345459087 578748223 755853376 519127379 601733315 354693263 460988190 186745245 454143879 223133738 902032151 68130668 708491594 864038656 519525106 477090551 486981980 721846129 207684985 861692029 616131836 537701176 546238139 483540700 260224841 81352525 942933817 441090417 361730891 477635686 514770381 137420538 440857086 336704752 286728788 396782942 216600862 279688500 751033185 419837734 558240815 385573747 597898628 216102161 111013804 778742425 491954087 449360660 554261640 658491561 585906718 440662515 221414121 789150819 311224985 988341328 905620972 874542157 15121625 434464437 966876703 697102077 631991994 154254751 825071 793278845 44210119 351209516 41136822 449935407 727553720 346877029 423728339 181121756 172204601 872369420 578757560 93983491 231819675 859192710 608718810 49659367 383074670 492915922 432057107 326974010 340345469 954247659 449391746 256902798 51460704 971567386 328893407 560139777 868585028 676723213 606018961 765279228 559886485 249697056 784749776 576760619 276061625 242421611 353709689 823204007 422734328 235251806 503014238 754187667 588123926 767149203 418107811 228143884 231285810 31504753 840460490 664483979 335025390 545396868 222713244 389296643 528532249 731186404 94148603 411397080 276182682 91257071 396074769 490294110 272307752 205383674 124156384 109681462 175353145 487086314 672022008 950545459 448525007 601321137 667293970 2586941 912777476 124305960 811892645 407940319 161972334 141112697 959906562 453147445 915543510 103503008 12232046 644780712 763930955 197613896 146634252 406004428 449838329 824428205 225616073 618963170 926962523 579128575 597454960 127995651 986005377 617304094 614343286 897574680 697846295 256327296 109264052 612251923 57014083 147274430 468300815 130602284 239153731 378177168 432387281 547299899 280033611 591282889 629831719 823208243 127734204 382535603 442043587 281704485 250456348 515108282 743434755 681173447 441481526 822456587 887089427 306117458 611024265 13948631 482181137 159581218 133742904 665322794 745646025 548249956 239472828 883010119 825484288 253719594 433540271 470414811 483729028 639773174 851866565 518096481 861927113 351346555 597108040 99574672 113422549 60352589 398480287 940181754 54994951 986336661 992421185 146198672 823011658 885635906 829686128 809688265 608602663 282527147 604409213 761026473 534142606 571343914 760329342 293086927 381270976 630905961 361174495 433027169 412049836 314595453 573739977 705273983 675158862 780419459 821846007 413068464 261740126 93341115 343327323 597509038 682825475 77917298 847769004 377993775 906552851 855730855 690595522 384830962 17050774 979590654 669089365 193866459 958319552 846952663 964574361 345317427 294041647 72270122 412238802 486357365 916905180 204893044 779552160 73021737 907400393 243486058 621504467 545746161 581252371 637358545 26794219 454592863 20237049 916212404 717830321 834567251 975329188 769643374 349154395 442237906 416190997 75801284 588205941 785559121 795813047 381544719 17058481 916566460 770548598 206650824 653122186 106697088 39890461 344350442 620094615 375854982 973416424 670852610 453535527 427938913 188188705 524555850 160089327 875636238 824477029 974566278 93302676 264632815 471256075 382737341 340372121 903688007 563272188 224021557 371591901 965517008 90195998 695284262 700738831 275065746 118874733 276899045 291810210 439643382 764718712 110289868 98192392 806719330 170166503 213344057 505751868 110089825 533414839 568812129 105167731 672947803 609884693 546066703 642206013 171784453 571202600 917305535 38832181 543836044 490669215 496886043 622705969 872697054 629006267 593978781 227418653 77418103 738896680 914480048 308343133 633445520 389954769 943301136 870621807 70546608 696337808 492164788 941135712 822202005 649891360 905959459 377928229 333595526 402350746 16215335 980972225 502034526 581281777 677345787 2533335