1994
848939151 591363659 374845131 837104747 229576571 977833118 268143720 185851505 916692761 341003505 816224939 87245912 402532547 266259037 503793533 436641865 406341257 25199786 683888913 155465285 779714386 165234984 87474213 830912336 171916101 102905095 963352185 152860772 403459105 241763490 944215550 11796573 171722453 922313803 581920981 178821327 938803262 281881920 283638413 514884125 531114413 306142985 662944341 312444687 742731684 228907572 142182344 600553152 176046989 304161978 239523807 798004824 676884036 816919371 102297124 510668142 338415281 289988990 118060168 234305863 287670442 552252257 430135410 168113659 992463332 599107419 98672516 532352140 40130886 739984410 352199120 976230222 429189360 45740112 45720398 10372888 100801770 340579391 687273871 895347730 232304596 431161217 750022136 801444656 899114328 562294893 255200547 123682233 849928142 230176998 399060628 83321600 602121462 145402242 406655783 944320744 963737588 266287637 696471648 439186758 207616129 303343162 908367728 392901713 16347062 964298864 292582014 523225010 912022320 570723874 405521673 914534721 938571637 927813946 433026273 343010608 155618060 471782359 740542642 714516109 359836712 495941915 998093343 755757948 568212781 670428507 711283493 193638028 243769561 665772945 805343689 754782240 922212923 299277934 703180066 217643509 255767706 244212479 491218812 290359260 260635101 595418725 369277700 691609313 995318248 714936844 199699989 810735833 109450911 954675238 207325701 363798925 947773377 87102518 743609545 303363808 57576420 219453882 598621149 788993652 390141586 994431676 304328729 66573214 141644906 150252276 294230442 99736835 700764118 350055079 432589986 769624558 519003798 945902367 678984304 226676325 144250396 91398181 380934131 382110665 495479380 970171777 602976539 759558233 493450121 407136480 558179709 481248697 857683935 769075387 753922827 234399958 864150662 137186763 678638110 303249461 641478476 786028049 153473440 182088795 149688050 313913480 28780274 175270422 380365550 769003422 395725630 488668072 300999869 679978605 262440745 211106862 221962000 840316755 392203456 716674664 209648229 522025779 932778707 164313271 490550291 449102316 58009853 690715201 513269844 730508700 219118295 197422270 577168173 207801985 305457322 887568952 268514317 194552673 618664567 526769242 831411825 18746629 806306903 154290699 584732104 365321440 512739092 118492870 236642940 94592251 272204562 602080217 256402375 160644567 523486180 18068089 531651858 182391155 393338503 247521863 608116669 28362770 869501500 838625040 76530411 161629846 194808107 30369683 537490183 921404534 463542481 805628171 403077818 752246893 112736802 113922934 983067935 436926446 470109576 516779959 168939758 827697137 107776372 664607727 597619410 366715454 118907618 63122389 298156002 708484344 855850100 239893026 326557743 726896813 227069785 261732904 704388878 721840104 135102602 341890685 566017039 855022141 669110882 15526086 90810509 345203025 125992973 244320973 792001906 851805624 413623762 24199348 948026077 499701605 877895040 424872127 872895498 490041169 921803568 968330101 786633973 418994226 614099633 404115640 544351518 615778576 524070092 291276583 577897424 124194426 899056496 263061765 886047103 854517990 550629131 670093574 921390906 602394190 983804583 453996299 398133721 829876736 27488653 263504911 444846044 648221651 966549 588966907 304070766 917955451 366284156 316230613 281224629 47203472 581905029 129046402 246195409 364477590 268142396 894327208 68119917 471915505 948692602 119503373 140137822 77692646 326411473 728927323 130988624 917937295 36385920 833548588 692727919 358233606 325780226 232183063 354367515 209399863 383296899 319933217 350161637 223505628 38702450 700930442 295368081 895059035 390606027 89989769 19181044 847923482 656416386 862782081 962977033 606223484 333563727 118028816 57595305 191788567 298168862 807542928 64598842 258331926 653716717 204075354 281844356 445900985 647625375 166516336 56706720 972241171 13918351 117293148 907660740 203390615 220083028 306565940 269974639 322372842 645008337 210920314 475791078 330321180 987825839 855208423 33499053 848414142 467371739 172482320 55242656 926496895 61022915 59242716 834186919 394475533 253622796 975346164 4815655 179937728 253088369 406406586 779313592 715503982 957317364 17048045 115332633 39535350 306769792 562124147 706299779 531213021 220195344 9281925 447561626 988315252 401424522 526543940 856001289 314525595 375115574 776061249 842221358 610825583 266215516 785643100 9829250 329761164 867575121 640848058 81017010 81927455 133502333 974324294 666515310 846581030 707961146 422237179 997596348 97771218 275212553 159563999 780449602 792556628 35465026 159645677 926865810 717296891 602138729 861051794 767424728 730268203 686560788 113471562 293532957 685070443 380035017 770008549 35917410 191632454 784377642 253292643 222208381 560289404 555069112 367119063 209569824 428903448 2740012 890697335 955192513 602220813 390474986 423045685 777607065 508424154 876186538 277853009 395144245 273914513 283497146 926069604 384506504 612295169 773461061 826605846 376899393 221850695 844833633 698624319 631117788 618681064 476788356 923595206 93752915 335674286 49982023 450296851 353968887 425672386 562791559 465589960 95827008 660870446 811788038 288961780 856944247 33492032 215724373 167360971 635576858 903145876 984129660 572716635 270011076 420674125 179618601 200534836 502689244 57931914 197935415 361697820 431368306 710664183 238432097 256297819 686352430 995146504 194321550 154725694 771724073 927485533 57199811 674919653 241277138 638770013 281243530 953833533 815332811 55829611 815269498 983557983 411470604 969376401 96916456 984303108 10347454 418673964 320371143 332491813 425848036 850516627 514047613 383482971 479393980 983311608 699854010 291062250 639028146 499213416 276377376 48085998 102577309 206487489 75673668 552423475 885886636 114352745 223725205 941930354 681213526 913897531 15061307 569188772 787937064 638258133 939181080 711137 5818048 283218134 897485370 372838616 958906231 773793107 318768317 328403133 469811985 454419092 804561719 288479742 110312518 690143065 577436360 159975026 355717353 256852661 273203127 132681476 105267958 549791133 221697784 923748213 184040110 337394253 58077376 739485606 615585538 274092480 664830047 55017809 542930757 112474741 230117382 972647762 572372141 448185958 805416969 309378191 625826201 285822654 962292111 165688564 23567632 526373822 214864037 804528488 878803942 784783817 517615967 150754705 63968250 229741201 22113548 309865033 180307903 415385722 303506492 841395704 974887433 845281180 916275281 572980220 647861540 613911450 552825343 262379874 118425447 514781796 315890745 587333677 257588200 667010512 87534878 628263501 225176670 720788272 651513373 961276073 598193892 864312812 259120119 419756098 178623276 937653356 910864829 12842932 637269254 650831710 39710565 931448233 56301125 673060731 682109531 418151010 781189538 665799199 94608146 401844253 134160859 159548493 65589282 579198824 860010421 192386733 534297517 273581970 725230437 485091991 70524732 85521200 316038289 494555048 942635521 128656026 205434513 92547416 87714950 670027493 417373460 793738955 978820847 215123604 896170063 850406126 907083187 841047603 505137181 882369735 674045328 881997009 711629158 52418483 260060185 769862315 664947286 129305233 904218859 949490479 743444058 195620580 115597304 823372483 536636913 911329343 146904577 617178501 64712468 997533447 273931148 286633628 560545583 68309472 434963507 519762679 259947050 701034304 486462741 609276523 50747084 352115739 184109410 215084778 377564545 359561885 366056895 74621482 868427409 238526850 504769562 556783893 714174840 939022277 955135023 736345473 415718394 24456023 708439394 229797949 95947784 865159688 475892467 177204973 372095879 11759614 265465582 573255377 644252292 172554689 644500090 293137540 870577114 776595737 218775640 379102594 755103369 573205551 988218567 917762159 131233933 253025318 644122208 517314784 538650176 70765283 700142966 666506675 198596306 359806118 884246057 453635814 338148047 438886974 163356323 687109841 788669858 443058148 534975986 498475531 439744261 675178952 645028467 747305586 647325248 376961404 693965734 494615513 170903148 461349847 733947035 725346901 523313359 813913466 841078932 479290386 238574366 957898201 285454566 353713878 258886122 237162738 403789239 887386272 593738194 284528187 188546351 295003870 242168976 230123454 600485010 205040963 225007658 743196184 12055357 59866442 139983594 106293041 490112607 570558797 680298730 234724903 203695482 805047814 901776720 23715160 66646589 153103321 506376678 580188112 826614209 484466847 15317564 84507118 752986477 88528079 183702652 215830069 302617634 443559628 77455082 621577245 796280547 252891159 15054543 465016835 328306440 28819032 917863207 714146626 767884066 429875737 805848250 621870157 35641790 915747420 814741741 127831983 562880845 153038922 118000937 677891618 138831054 571053046 201402117 687472459 281603286 209900314 329765820 374652655 216568155 456932951 19168503 887784113 136307434 952136164 191114783 272495434 428629123 522029221 510169496 34382785 653044970 179237679 141850678 292795157 198799014 750796547 104843800 65943622 15019948 66493598 877600809 240312467 738623348 730090961 201881600 67637171 621076241 136431296 201104519 836421813 64839148 322575950 154039825 293780013 193155031 400789942 141572900 262336604 609793921 906321703 4301821 489233229 147801178 838658882 778938827 96079587 252105343 699622890 411303018 49921388 990442800 40930866 299493651 57844355 113451530 420372498 40872857 393727537 918299031 987733487 431918790 651692316 28433272 873765855 142185490 859830637 658494852 960531203 94025129 164752947 596278726 402486611 612746283 299544673 861604265 322523625 183433725 930460802 964172392 533622294 831322148 983913691 92547796 78469291 34838577 171814286 870681904 520610299 288832074 623437925 60286085 740932245 941570234 398796111 874948024 192354127 250022607 804903472 401384950 511624230 41389025 785498862 480107786 192745805 599993652 730867645 527873026 137897470 348973756 517870904 777122761 34858766 450916539 355273314 233797745 120714463 428777199 218505555 209699246 282239612 941870326 265127839 931767520 6450729 801015582 53548936 786281009 335193779 282413804 750220642 552457979 227499310 819811458 86240591 188363799 711074882 861323457 569439500 880985586 391181482 155504287 775239753 35597403 771780066 25686521 937895855 434092536 169189627 316016550 137168036 873248633 117936980 89267908 932147027 41322731 846394791 867322935 878620284 121213132 971993069 204254999 546931522 740024730 272078337 111537168 778851234 259349396 437439406 99017450 371948121 676671737 430417005 7459139 138820310 299887437 589355209 431656282 343668842 251924308 815954873 392571550 172064682 47658922 361130594 110521676 167201849 302292161 520837390 753079052 935311204 584244309 772056822 904383642 816503865 372062869 8942530 801906905 159361852 94329923 895254051 764847294 392418584 643066398 527715063 798544838 134003412 547666470 839504448 270161919 208826541 701376161 911103942 515069530 254788305 237067062 743847148 636074350 622377299 97513088 153545094 970040474 317779380 897982064 243243301 210808281 128355724 716947911 888090661 825053036 405285696 954460252 482554412 975323897 557602470 641873272 305647423 71161969 188438380 515742436 822449518 116367172 977212358 253922024 832811545 694519000 862714615 600279126 939801319 573061168 279751999 96398825 450434444 969504101 205183223 851918484 209958519 490245269 503282718 619265877 803611614 933750733 791229230 28249907 821089138 798022180 194296322 278313684 103043255 402887169 334520652 557637880 807182852 332588392 669528728 581910423 384611707 971150635 410484451 211172146 530192564 654169394 73866538 347808898 329752058 987004908 707503235 271406321 96572091 91028110 571870503 288206538 325500901 476344591 470181479 162848802 732306528 496688267 122657896 575517927 177320938 336840270 876472843 16384067 76312786 506982576 672715714 566823782 423768238 25817627 615549026 907063572 840266630 919105874 212587560 240867579 854428709 757732993 882224915 174809408 3344575 245935294 692090116 333140981 438505500 794671859 979830165 947388709 601280550 491504646 298523268 12820989 846663614 287579147 536423903 809793239 482638865 468131139 230616163 348485681 75403760 923804615 284700260 546609234 514258203 6652560 694704236 276153807 528785141 385160781 524068288 169494685 145214209 569469783 636082378 532201975 64695569 286614384 749342046 915358131 490040871 930605124 240801247 875184698 766027584 382249681 898982346 942401796 437586382 652930105 496205454 556099748 253037614 909698363 937566130 657737646 508441907 146722624 830169155 396832553 955317343 994236971 604923437 652812689 834955092 392608684 221690834 711981943 229462329 838504112 158741899 56478579 13482876 102483295 814291745 799532997 246384546 888403843 588185117 771316092 467514234 818072978 268083626 517628843 265516103 841601522 615464149 213521632 844915612 948969191 66580687 848649265 92526191 554211428 143664363 484548993 180567010 101961812 978507839 198626883 878290625 244987321 7508981 564332096 42280110 574688006 845630428 929638220 840769965 822089531 165454288 562410175 987098749 676949683 373786215 815485419 78000074 740510544 2963082 477637622 782543684 384951095 460175736 680791639 537077132 320116348 150661715 179833326 359811949 233281813 871555093 195222165 7867416 278376711 511922090 236984606 671022811 402901694 814047002 121664191 628538974 581764160 283915064 187731627 753691401 228111420 622564654 202610365 36603851 242074780 594436333 545932711 959967490 499291213 804258967 81991919 726181445 163629967 373204835 827131891 182496298 880415251 597733745 43135529 383229533 457058725 610340937 860006681 531808310 719533424 275515825 360997193 337419407 201611981 901699201 444023500 727056336 379447075 679804545 649450162 601976985 34751017 380158778 353781119 47740497 752871864 562143654 423137938 444311293 29543634 711892410 54677956 338684095 313764241 144584872 674257841 584189213 169143440 575500291 536898073 476286435 248135612 516619616 135020726 68765487 378130852 488346292 654653194 679475004 173920126 993597350 695750341 640148194 333291599 24051749 460368897 491798404 644136684 310113891 906210305 921892003 961435953 174454828 951711471 184208502 165087868 149046669 499458271 294812143 84582010 174853055 446432698 918940591 225224658 877898747 17962222 528661564 817341288 132344177 44415003 107797315 286857855 518678647 752441554 348974279 954701631 432732010 383356641 316492090 792405465 760591831 215176511 618044041 118897118 756498465 310395129 120716753 967537124 154259175 896071480 151198640 395283009 257966928 267021896 341199046 147620924 279610468 799720483 525284585 477646323 42513274 82775970 251038650 415751528 721777615 76058284 160487917 114767416 880431352 102608961 232894200 629558545 367628163 716414884 687909204 421335562 243345535 908763389 249002780 826646102 943069264 587681559 837567573 924132546 847561594 757059338 737943342 740309018 296888279 320479155 609819628 108804578 26462725 651349230 863817531 879346508 28460722 457997564 713985095 198502610 322332052 133128112 385777172 265785287 787724578 710774374 431123879 871580703 475844128 160547514 918887810 493640406 715103081 308116207 103219029 176440211 275313255 124669920 62895449 160070432 158709955 106068518 679610644 169609732 873150917 739619328 524025804 354669726 564528130 12003534 868183453 832558909 487210644 158039577 831700607 30194329 929716612 808553435 491840989 59621332 983019039 582828993 494152870 360900199 448518537 935031180 260224893 212753345 379026276 625080299 78336020 227698690 706556591 711075915 372511788 163396211 859706141 1565629 649666722 206977720 896735570 214333311 261770751 231111492 16703130 798978733 376459495 198234122 481399894 932790788 876130913 153735049 129544667 668868377 566730523 462961759 641227289 549542624 867810032 329410627 202185730 998406325 76344899 61331860 234467065 747654368 709693266 44796963 29221056 547938694 842365608 38771476 110860281 447052227 412254740 113554355 809971462 120665292 920244904 675404425 932133029 422761974 589572293 399200337 602503291 129997407 95202935 66584502 899214589 808494731 986539308 347464285 163598880 655000744 107870090 824103592 878386873 873075972 172776044 778955581 105658311 974920331 747163370 645548389 910035134 124685240 744350537 103233477 84688492 332176427 650743205 28180430 45946818 544983685 776699527 231509784 678660075 706495 707729411 989028710 170616591 166162151 10471845 498299547 103259390 791644156 330798262 534305102 922895326 102022977 522699395 745317191 337372653 229647007 903418594 39112699 164347710 382673219 707337646 363994994 254722177 876231163 12571539 626897958 90553444 52556240 231619345 545716989 152997659 5342178 162205323 181095161 446590150 811660234 725020265 459961397 823155966 852901622 667218037 603486117 193727770 631965565 493685875 230162634 529304776 327699697 865389672 805034818 136583462 463496621 589714415 832379677 628670223 87771407 669467279 501035511 535287879 69063150 75345715 769876424 4629130 92588774 571185522 306639199 10783079 743905741 287700667 726612529 647048227 500953192 657501227 319380744 389029250 256987536 560789011 575932557 908935084 560945865 176246105 750607491 219682740 978302962 910090554 378463277 172152495 308816029 612351144 505945989 287661487 736700301 962016738 196302969 233210478 512507063 366258962 529451223 638220727 50113052 78271109 732752703 724782455 876053182 778598963 435765921 834173912 468887962 670813728 575961254 25460059 384709153 179031012 684027532 234646401 867063361 727890223 682678237 375053879 984768813 83315285 583948440 580848502 926061067 942379825 920978843 287409140 529027980 664499551 217026843 630488114 803415026 351445986 646537220 353903581 859375745 209296485 940062994 805042248 989753156 385703056 442505789 868121512 44354573 496989819 649382859 129564417 127889398 9512113 489938513 898678189 79714625 468172936 266348483 347870591 70715580 520308022 169911610 19180300 202194107 448196889 315421986 565050425 363326766 268409885 680720329 314015715 199193000 221294875 919926706 520450779 346971751 767601776 578251000 643059832 639425769 159321925 514240994 963021701 333501388 498247776 946034674 370828106 10481103 943783521 291043897 799651931 663255789 39675856 683625615 106854035 757074099 111736777 213148808 192670359 514474112 541251177 250559567 6717290 523970781 955883628 324305831 237910091 535984344 424280822 730923695 39729735 17857676 687446318 674721511 948189757 379777787 807920121 409087920 905398286 280840203 668480107 827093983 654372997 400386388 1127550 782493155 777330595 638467244 578738023 403675693 87432539 300836116 863832411 232009585 965782856 751451821 543686824 450328314 89943169 369714280 625415378 107014266 465623067 855858570 860127566 693964209 652317742 358424512 78516058 79374210 306802232 483342065 96732242 94182785 900899980 75377970 848166876 247082052 459929934 405665075 103864075 970797806 55489936 38965393 816445148 481608168 455260872 274323556 779424184 988873542 83569170 662083003 486775736 760767270 309962261 343769441 986293535 51906502 909352108 846772543 140758743 267608865 836830226 260748572 703396127 167389435 8339617 810707988 372067097 883909264 10652110 267627970 233008971 871630164 584502315 934002305 647549329 551633996 330983764 148318434 403136135 532981209 130234697 105654522 878364224 479856913 152670526 
468378638 819813355 856076731 327775375 707845097 573392736 318875527 489536921 765548070 205936866 309725834 60926820 527750495 746139287 460071397 618481407 19275202 864213378 435591302 57386873 169862162 326735003 642281277 95953087 851824133 473779786 192697136 270355974 321481174 891289091 451758222 234144570 764256139 356320602 988011299 279258280 105537226 869308912 959036902 474130857 594670194 405148115 982517706 544613543 237969406 914027842 909409006 68710684 848936078 961111293 832221644 462305747 105454505 411670218 520027856 351279188 354750990 280386873 789363989 756793120 662772376 114528224 941649680 433793876 418383322 252673479 607842226 950782899 936710689 232243648 377208884 46329366 903797780 938344961 973956840 423096957 157843541 764475 870604871 88912116 263527614 54727354 481181840 74624516 620167836 819034146 372874518 159662735 150084167 136037897 14377640 803435094 437766698 626838151 641605922 251471367 993683490 188832339 576920475 990407586 837677632 88364833 21943373 991082832 503562578 436443933 551198838 598060406 605900693 917975918 499765060 3686547 673766043 81576385 266376688 74753131 175245677 592469634 201716221 87721560 179474881 326072043 245007702 165148108 809739145 85548785 92166256 236163437 38275387 415642019 981517096 886375804 605652448 101531985 304412648 332021458 804969376 21549254 186671404 502537701 420024810 988507265 766776546 931907964 389448157 245136109 345740374 242049069 644364096 668401482 224259491 351062448 604650958 775799547 405328368 605787127 803691579 755294117 571784881 563358863 161288777 864274252 204001224 999128595 675615019 443754926 150267339 626234632 380293924 180383376 79973741 179821477 535673950 638519286 346644364 431263069 602088768 643495457 435395001 212302986 681839268 805252789 41697978 881713891 719852452 702680687 654207957 138854081 252121567 531539475 295867335 110964559 521228421 875255781 468284472 804424955 887898375 682416607 156157967 11384215 470028748 493884552 405747337 781073470 51365894 20591398 592148241 29222482 223036888 1889696 873261983 689946849 442057876 327115790 36791970 982408571 304001708 629148264 1854077 16265426 26131498 274399472 81350581 235661129 908589061 119401412 941826410 196625003 787508153 520855416 328812481 542054371 603202021 145268005 274784332 192000017 72308933 30162701 559461184 18015720 690662448 404743746 471294374 305128711 188126648 256608503 969138112 302689270 384004433 335214835 90264983 132171721 503539600 390136373 977783527 316432588 465771516 929053833 924107798 8698330 861985127 947463626 555604473 327391415 3844952 866489792 158916741 161354819 385494841 283483303 814051927 42653989 496232623 741742220 201581866 948717680 719667666 397762207 930005616 998171768 298810110 240822342 242142432 870762399 155146481 590406407 438150760 408291296 978301603 534604897 171914014 124948522 826818034 149047206 94118158 715943561 847055307 223550689 27061629 608681435 366941329 647579741 713111563 466684743 721448879 118832717 359579130 685802698 260022840 511354307 173761458 105835102 259523613 824336098 841471093 93648830 492300694 200989145 469873935 101722666 374606555 419994924 813728861 835235438 394000311 237585609 56684955 622692093 784507177 14699411 268233057 475451598 407700554 325334943 36701191 704460129 142447792 748438568 116553253 253430108 24353808 641868791 511357143 968370364 292106093 113946750 723015125 107436232 243636634 219701063 656477581 693828065 20253217 374108273 138923765 428818396 417722056 849624243 328445258 510064802 423305247 703837985 976925441 287656428 951490046 384667177 169590116 923491753 487000208 301592603 51004230 723993196 718247111 916871091 522752466 763237194 540813823 191017408 211278039 271804428 639602704 797403109 998758167 906128134 209233765 550609222 27966370 96280675 722338888 621883022 384801083 127819251 726099838 482773894 110953251 559789307 843346988 781567293 597576501 912929066 122064211 342980088 573606705 369950691 428431395 216413764 130812146 241251349 644474563 356753158 861997574 963113510 429096315 104451925 357571828 882730817 926415544 493785746 524688869 314594918 89279410 807169427 742299052 375447934 300438544 232500042 267881044 82028305 243758339 793672719 993171147 809440796 15314114 554451304 886805831 723583813 479866331 431752372 945210104 623182897 655001196 883933140 684695250 704338905 678703680 632460954 777686487 28431961 709175523 289619393 742475933 973799524 590105130 18813580 173316465 521444545 967352279 582210267 206464523 319352007 964905718 301297883 959038000 104634091 891176988 788334106 846996856 597432968 419228549 628664653 253318055 281436836 219766538 68012312 134580770 315821591 853869908 36667104 224103216 870988821 260044883 59987257 783803596 779322905 380189328 758528714 489836593 697170109 648498236 43969887 326561253 806826648 48067224 10456293 546832438 68302744 289545909 960763520 902226924 444474251 248654720 666019008 886057464 839041105 375813833 232159435 554457161 573584535 642976682 745895991 495702304 724976283 528429054 39754319 43190342 195744864 569842146 638524461 245373938 342876246 423380101 760738047 528963016 808899518 254920623 540343896 362367165 419791941 116092131 76350726 664028966 143525407 6595900 104493713 770052165 397745009 572808855 808139601 85497913 26517588 894933931 654029270 402348811 110988874 197166586 41751570 211192948 978382167 583894880 215460604 158725423 956921397 70719428 318190684 934938210 393836886 625103360 899374113 995867634 406610114 853992196 448504124 804842195 516345261 733830720 769266984 446856013 780375076 673356856 864169889 322088822 803264638 226204001 922559324 354000534 766831875 941276222 709814172 370926689 578007003 504444244 708098469 477173957 874673426 600704647 945163680 266651182 554872599 45055150 16444854 613648318 538621201 932999940 137181109 10206960 876631189 24416246 133582956 570783393 590187857 110288723 413907687 250763907 798196547 930029059 234341847 71343778 205617940 372578386 727130419 913357671 886481420 297176286 302259031 561575625 116333860 535814761 111257253 249869381 115552427 554989855 296272014 413030670 699033172 829001302 773223893 980280249 773929320 990124628 646069790 98087826 161274609 228329206 544739635 432169691 152727960 607013639 500932256 210961403 160586194 21818339 188084480 309168713 619605394 60577339 426785699 26252526 885519479 180791280 671202936 771679502 829119541 414021524 14110320 123593498 160510728 294363617 118240704 593151093 804846651 882402320 761262084 601718082 899407843 751908516 500804245 669186226 585030610 851938309 826888394 342237184 159684234 731713428 864667701 593081550 811974275 589529337 919460093 433520891 220835822 73767799 307998700 891582450 948280290 648508867 392115430 52086275 219775007 256102001 511454021 239423935 34392574 299635746 219341842 1081857 611114640 757371254 240025531 775354587 149787003 715664983 210918737 979572307 819847649 702888818 659557028 650852152 926479942 859856075 388033822 613555791 325712288 63102103 675210892 603625129 992965589 705166824 538318810 386320033 254719287 624913788 108266116 831952895 948588641 602997906 186226044 895725484 593242198 438566933 667933472 681028987 307005344 145007254 460932686 496954235 570375847 124524141 86217949 992214512 21073062 971163969 903473535 739270582 43608938 641831289 156504802 895001446 667249861 571442801 446848666 36373372 466860878 161603794 18808784 670360417 58004471 474671284 735184715 641849269 150718675 784467788 315536146 18514768 141761963 151906557 596811834 339730383 801443281 680182896 532167476 200091124 678699245 960115479 938165986 679977666 817089532 753485636 852558227 18643453 217532216 128676412 965860356 436316610 523640972 28044576 282070934 327382982 595709470 157670051 755670863 435595052 475410134 677767838 794396232 795939767 523517067 859661731 697196497 640711566 171795092 412936128 585232706 803756168 686565647 54024905 418289750 622199684 430434965 852913487 100656217 281478651 548092811 245613688 692719426 549061775 982657157 758335358 403055804 753313022 372504515 183774301 219240238 873278536 499571782 983083903 730326748 156151454 934254918 976528600 130432840 923748244 850989067 652228469 224712084 342335868 240361276 742520631 513406742 109830906 129377259 363154016 117138664 436748734 327139620 278572173 549104456 46167774 842266634 68661517 849253768 137030160 267411159 633467738 929324526 145763417 916170893 656155765 123682241 232058570 812234919 478359760 386089500 917582074 345356357 775228942 97147439 249046087 681589830 42594906 916746034 74852365 676674018 888471469 857016621 980080159 156830913 712445300 334155686 9415227 846050336 794205381 9825106 53629997 906217038 705852706 581124047 271496109 14299091 490123725 277691857 51549499 726587312 708033630 927299919 81625257 541495154 83491251 229150620 968899096 218303811 348553834 807629283 394317312 139465751 296407150 209002101 986325336 874939612 597475487 591398800 606550884 154133412 177863947 517906204 197554372 640681690 27080375 989047161 769408569 765435330 157289689 897915157 34305277 691834818 195266340 328952076 199770809 2513917 335049629 741700414 603005639 216916138 8320787 408244000 988130525 811645692 893559235 747359589 865972911 385709203 671850838 234831680 268626728 990036979 639128017 572153315 353529700 393424726 288370420 327615352 968751325 934848106 728730481 898059066 265808849 754829184 829620421 173560615 571574508 814940302 631028826 728518873 548334645 171278289 340237626 791667892 874861234 9028931 646926 202266764 972455740 134349924 730887942 191420082 415886883 927537910 511946858 477188608 790848307 326183337 457327657 41516072 181959603 95747657 564137509 719193654 484822262 57177046 71720928 844665541 472503449 58650560 944360535 955900094 266245619 567247401 625160284 324791128 44480231 51347730 113888724 490364338 987044507 437109354 533421414 409474134 973208282 503655216 795570499 552669433 769592405 146279057 566796721 878909536 272745480 518188114 486038622 702532411 106081284 639666288 339253074 889747102 387890598 720910973 957570741 578675934 608219817 559794695 121446235 279832691 210088905 439923626 160313537 769508343 400671340 6626960 209319855 426407601 220741950 529585611 260727744 597189598 573907221 389901983 4915582 462468101 217044346 54479354 126626947 386864034 645921688 44608453 165601248 914619414 229764255 332193470 643421291 953596321 481348044 813318900 254899865 554835104 894106970 285326761 744926662 236586655 493167933 656514647 555573389 633643868 487866171 774211483 12660215 920900586 475774207 688472734 422276101 786941000 360909932 412033052 714484161 447255507 88382926 42004762 763641402 284056950 52537268 846935803 151778406 819483617 352680648 673149145 89026301 190176061 593290603 31952028 98797693 769551710 871087995 941413046 137286786 417774475 766368850 529019517 692439308 679699086 161499715 836244367 92211000 805146162 68143175 427694471 182330923 697214546 387023894 747981230 7687833 982354378 875707767 284316370 691370784 423287521 501441773 518426725 878179066 188340788 904349466 54280237 607516189 723126292 558283299 761199496 191714750 602303129 467963051 192848304 578890920 726694733 377413748 721713469 800766659 116446162 452589773 791911 567443892 768477744 709365012 3868928 34280308 297899946 600756416 825036452 932080893 979497902 943881088 779992107 572838659 295707056 324956362 830450266 590399200 994157237 727159409 387140609 807993727 522103393 187913797 19044918 228183159 565310052 508849575 604942944 431827511 66347760 614759541 98030966 533140572 863050175 196510397 841403764 326278048 831092311 29411605 37310048 998296027 280181537 187547165 25267810 883414306 213694715 71562901 985258476 605260098 215309957 674035797 357535860 830752506 474472080 906565962 609053 337896074 902269375 819517007 607460221 772096934 705534461 87815234 811757153 444516893 510172983 453279043 172463599 911696323 153409092 37957065 963591656 774155167 969416019 423685329 606428986 83178685 235442567 807283437 308365677 524793603 530024144 975845573 58411736 879000634 222772284 224951462 433977568 447182820 782893711 628331143 100734927 131843310 562436752 923008461 629973198 748250162 633688587 322087004 240742697 777687465 301234289 204206149 742717069 480147588 23288337 689879638 803601341 528454205 262424555 739692233 431325422 338791595 736612094 844216139 809616739 98185308 395503283 575600933 464224340 21702654 231078318 782142712 61726561 167220855 376582048 285527023 168034677 265025047 564261392 536070524 514866386 630336397 897089802 748398720 151639473 81932979 845373624 828143523 765649400 634038112 985435578 267173926 228105558 226855406 477895455 919695837 614721665 163365995 620054651 718637704 488104600 505940141 910852165 497860900 113323527 484732145 125093571 669675165 22706894 589203007 535004393 640822347 826523133 225017667 778509934 269467464 390254554 328855348 612969807 705859254 200955642 449701463 140866863 783236340 379069682 277008423 197005905 108475856 105717621 60033042 227499318 261441248 731625133 998040079 192697305 185389564 145124956 483258664 670208243 138211238 386337500 356544226 409910018 69413683 770989598 147771694 653994115 66370902 264458030 574476670 822722736 73248506 474029182 101692231 620461907 151188243 16620089 771197900 778394934 745294479 875578381 165368069 481924535 150999506 778003965 645418651 143656012 337874187 650932172 671194434 200637299 218381778 289312729 640408052 68997008 534925647 748191253 125378755 246564831 852010732 773440626 522263051 446203840 247766117 648201346 738436985 855517418 314073624 648613641 281135363 250905391 10741577 94979686 186957364 115410949 821236360 281133719 166123222 645750400 534433711 123337958 361470735 994952850 609458904 436945658 492071543 75528444 204995005 19802538 28307849 832708956 655831087 891933584 608832108 848074107 884768188 472669172 671331095 212425720 756469194 336205377 856938460 829397020 694009081 912647003 906595299 829282928 212953150 594956473 108648270 291342604 164991620 620864726 990086637 245117980 942804547 221629271 86921606 710318621 213197263 123704337 115239524 425957228 767090790 800819983 135289545 615057096 566614937 524011216 83272108 362654594 50634584 694651817 827077077 308460859 114967061 29785262 864822922 318813886 396230354 838365515 916557691 675245197 429106172 189460031 654105834 240001982 692699054 813912007 783909385 662902337 881553577 580237440 259578129 539359032 742049234 237831715 626558015 638020076 5018577 962914275 594711248 603579607 498530468 933198436 280274203 597820061 634422401 878431606 657796685 363328655 206005462 254383503 78835971 829394525 97003676 879829712 95592165 951847511 721990313 162334052 561840276 41740189 559095973 214667787 786362548 516984394 985890871 411521467 269383621 682773471 798038955 712473720 119791157 930615416 746980517 118730845 467631076 525918407 712787107 720226494 546733069 120978213 25596837 639419742 903504820 575433563 188377599 527606750 402158526 615073440 537427351 369767176 736326754 457926686 710771507 761394794 79153285 5170508 380118837 538072786 161614740 736298585 947201075 20169446 11615897 125792384 828971786 333524105 947394768 558361028 859496827 693401022 286439512 259534245 203351920 723694725 912242883 894649023 649950475 396583973 337231857 146765951 775733477 59501979 36870556 96556277 458070974 628216318 661774786 481613087 799061623 419312446 179397305 710957525 288751854 135235066 662379654 728898373 354947712 547403446 575283348 522697388 144438954 615531779 339067566 228684993 613012557 720407819 766811623 54700280 889355154 933826662 799582722 910627740 830049002 556564881 613313376 372263965 107427797 380365339 92494288 472008145 251535929 233587510 69666397 957672908 872032387 387408904 891852471 924528634 799951628 915536443 982997959 356057026 327162349 397523955 726881373 787219559 442298993 575965111 243574607 759561130 894810773 346693169 179064350 847976526 306981118 975351221 330303637 444697375 164350737 163583740 46158535 96789395 919720851 235217556 249413640 26085809 430038921 328600182 105709114 262375105 968207881 24487879 536084694 818740132 878043688 725759105 14945607 673068860 753964402 488720135 152023584 234192298 354920606 530322120 132219367 296902960 425659117 753868725 764439196 841608093 98556003 768499538 540211404 727024256 385855986 349570882 735300192 648573741 481318722 377501493 913103104 836514010 726703914 94164056 210169892 719783773 285478048 566687417 69310446 788652662 509072831 336284068 719587828 894443772 131300659 434424935 578563949 693916250 417395513 269341192 654498194 358480209 876901591 880403710 229012518 185096470 938565616 810348139 205730053 71558803 63710286 955362279 423179373 60376697 280960890 181081505 921452286 759017453 111421099 806216886 538404407 465420147 188293827 119182240 369473994 655091885 358677623 159855041 139378241 670907671 60555284 849840266 505787811 308851941 272203638 163262779 969691492 840601599 317848454 379383557 368265658 754012190 962548557 105899845 649397457 188505134 980357721 535620001 188304194 922013349 206761711 886146751 224335774 869577281 284368240 162905941 283859380 685573242 174799587 625630020 280195528 324935792 162293093 881968172 177251569 924493489 596656770 605065550 295021300 926018247 331184879 426703600 499084296 691194009 112542470 44491731 913930939 917713200 939934532 28311142 821353549 878299671 304109077 468734891 2518871 347751465 813524254 455336130 421007381 119033463 367271031 282935189 459651063 543164344 508679626 643717298 129025773 387427052 276740081 758089605 435921166 44147171 599304457 13932123 171922226 354508323 542215487 481578663 457687293 620839781 634833047 91886336 806762313 952469675 316761297 860957916 15632975 124849882 887346004 15146398 559706143 679271865 807206197 819749914 326329360 965861870 740987130 75109563 617639036 635248759 680452016 636912479 225000096 142782953 475248818 850528921 643181909 910466580 506158697 152171495 389799132 609288586 560802748 342830980 172196098 142557088 40861019 120870104 746376788 894535961 533323978 920499859 7201710 674717079 292151281 541269105 656626206 81917977 734727725 937011690 886702908 317666135 992149931 806657320 191354098 172355921 888147980 737663045 239036687 925626228 949430309 937399857 724254524 396469333 452842264 5633955 714157957 78436347 777226912 434320400 532557383 623813313 55536274 98708165 206747821 408306164 783215420 484198201 193764245 267554547 114173724 198484198 963834857 230884056 482888341 144803369 432427769 984829887 309728175 870654647 191851139 819887588 262934192 896363035 10521665 99585119 265700623 972045423 832011077 392557942 307950282 936335846 136259140 692854357 28097939 537795275 982687134 54569937 136817860 381117663 387470788 491155727 312484690 311530719 59507906 429280723 302039706 288287350 23074304 943925576 747208503 549679843 204474669 24905166 3295833 767040619 724644011 964626089 761410408 562165399 178356810 194727740 753998102 292063253 272321853 805255686 247524064 850997369 150483094 722807536 964955412 762311472 124514246 278832818 413113281 845398384 587324377 825944304 478125688 834843737 277510237 784845853 617474873 952592932 370025910 96627977 938627594 946255801 174204185 727887264 575563087 181097289 36125030 112120733 593447687 600374022 775282708 564706904 136766150 632330557 618483251 513236268 167033795 352209710 573083652 447863329 518664420 900808466 734562303 412481729 185576147 78186111 222599783 458627075 151061237 835018554 534887706 92183680 134986596 76193699 689301647 664199905 80998026 722377166 180864379 850715667