10000 999999999 683910701 810548722 447027726 397353280 37647349 291094378 9511938 86705620 628340776 730221429 286450860 274970585 904879386 626052608 15266871 978053575 872126891 26355862 462914926 61644455 238162888 347237725 538835218 189909460 696798170 377325637 383793092 695996021 168371624 257097062 247910401 312470617 954484055 23493096 979359757 978713748 28090426 589010862 711966343 627999400 631013605 423703716 799911469 817653011 116342692 385157863 838553119 810101077 511344994 18409894 822891683 640211097 623585721 663398553 423359293 355111767 33171176 66007343 749468841 917344094 949792476 109778895 275619282 792013623 435055451 254318944 223337545 455506176 747071201 284233851 236889441 569833590 732208530 805762392 714082907 355955876 23157118 359296627 423911877 405271070 886026461 92589619 773268473 315287980 553243234 225096093 195230263 788338935 772766635 357687452 993478452 246713748 665000130 388651433 666417317 290091372 202246863 996780610 278865248 38526234 185267385 471449602 80218829 294051105 289210359 999479635 970323658 634351536 966782112 266517757 975614529 781737608 938007255 569467967 959233371 519200856 949442914 254679378 893741307 842736983 65501100 648223911 170781741 126002348 152990338 199409374 308819690 651043235 457616607 52024798 701199094 639205745 346617764 940679998 578669738 751939750 831702708 198582238 452809182 165216866 395909454 790416003 972097854 637478832 759892813 947508884 326617654 263833135 448635284 995653994 249381330 753656225 597901968 907918721 904231785 390515319 188314543 580227513 847272725 278666604 459208413 676814446 79224966 886244758 358093937 501775957 451391526 239165091 576324879 863517054 282629811 769879407 637367796 468101980 626565827 790248893 98872741 428244332 788064019 737336088 739701258 945378607 219632084 774912252 492429985 817046505 79063457 452590412 293000054 860433838 449396315 16935 222631749 610658855 414517239 427399882 661503287 250317090 954905430 18359559 335760004 921432680 537669901 529819752 374058456 644578384 585872680 590206127 880066761 570357546 939976045 435995305 234270748 279167748 388046534 412703176 851333011 155289321 213163196 145378225 505501458 335588873 61507605 151864047 491673392 481850066 801178873 16428862 787323213 274917609 151323551 289367814 322354421 470067398 898268231 648030194 329922457 993522468 367687205 805197477 249401908 572672530 330248904 331253398 569072509 965800851 726608481 257183108 445031023 945077725 3120035 726778968 606683286 758971280 652425924 389804678 478440249 92405487 906462746 885191415 210566607 305938487 789849103 7148357 346268315 485543367 718659655 720529616 661938817 104474762 35938314 478699170 636020982 686049814 776781326 571888956 440315253 74437529 221373426 911691903 45032384 848838085 546057873 543535481 302833930 149469697 945558969 720031273 873033431 81916768 752174241 900906305 788678586 805605863 301557908 47331389 908157599 34067058 24198001 918034631 559154092 636434038 614541844 260413637 334222236 254188452 236768810 221351752 270099995 772939111 861390695 519641139 901381343 320146148 737249005 855482503 865710807 415880838 139270230 253757042 622753576 470304932 296855090 8564676 281464464 999535702 407461136 219432925 686387052 487535947 934360222 577786983 548743167 537858538 739408612 709522689 104930333 883334277 726778091 530254195 204863658 517596425 490906804 389056356 864636802 8786855 343508895 319952187 729616779 297613840 115527680 184297255 980837419 579481747 318748456 458499630 453048988 349664702 839849303 627725153 918774700 243051452 11531799 705537179 9101296 833073442 48733726 70596941 296698537 240894400 793602846 244019038 945853929 934263832 24850079 214775544 652382322 919720400 252372199 636335872 545507816 121800855 636833699 486806789 324725615 833917356 99545274 319112059 255866812 968587457 676917513 879763047 178867454 446338127 35573385 887684388 389967393 475084586 811567138 22161486 986242164 982957967 35900662 445683331 911635361 890899506 527596526 398303877 760267384 825954552 397050044 850802094 192131911 876813898 31436262 840673933 243861813 940114155 408911838 774752723 596684223 475299856 790671954 642567229 46747993 219069094 704168711 113572585 639578573 764798436 294665450 897917816 638503274 310723154 176611250 433858628 232626726 261511970 655016949 965324700 517579899 435323213 857168554 821170860 244199249 102187941 866821366 274570428 397022976 944986916 289798638 708760582 184652129 792348752 908117640 46463077 174372900 890097740 758953737 7942938 338855944 836648310 367624975 880621999 786246626 655830424 186155904 135847440 77669617 881512880 959805321 580866766 787349968 811171237 635288621 341944162 397583621 94950262 111486713 34157775 639180953 673149167 144530449 71657375 961390276 384387861 785727406 436576089 245442045 730595650 37427045 973542453 42621647 710626843 846296040 668619104 229186869 994602027 956418213 555915941 812628308 194476055 560088401 162127721 810984890 546945490 609206935 429492745 351555092 932356036 284996644 172449776 917895306 43105820 621677669 534498452 613102736 438139926 997192152 971983495 329799222 693096802 950641499 743888869 327847149 410724713 74478542 115033868 252646990 291187754 25506030 758722925 491020848 90302763 671316605 588953843 697435422 194692170 160038255 267399126 648043914 811030186 96318317 362831338 439237375 762352044 803708907 927379849 664724628 483765122 834452340 572522115 132364031 654448004 886677138 846191798 48932780 649775609 243898759 339617628 365748015 569616936 853294679 887905007 176681423 434793250 501436123 11976024 56893293 447460366 976078939 311956859 967935694 202515474 70439142 434733520 603245605 901378395 195424819 963101625 656100103 957635717 822010731 713252473 636595015 662665581 39895331 474430117 300018528 580707454 952467402 813251491 59129953 114756697 147751422 719818081 598453955 790624532 9342291 258402010 279019958 575611876 532451717 57826055 384397811 325226849 663265458 131964832 208912119 846582191 13173198 745987436 900191568 206516977 344526388 566579160 642484045 687698318 165974174 272585612 584326078 114199873 500818924 915105757 82203993 302176458 742041168 252435026 636916955 829734417 26614205 835464887 955706610 617037271 746531715 963845150 73237080 432812044 364802471 593698783 428700536 132085142 274845313 565860371 323320165 433154327 887689914 992027440 699081953 376096650 762725143 528032872 690532104 302747916 427132077 462455595 739935954 556918685 522413439 829399657 143139631 937111797 242530599 31527815 948365441 821278207 309153732 38998920 980288667 418918416 290615430 58117681 52595047 650457224 190653491 477175025 887437504 83266757 392379947 873676115 931555417 309588099 176690993 275085427 776172809 291132025 780231716 713152964 709160980 941175895 906870581 299236934 589469235 505993176 552366954 614845017 599752151 847555993 191600768 588542750 945836259 238366051 761572061 288712683 501680736 742346806 354689963 163305835 94428635 173946482 222100907 305246637 262775099 267558962 135524910 808698147 158079715 333294261 630971860 340754790 874429488 870873906 374617229 709719415 52349674 424465457 268973875 629979012 590319707 216706403 828373793 620283151 786063478 644727101 371866251 223240089 111255152 665017029 237266946 585991657 72446279 63464850 243701986 122848467 529435024 993442255 206150907 108325877 309846709 375620770 321899992 882307388 683384364 461161338 546291017 37389963 27171357 253474972 697636705 791874106 939103353 517020741 475742780 411014529 831536545 744311385 45322973 345333898 183471132 939788432 478037983 919936599 744276311 162484499 521377397 285380688 992703219 965011901 678705482 671938337 566328328 706630502 955202625 158787138 521669414 805366 314974544 452240699 575152301 596242766 574216398 977586125 649136871 863993156 246078972 733112201 422718198 866558230 579984476 278774599 309510872 78387828 479900530 272567096 577734481 86677766 123947864 602589865 743403598 668583165 376260510 260191260 35169303 173070189 618932099 168197403 607369055 55493725 527988584 617548207 302250485 159086132 866571635 315668401 497400089 113974205 317968416 241281665 862512860 250834573 180977709 104414226 461291251 188203432 803679796 688945245 418094397 750751344 545423368 310784157 501729094 877119350 890327399 50753785 215365349 462415557 851514645 951321712 904979270 700042955 719466551 524864991 670107455 3646394 439262195 373214010 469297641 331730671 822106731 519464112 325843051 49639301 481663008 899757654 352700402 956446239 863593828 941838385 902546754 903877192 238847141 996203679 311486046 432244733 742142489 702792101 822855209 951778804 844539687 930133174 558909799 379512908 393710211 364167180 139023174 490522935 81533573 940554258 337668979 11911622 902975140 287898202 226257055 148213851 553064026 1200150 570365535 513217647 423499852 606944921 956689809 606529694 763420908 366047113 628869832 30163755 969733702 831609338 323143940 623222315 883830400 218860159 346517588 899227502 359326645 929158479 642962126 414313488 398582851 913613418 886329631 554420730 456297739 270338073 539567838 300559052 401578914 488921167 973952007 673483339 393921857 923276411 873051114 148729065 44911387 367154567 305771756 511486459 640768441 393441713 670957457 545478639 528795518 407708220 650671489 43701716 614146462 57730380 896590673 830060665 66105815 773919713 278143709 493694835 42280028 221427614 584523215 81858222 454972751 394434398 865993649 57953407 429859437 938695895 471640490 909691007 249338026 152346690 967617181 154960183 791182744 480410917 756928326 422076701 30062389 319238264 451848202 324474847 280923261 607578614 34345654 71104740 948125325 166272558 67627673 981888755 474628681 614230983 760507259 157306516 536651231 130794074 431254333 592868728 829377875 440612470 842534259 658882624 769942002 394420032 285734914 475107496 289591681 25632763 61312799 705874282 485391283 237400981 839759478 356850011 93814346 466975855 81534244 458342682 578100935 74066040 358085336 25966358 585352577 487919369 742272977 367346519 828215588 645457509 945620798 888693594 232979486 171832127 170490722 798484574 827436461 447798654 644257841 23770389 127481007 918482074 14739112 779996733 233870947 109227512 544510562 365539895 935642686 100700678 757465050 200893441 503319761 92268658 603274128 978697868 665345070 955614016 631706217 129310092 320298784 795803903 254526721 997714588 623756199 831564825 141596884 47259480 183538019 857841989 701554813 695560714 635180058 30013831 565987019 705181950 988395413 219176377 987289893 319218758 925940132 131122760 110610472 988169479 992568600 298059310 553602604 783563437 80747520 872385487 566620840 655466469 251682936 447309391 20908038 50545708 128323399 361587825 431946438 65826589 467779498 717808959 346193778 37216873 123615909 648540558 456798592 33531590 206422053 836136648 350590049 193980684 559771874 454444341 485800302 773354553 607087300 219119528 846859203 473562954 565094063 163409183 286585134 487476600 36697999 794378336 242689520 271539749 118535012 17565269 778348990 523342676 617603925 373478327 547436168 60866761 451848765 825365973 703720251 188668547 199010889 333087371 167959945 865704083 397342161 392097924 323446579 248287749 134803379 399581963 743472258 423932114 687237639 312277108 155779480 847253752 180901698 403830887 539802589 873105926 113979847 725524011 131070537 105589208 931739777 975425316 600262533 61196950 20388621 130674874 786976064 912300670 478145145 279413242 933288283 131322444 804381256 377300230 290799693 509753764 387847892 63635124 506301258 858764728 995057269 509465892 142885266 304230348 685040710 481046768 710734397 328933751 985259179 223485693 388605199 964465748 236857469 378954467 264929427 936528130 690293153 319579286 46372285 277190732 842333058 5876530 229618243 359001337 243313657 676762408 245235735 417179441 363352556 376784362 924959353 111541289 334946576 960961052 258005057 259031068 437293095 858765336 58608145 526123164 958045591 488255081 214478193 108889615 667507107 891688752 301057541 513796804 128046877 408320851 784233144 766532655 700490931 142245252 877493439 267221664 615207553 647556485 529575107 141736553 267528110 804769109 484667121 139563790 847083566 857037513 946614008 743552192 93791978 208541872 986794653 296220904 917923058 947364641 436080066 237101791 559337475 368814931 896251086 377443218 76221542 660629469 575367887 919733976 134107444 627577593 602835107 332769160 152505541 29138073 99432370 406850831 903023945 70136359 679637570 792296782 136481647 501196378 940542533 37447196 947430478 974860137 364055188 825163143 516008289 976175370 525532170 510379079 955596281 155985172 489248435 702205558 49917787 984238197 284069071 44604573 197689204 693162585 724350559 327630148 362536588 770525324 982597349 920117254 919568963 206470413 970992403 333614693 119821909 99257940 65990216 601018600 284947896 531901162 159215532 442124354 575353313 180133877 662583391 768152516 226911655 379874901 487603998 589820386 958988037 237554383 288142103 495951630 957487559 318117026 360472878 484793539 521809243 892634137 570447488 496621577 427893701 210278857 889209526 717955393 48066651 708610954 508570983 824516059 732297141 62968308 845371304 287272448 298129315 962185712 879538131 684532023 304354885 86396924 379901365 409629331 156040652 946487068 409966029 20580861 768506650 657638659 655831864 792959083 221086101 885769609 241391451 373668116 476933704 790534803 781101806 120380005 204854149 847618153 35389512 93840714 88293412 662568554 73624536 358430142 773591727 875344948 788215533 366237319 25784421 726571781 742497687 643092028 410225333 931430619 54585579 668703981 289792719 943915591 527256233 920151875 461239515 142273743 816343979 216913785 894314134 715875373 701327085 220538972 780674688 265178014 674148906 672655784 146544132 161150053 116351490 436642593 286826565 260420006 388939958 891935079 95471111 490054360 640799309 732205305 306799770 344404628 54834455 771752426 738004666 359691969 429307065 266243100 799888559 924329403 346231990 317908370 990115648 259456437 948429437 740544369 422827836 370442780 349289601 900903414 5660129 172495928 580001735 390651270 928278014 668895742 461562719 292982339 157004699 986316759 925068661 431828628 572477539 616350053 723489871 486597323 879265854 384489903 639342498 644377044 48817242 366920517 731531933 483041071 623921516 241463599 745411677 736748472 961160967 822692721 975159539 209727767 367748068 863774321 887428468 360274083 4057271 570971773 38515056 475576158 479481570 773487397 920762384 165915785 826557257 814581611 612458348 406175710 259297167 113487643 562113679 91304336 22173969 15948535 673838394 113893283 135145984 169279433 564839123 145428567 809589040 781366660 506215580 452804376 325184129 948244693 29750083 318691760 747032629 848757057 459892362 584309523 756973740 234846375 13400724 887652827 257832979 910396417 478992753 736523010 171831319 49053998 553891958 306621459 835452256 401505132 459463948 978997626 636643901 975306967 598474604 82378019 543395621 316248732 444256170 54075734 135668945 400620372 87743000 513640474 828700817 574620724 510569668 307133509 521279106 302977085 627968159 943502259 727285851 456838884 958940589 540211749 865308405 864939013 766127338 220916495 255252691 146301163 75070262 177003230 171601583 852449425 871444720 396403583 152315161 477811407 302685254 471893141 485563778 395087349 22765729 287510720 171839586 574699157 139348368 621725686 667952934 531574075 102845290 441153479 796557011 176621856 447023538 546196526 487852711 643120891 508638170 192821132 599826149 109251870 155330448 791247272 233708934 687246208 500937353 976728970 469396519 527714757 527807448 479564802 741507953 965979333 237214198 776352439 563941548 277559320 260134194 483264779 595620607 14907160 958271969 621379467 182201734 960204010 684148249 26065238 270530773 83309169 632332103 334968914 690398251 64218335 262622670 735732751 150612814 590665134 599430427 314304664 275647739 829461971 377154446 762310171 690317540 891109046 404508326 987786402 571429265 348018339 135146451 953611574 458571618 654941781 59341692 733799722 135724838 774023490 551748382 236696545 448890679 185104140 431458278 468859740 353275083 413905187 998754992 292512531 830651661 26550919 322451914 817023980 580462075 899211126 254842697 330620547 267165285 297755770 68609839 757821829 254651585 606119333 840158492 271896080 32634816 276115618 173527226 916549456 249397333 978887809 573157900 929323594 422782627 902812527 565390777 208630622 972730152 438914554 448721488 840479614 372871357 37729922 560871099 378845385 577825268 116743200 3962310 250025918 772041792 491309150 513071349 86580271 183661230 731263494 311769446 366510931 694334896 87771450 422737498 579855032 187854321 558519981 622015604 425003991 654460734 272919409 499943322 673732682 594672605 581956272 456489588 275563684 40322347 69771122 777721086 702821058 778304068 596586346 655997230 187268060 74497954 506569242 399616673 352925734 254773635 251498414 476707200 308511051 13330148 994246267 129905730 793515651 845474145 758260923 337700932 756496017 804966090 514216392 968215218 330514406 81096687 267214338 232818689 622333880 96638012 892403360 489552560 878031708 816816011 719296403 137276645 272879879 306668635 881702807 676252406 908001060 807907035 317962669 963162622 206419555 458131446 252616634 560108822 178291293 429538791 633928092 747800993 376541104 608791066 600586033 950968553 462711145 815312458 754869613 795110004 337007836 5894284 118588825 892318794 710427636 436180447 822893668 432457658 780171012 544577602 154855867 254910741 547670549 544703804 764486647 894155045 42439916 715102496 978100297 56217987 801196909 969175538 10830377 597608862 932552552 986824870 806442515 676536647 770840870 457957753 530778782 739287666 801866961 495750516 821252789 131791912 307576048 146450809 554455913 705039204 120619667 977723706 583422499 958623546 363868840 747433042 952349630 262928991 950074364 120741332 997114049 69080637 574702854 750079860 352939248 886653121 607710502 897580354 724828572 140263745 600506167 253791395 731309554 843711082 511077975 983871604 747669592 718510398 417314626 60028147 381867649 874907208 655670720 66948313 585969886 238227683 474856033 298674412 900193121 390382155 433148552 707243052 547987839 582233515 659841585 175019572 42216140 112258648 528463154 426702071 258168661 643475967 299602499 389267660 103332123 5118538 447920688 867631353 631504882 587257853 20311334 402555895 765725649 152911011 824940064 190583990 406819614 158601579 134379074 1783230 199090425 964524625 26242458 361343821 329335133 431147085 373220594 550120236 568096104 720138660 738434241 614755580 81678385 851983506 204432698 900891989 999366866 6602051 153422038 177097096 102514097 301073009 676530488 199595903 491400712 32471028 90825203 278884428 503285222 154433053 719739374 702136801 212772483 161969371 896527548 596446110 396079527 17001161 97941599 296931807 127127691 262018002 238736747 523298005 79430169 874114073 754727723 634357949 907888303 617613470 986396369 91295566 693897205 899790985 125605069 639085706 661255680 238217670 199522094 936735633 155566003 55518382 98766690 709162010 63009946 351453965 887010181 438025192 403137607 914991795 698425984 90276535 132769102 760287690 594692880 39229839 253075183 858277594 237573661 754465448 18785300 526001836 74891971 817760012 447309690 893115798 641115288 609577058 847019710 131661507 258448248 554648353 799297047 881592631 875699250 19144154 900151509 879393563 501181269 922316886 696758062 877169411 939146490 421878116 135340577 779690700 608960290 917428004 603221515 610062161 660244978 305820198 323977527 602081980 459043855 335358571 615529785 898224126 638773398 914255697 902318785 73894681 130072075 908031758 580755545 906691216 15970132 838817036 958818490 437465134 329072185 708286550 753517044 729808189 407265150 89772092 652133038 706039012 561064542 561660154 483468596 728861225 251944019 324314426 753188158 994734376 925332793 500403884 962781961 421900313 38514763 660742380 935362488 245323580 642148476 744748377 634723338 493042734 349899890 909734300 898755661 512222938 414716919 302879327 466969777 665306703 439177484 113497500 407672981 731961897 513337837 43780234 927097874 764032046 94446766 999388840 844872830 559536251 32250599 16043968 162716664 287202629 880495166 326675151 941787015 422432747 114360691 860950272 585005711 194493033 455295432 133422019 930838326 416745253 65020489 399551637 781958423 428619800 550962934 575069775 484143621 49685462 183263980 861205286 446419736 890585388 381654834 387075838 452304848 118923932 827371659 764934333 794046301 204660785 694994381 1072871 597654447 211580049 701368396 165196478 767606446 629460533 418955143 997312532 228235652 404312356 600033600 830083923 176576192 898221741 872741556 885734897 881962280 750843439 882229602 932673506 804776684 604406470 808053724 173823973 984816638 54386450 755830720 5191355 433837472 988004687 126225981 301479993 712608261 239823093 52262047 230851680 676559121 623422797 977080268 301459536 122730251 364115749 544633548 629674645 491787700 561600581 86936958 978504796 990514036 933319225 20681633 332283550 261202757 937007158 586077329 991103667 684197453 730690399 260206919 929626887 348459463 914424447 310053407 466892584 843185105 802776889 786423476 836766144 132414656 120934359 534592532 686034417 586194007 598998641 761611381 715315523 608705585 385283806 370445492 926473998 469041609 515119175 679691018 261815091 787739206 689809418 592378680 780794172 436247329 252136034 571814068 88264139 282188978 729361648 505612280 126465604 566282810 469502772 285792736 996236900 673385114 367175789 563358026 459603847 497220158 185227671 26165307 677448031 473523363 579395218 840711688 486917527 37691509 255277142 748922693 761330625 759406418 187960008 143006953 711351783 617487290 50844625 193397186 174134788 843471127 795831844 480838964 244001429 912784660 144428562 303541199 974250176 669143748 859034020 879317323 228188611 192911627 414295892 541800353 184901144 970104548 756743069 5709950 71170056 678716424 481790270 131011803 658058528 616832090 53676428 897490719 144759303 477025799 807077064 573235283 672357351 988836662 888278330 151905385 738219629 461339910 86299984 889150899 793005074 657281303 565713920 298521864 825103704 805825597 816756997 897634270 503110326 140228001 986439445 717832491 640286307 747833866 26586029 512346170 253557365 1535649 499124119 391827443 154256752 553581471 201583715 470650393 872496806 104475462 130957144 976560093 278807991 592300553 384163330 129900130 725718507 402418562 918881113 172076582 41579666 886074349 268090799 967109697 625617783 251489553 242050903 131683525 26482701 495741063 867520515 200255019 249161442 863868933 638824906 700379243 92853334 627662021 999985520 512922858 744205456 185466272 580853330 601375574 758254795 401814335 390379382 208755290 278711379 177975145 72336050 299988777 658165167 808582336 676599956 248112561 518853949 212859860 744280353 165779703 180360259 499786100 977407984 526603947 409707617 43613108 321596698 726674885 712620648 708899471 969186350 443612859 176145053 612662687 955128451 262901818 939462340 776074028 610668570 278668977 161776014 770594558 931219335 723923244 276910849 465499513 753337953 144496744 980200235 837898516 698180196 968156809 843908752 505795312 880081645 317796139 465543352 823231846 982024435 623118038 334767149 558541608 125816610 562288203 78190165 27235390 3099340 442726135 779141720 125722943 551187392 653284336 746824842 707225495 450748294 898863653 454334412 743770923 364068330 689014985 609333020 455624412 924896705 885882691 149292101 180056928 413485703 931179848 752816026 953780748 11462285 839601777 570493866 247099685 816708095 855658351 846912795 802870636 22748120 276439211 926988846 280416698 22636081 814045653 514820327 204859381 704484797 743680170 635166951 287862521 963255159 207656040 392848898 369042353 887945663 438476456 643415029 271460962 199798647 357862106 92043486 653473014 148567091 301029332 92631360 247152378 131400086 320114707 694348251 615624992 21763455 216507434 900641725 43541240 401397517 733715202 990986151 342924176 222134335 70603340 386880547 47643254 610084774 425388090 402171170 661325912 614019247 795233910 238270958 683795357 322587792 891928700 404965856 78901375 389363068 213741093 958057938 561305992 146676714 975677146 340042263 611436318 23113067 449051449 436418986 907087107 347707400 16296338 668299645 958334422 96876335 893604211 434997101 111423397 66518748 513308403 104737591 849656549 8324161 256459244 587071165 958198376 710995071 866070394 569678593 768916258 916837752 847858 980899118 385310914 503135554 71346800 566379357 671291009 15147490 564530978 515839650 426679947 480855657 353362849 419265469 763197539 362225740 115680710 999178424 324149128 477378125 577199234 788469359 886718965 64451022 238602974 386155175 665767247 730954077 953615395 14046794 561160217 550069195 866470342 656508340 806334320 813787484 981865091 137192467 274047479 46235083 982335880 567924163 756767289 511419116 796794544 895970546 185176380 138425824 95050273 930097575 190753357 132458892 87489992 599521365 9852719 468774997 263306134 102682419 210323052 483438350 536968077 547400754 481258600 212884414 488884920 136228928 36389129 404687787 295879016 579653812 456915896 963928289 629283471 347276663 845961555 330525417 347919103 418420243 430508024 48372270 590248718 147091449 564662813 810678715 750625642 693313682 937860085 99387682 450350711 628105130 541331872 309740921 642453951 930512769 104666479 922049087 342575636 752937307 680919206 887598503 595512673 329447009 373594169 298661144 372022084 987948514 792539334 556148180 363060173 851155801 269678827 403068490 584135375 876594614 621461366 206254912 321841367 998844313 915470167 919560243 14516337 357422492 276982179 3785103 941570885 683855196 891171822 794988502 149192452 597367460 542540824 64682037 427345054 739220444 950060187 791978040 703340884 733083075 860096892 36433420 275491712 968153020 45755723 656612195 486804463 191354399 617709612 936913685 859343472 96283185 105459259 765737797 266343229 194216045 737418481 231466532 318646576 634139760 992054913 577039752 957415748 645216646 459940359 665226006 964794071 450321892 138020300 69293728 182385936 840341726 653361949 810057216 133798585 806002187 405373768 630713221 217402716 350427232 934920701 634130596 919896548 707847389 828427454 530065049 616801376 981466332 388131209 657026455 504902269 699138107 29904032 188235183 351727080 935032361 681928255 414399349 861906844 627814387 266014062 957184586 128782515 163111149 954161687 23614622 456643412 505369259 252379944 8742600 664853258 439956230 908692418 615402296 195816875 301957678 150231510 237443175 85865980 858150800 193502865 276456278 278922730 410783613 351087374 789617092 290086175 296880550 276649222 934039676 798556229 558773338 988175211 945211122 70663671 907491845 717547022 306039837 903939658 140738297 424133204 599312882 27485734 814730032 942995513 638549505 93372084 310676211 317073956 517117957 814999146 41622953 380510411 457933347 733532465 676554441 250881224 869083675 70514189 131795070 75948694 975471874 217043605 113864901 330648908 292271739 446605048 65067917 728073126 100057621 264430986 38435143 590460773 869389707 531572684 840522892 409618282 238051241 752587061 460425545 538248459 968799167 83537819 535772746 112583915 189287999 109078189 279137848 671254385 846766222 926583203 742008406 654895535 484357959 750107909 572205597 335665226 277487739 61465942 21458090 416236184 450665958 259676847 82932356 875270695 246934627 28772172 437216014 832767394 143410293 8456110 715988882 616541428 923311207 328987976 264968244 573621439 32501846 693117552 614375739 871308844 699937566 751811980 711963628 846460992 997578179 840340912 309503179 803268882 95619590 796136621 840647990 335066421 750649973 664444330 511435391 700820635 693079179 972476659 922700141 858824975 279549959 793561358 337791560 926289886 97774985 671225067 133778515 962160186 285237319 286514105 167491477 570376701 107451779 452967966 840107610 291353899 872143370 51008761 849478757 630705226 897014428 71191885 725103667 796877367 943127102 243506254 696750031 354642923 43830209 273068136 657559392 511261934 849242014 482097413 552463799 239095568 645321057 440600697 512477785 895703891 849398461 735938521 227597937 63773345 613715121 432275538 121465489 523012138 846138560 568279754 778570162 249462474 472084824 564450884 151666370 170171372 681123502 4845516 418431070 779125857 621306439 532079495 990536351 230707548 997565946 675302275 336684695 897195295 99334009 209955576 648330834 725206462 306722961 32776069 340486814 811206871 312188235 698530511 280996380 87750337 431697816 394858381 23916564 659970199 80318788 682443181 183228578 336701376 944181721 269265684 122212243 83751252 614506295 155262161 4778404 200175287 558399434 928294492 814307464 834487576 712228092 830538698 502659654 259711874 701405454 478440332 999699179 997843759 548419597 107120888 357730339 200063829 640010356 735025601 994624349 563954066 923821031 285781065 456191265 808688925 611999613 56407848 667717408 279988235 729606977 844559965 564865327 455444897 382940071 918316568 766765936 945215476 688754106 971832790 513691339 401150314 529752054 416093176 75877285 568030797 142610211 228953861 839686571 433088855 538357897 71085377 86314228 94446815 765385478 168438119 343702437 6198441 495100504 287173710 64452981 738843295 609794779 968989274 164618125 280600730 750258349 554384622 756762300 300305721 813837537 665285993 785187245 189290567 436866152 28770977 484397628 231673254 631709555 348289065 849572900 944219023 139183261 431217461 48949613 643455501 191099021 790934031 794676898 194667738 322534606 302554932 696081610 871066587 524626666 314425364 75689118 388726324 359881883 528344297 365236095 711364066 974947937 351949807 200853384 756848665 120365451 703917085 591285246 943269303 31042785 89478076 881266479 735878007 121190227 348736427 717946236 287284979 17476534 767425659 348597281 582594788 186611687 198868735 532977115 530014472 828923092 712295052 296933281 387755231 406410892 807332917 41614460 142326900 78999567 934023280 964532078 694752778 941130262 464320548 857409283 353600696 615469172 172610168 587075751 451448509 882474636 12756950 608563013 309517640 343127131 606704348 826096322 79380742 944664985 479399736 833060665 637168325 691192075 47175569 804560829 31478100 236164927 567647894 67343622 468769112 863783273 330303443 66174856 327564355 741083040 965461082 220959790 734079689 220071810 798064314 115783664 206357458 425686743 110265345 873574169 321649397 744951676 207099492 195320383 213329195 77846372 522448055 830918208 530309575 591584517 143299690 603071058 755706005 85860849 70021391 132701643 84868200 103929626 35542007 173596610 399055516 367999180 559260291 718205787 873752213 560378555 159967433 501472133 954317467 575224822 859597347 124222603 481381925 118871543 605288350 114074232 709801706 506952775 365783652 915199160 534351012 89380778 29967107 76967432 999590027 403322057 976301222 26892415 858024635 711403305 183708293 450010989 667942697 407349054 924239142 842534564 448957301 72114226 588558897 603127754 888724542 26460018 735322144 614454510 308571141 665088625 479012106 647747063 229529561 865283835 307506924 794296327 254824329 360008498 85862060 143253920 812097082 250218969 607538020 941420903 931138467 230528732 615158431 797347052 913776543 621171305 762081677 141772243 365642760 770484051 821461283 95028766 379212030 726992452 384532661 288435247 598831945 517876595 903698192 663019777 767081796 728530831 823315555 150307095 94023927 1591669 562277211 704712582 243642002 286840747 643478637 886749639 872542191 227546958 447710793 25347171 852988046 593977387 60604993 553785579 574337092 628988366 903857372 7913263 943360831 89938573 234542094 191346457 934799205 519903415 862988845 397353503 209489461 301696840 300177609 281275857 489806957 611030958 985243774 903962413 22875867 838898278 763465807 722236465 673589857 74703795 651627685 446446177 465090944 85687354 423135457 980365022 857777676 977768562 217573403 320928660 753565847 539249763 291986692 743464433 295044995 641085093 13175924 704259374 555026139 63048154 86410874 231717694 377049626 629615276 936567888 678299425 18630579 546358402 728744053 299353531 93902433 628869203 128503285 396431763 229040358 591596904 964291178 599389021 91195181 421484278 139068573 104362401 179058692 887062190 633334791 377519740 260652076 541970700 201541974 474349556 292144714 865096949 358168461 911423312 371759739 958164605 713773248 115317987 987019701 94309390 406171843 218187534 854269412 304687925 794057835 180886134 769747688 609375669 272170730 415269580 475254251 776721855 826330792 713153928 863086644 43077911 86802094 39338083 319443640 781658622 238607542 732169518 438570388 992615198 302330647 702545217 177845505 841704068 368949978 109313415 103695529 525857674 233340003 697221217 177206676 42261371 164838077 947408907 414751753 113096755 936948118 547679068 241650418 528934029 634678683 531187888 835247852 555977225 605673212 51762426 767869289 170244075 424284740 908811562 740549946 677679838 115802973 54965151 716540578 523669251 626509763 818465804 781262427 637055823 625096370 56396110 175170610 669360750 948823946 983621262 161046187 734297534 145874003 758558270 331363286 308910879 661469834 766368600 158982789 486862279 833029438 841856364 710547277 765797861 327937059 790309596 532257279 571749188 321220587 569942772 478485362 169642775 179847219 422805123 271846405 953861774 821476704 313456525 586428457 158171461 139941507 940951340 552063078 150071686 844683170 717405699 545565947 888782024 919715299 796475764 614221960 114731920 357882785 31388739 657462994 15876382 322345436 641815160 755355147 674770609 899058842 72045586 598464559 560622120 866907528 682957548 554820951 791129308 677041842 393574800 358584936 276568723 116482146 484200899 964812863 178192488 965408253 504848151 669190658 197550072 640600353 565801429 915189854 973987796 162716271 390599508 218823700 543562895 371580565 7554700 638713200 221319429 736150141 169360129 152800963 55818694 224660307 799673051 9689106 893629781 891621114 452257793 579765099 133924460 243428006 866893207 807180469 79267355 220599698 854492508 67150767 856155314 204911492 532568203 963365151 723971715 762430447 155246866 397569515 78040026 572781463 686568097 538282240 23769101 890607034 801984398 179405515 324988160 922479742 74134241 374121802 159105102 182461990 811534629 257453442 121445438 478683683 932402199 125377707 565923632 963951992 633058803 253218881 732071676 203369683 667128714 635597176 350534243 534696184 206935613 979540656 29693526 951840286 384228439 437124747 772492622 173151560 278801533 920483598 350292005 574430959 869046447 487152436 943351959 897785999 9425687 444989271 747042647 483214158 40862873 121551915 19025638 617336128 58794516 931561295 13433911 125869869 946327 607378605 199634561 741713707 616726775 521300918 209747285 12993390 539543046 605601638 793095201 544850846 302534748 787897587 197690361 430462657 370509057 317527700 447337301 571750881 462692854 215718308 864731940 735088993 421862941 81550846 410922949 164238327 158170140 10928665 302696050 179626722 226357103 711274420 342971568 743377872 52028468 435617416 194429587 542318651 828235750 921715292 760678171 831258951 483083513 551185648 57866082 446505979 650668110 777214666 686345065 920818997 242871010 984800555 798565913 147432765 452915734 212843817 435729948 209605012 960855982 91502930 229821098 736226640 847113016 330507114 775646233 901849708 546768024 674596567 833670624 165139022 841610414 351608810 871134161 252964965 839140988 248236787 56680062 233479643 531150130 820064112 541154154 781531985 465580778 678674405 861097042 690281759 363714344 892599099 346636610 106094024 932980223 924400487 85001982 907586003 379706411 327698144 945855200 677534194 134845355 510476330 404331254 157332354 441195713 90221541 969473503 272547350 788092700 318622148 335157807 385201316 747277212 325630103 391247665 489691673 793122515 252177003 766372067 516346907 866167033 825917556 250545 646732095 148668219 343831613 970913746 750815674 105475722 8765639 116615641 416464293 846867574 914074691 907963009 10547457 289171156 862100843 135181907 257934538 124196477 459582563 899007263 685205244 913063368 268145820 830053372 200947234 550351558 53320859 437457630 90682977 210213877 614222544 607970290 823978569 699863068 171916144 974497002 601991751 873492430 621978356 59521360 329091239 570164867 30894396 13099359 251326414 54574362 882370102 224609372 462171776 485043633 704672348 737667881 692466127 786992104 670655644 962215447 652788592 953834718 535726706 708497155 824264009 165424669 233806050 694389848 155195372 844427404 596155391 858272622 38832567 454229280 892165879 580530145 160481064 272087605 254883944 142078216 14133150 795289588 977853002 870390353 819594225 806301392 225059356 712890944 206029247 338575268 844303480 782897445 867946085 954288022 818712615 421298984 711465012 428378072 924531082 762734480 74523233 392526464 519560323 771187692 972281947 944009741 90085082 377782374 51917387 86584719 399854816 202395701 868288239 15817499 368354041 437895178 58406299 264736576 353481273 716851137 108546843 115693130 412777344 139116530 299196371 192295711 595039351 416455766 471449898 955822013 988690319 167327747 891164154 831292390 383435980 478992703 366998702 720238723 136942828 731450865 93910445 764063320 468554969 462591146 398809977 900826198 608095297 438712712 629667269 209520537 330858168 599789371 88720741 412715726 621910187 773108951 915574585 567310480 886311992 918995084 693465670 723615339 20995 693089799 814070131 687769784 962822159 614150003 90752390 447414532 244074927 525621984 70612373 984529563 519398564 72663360 41161689 224483502 187309449 901164277 952683100 581815332 275561290 367186853 742651228 739405441 434436978 947726777 729992749 919934975 146037784 818561349 486042868 411450715 922876047 342066918 543038126 630142519 634590326 445273490 392725311 633922092 587781340 102207994 895638744 34010769 130851961 729018136 669905298 435570463 293989041 197848812 476804555 322641162 875338122 146470410 554092181 90600850 909908035 153865869 268264430 327484535 210340255 344128926 130102252 513358776 641551509 826992306 926211288 807241794 618196799 666099563 510720763 239607401 519317635 446890663 239296346 344258796 963475946 983947010 441261138 418376145 235792003 830219295 59631534 269025049 301893671 423249063 253612443 516681805 369758601 399925112 479535647 512831188 596329576 633246525 235967744 373993523 399770147 271878132 183986418 926335438 689092167 703989318 907277540 834133250 810042691 207096113 847217219 395734653 919624227 699637273 389574017 429373653 22103416 670190403 161623674 38430771 848128024 47081844 56663450 494815772 847534680 583296893 588122030 866528896 648129172 695812832 904285620 650698981 650321361 619638814 199327698 569198471 864786966 47961993 634690689 806116178 431722654 42000926 50398936 483874374 400798161 146713228 277685534 709677404 606253530 158777436 357117193 401470039 788030147 506776872 280553108 600985422 324275113 443888828 386752228 582220045 30558583 272383397 390849943 701357092 814857320 246745571 374486658 246464907 563573600 96259670 328938508 123044694 371991142 804569499 966651137 848636137 162657750 247308705 201212644 273281653 287892032 961766475 661747984 642894935 959227929 975221677 840325921 982797463 249049906 599676744 471217569 405323193 70472576 87008766 775334260 398016869 453845358 284912202 554128392 690260811 735904518 23443217 332515799 141978731 984965699 55622643 893448313 667328629 267688868 462670813 446732469 371080272 775518564 582415802 176280966 410871587 568194483 623744767 123549365 133072735 844654818 164288901 916427965 495002063 445756508 994603866 133929535 866304796 346676617 149812138 514864039 885118610 468426636 167019489 446173371 971030367 377020502 409937441 392188837 410720668 635526754 825294955 103873363 130667769 409169492 431188566 546845674 554535106 718110697 706008454 744006520 464217543 698462183 446621480 893874073 899415787 721977932 522848642 715888344 650616478 981930938 776826726 521189494 337172645 560672013 433599775 809563792 881625782 327715313 214378349 563860250 62432074 690935744 615591090 931312231 871921571 43260919 852516698 741578108 449825764 159384030 911432928 674294941 183376244 138427994 232485301 730495699 144250400 236694465 308619940 623975309 805089542 957798005 63824772 447830384 81635976 574404771 224589492 410793389 271548472 245880687 58059552 16110793 701605783 609445261 183081234 976678088 598365543 89587956 608596078 643668826 313606428 762823562 488151572 257331789 968365091 894255231 148283812 908956463 434531583 831417894 928954641 498823791 410357786 792654737 20973334 968493287 928558446 855624272 381409137 724880499 678763716 660859427 614538563 21727188 948861221 660642049 412128229 450361875 164314767 220480239 320212950 960817293 6061240 215471293 635497543 596765208 944387316 543713445 606722309 509324702 969718661 931234541 626544048 707198831 16086581 645798929 127579758 311023203 446865982 29224540 650246480 981119978 346024283 748904288 316041080 368518677 775528921 149118658 332195749 353232527 617801565 232113698 364601588 951092475 821375550 439089691 666021589 826291949 461529466 244114583 834548417 592160629 872079843 472081872 429759520 534166334 509289522 448339148 395964975 78967275 186681151 466309938 166340014 559353944 836257399 394731931 359717091 400607297 176166392 453078186 372639558 358259282 219282778 567978572 730333214 465199685 766697097 231305492 437041121 757881249 173038998 248945073 482323822 23009741 228348718 175681359 167209354 879168512 908426324 944240872 642368038 639544759 639924970 224167088 457793651 15148785 198732958 288233129 545928223 751124420 204355239 660595258 762030022 446040249 636128286 2503676 329236160 805153678 829378439 629409747 551720539 408904958 914383111 709654148 316227245 238302482 744661998 672127591 876826926 956005575 583281978 141528885 464881916 578023246 439199962 958893045 468922670 233878407 186012986 556339225 448566349 266313535 871779532 303533268 572005868 794237222 812890789 984836922 265347289 899357996 732500640 496814124 829682801 908173916 883088834 262598434 491888673 452660142 514778515 970133638 109490068 496723665 400627149 673645918 428420531 718501131 294954461 310679724 103130915 213713740 21682352 430044831 417403439 621039278 410585422 689117862 905659197 420916742 17356829 142782086 560894657 294090568 678678193 832163453 547152246 280880580 619364368 901142772 910254838 807607023 401579461 774932658 627171710 959409054 295659825 570967543 956717051 211096334 170928169 261754572 785319238 977518486 218860734 446586791 912472666 125702718 399022018 329166676 730451736 81797415 562379067 446891821 839311432 461395550 582145211 301104528 946628668 612447900 287501670 632917304 155485941 961688846 531849885 153835760 995621758 239888573 769228218 942473316 431353435 185541272 197878963 966977491 543825203 113651124 949495828 686779376 670480759 224562889 250363496 966975323 855662355 921403474 703489804 534716932 465281057 923381424 289122852 490711152 516092634 91284445 758060294 422230801 514883638 621997405 404341438 49446117 571580236 387336309 810834919 67574166 997821216 471184079 825590954 557094014 111894028 445673161 464437815 547505750 203251603 185464575 565112477 701859625 554365826 378124596 212295766 695211885 641813669 692925343 286468002 386565442 537742062 430445783 990832473 917640241 580850260 517101480 111116363 140529327 384521663 823786544 747422289 398096042 578613549 883396078 713163788 414644724 548680783 330963632 64295071 549365667 128201100 480972341 846484640 711354105 329942829 843181962 125654119 13296584 964353762 530783728 398603209 572495372 406260039 168202107 218589467 464676644 934879301 311383992 172172743 550540021 412930695 567552940 517939119 970419804 593348498 576385497 857583209 422530936 879783841 88239856 121071130 679479429 830843264 360910816 79174595 71066722 327121214 573500577 170629750 174574380 931919106 519109111 972727864 652968573 216613896 347512111 431609140 903727147 413577137 960785413 483350994 903804729 755109006 960553983 873688524 727777362 885923580 962417445 460572861 685236613 257309570 53984433 650582900 769448091 959327579 116311229 671403000 172189852 887548510 358487829 365233791 430206344 915270911 451373233 52310628 398142386 121385526 74403115 662984806 653073336 456716011 9953423 877521609 229360987 194513421 399544669 4457098 252704077 358701551 697440132 33727348 222706545 139468283 767778500 935660121 408469917 251007604 534764191 260244931 236667533 749895688 440718308 294943395 221941781 82115243 538696387 38863122 111570154 957632961 455257449 574715311 577085828 37318259 330798822 799054151 212452702 659625306 571254446 90425309 409647393 813727456 233117336 241926536 136880768 989701438 786541231 700126082 891613084 191040823 47178725 880239500 430018944 394492166 190524867 565002761 967305003 779335692 932583018 341994852 720563776 643283194 413005069 844576376 139575099 673771790 802457679 591567500 293681761 78351198 691431403 279859155 397731739 500976908 435267127 985031115 750885243 995340077 627675591 333559581 703244635 3019749 65947554 995280727 71818145 32492071 34495940 928505409 504938339 872257287 564063565 517749391 89212506 843056246 882222446 853773182 342298563 23976812 432659752 898961344 115815894 126954691 247792708 592583061 713679666 873635640 768706839 217859403 220878777 305794534 341120334 666838140 35615690 471634281 14518631 893789655 443830062 739571750 137879103 590257707 700101410 540941659 799242558 395221814 54057998 403920496 883137684 175374208 948623905 561523812 420503138 679728925 818252782 373519574 746881299 249234028 524889240 50410290 548504284 8445403 120556198 290275374 210308258 798462468 842602893 97365304 548372925 947167723 695802724 234158527 340890890 186423642 710326640 33513463 411252965 691457380 682425607 60079246 974541901 363526319 492348660 833902786 660635183 334551033 679140424 315944210 964828822 926297040 952667689 484870443 757635231 334578108 498307775 315045593 82030709 471662172 928606126 83209542 467408450 231531384 348915750 800190715 848932857 939950853 411231030 876518039 368616783 614631457 253411938 907488548 585606854 543451104 571676040 802743715 188839642 447171250 605153743 814467176 202024823 436921706 765621288 341821924 931047123 118622061 907034898 540204066 825208325 502282720 572602455 653435664 819730553 12727971 896885084 854408875 176713899 491777897 482484169 42310329 940011891 955510712 461528646 147906275 726608819 302222466 928347020 766088295 69030086 638552442 968927449 418724145 41692185 337520166 983201509 80711335 606129045 619159 906621998 236000244 418568049 757453657 187356343 204371638 696848444 594632821 4723981 658178326 846278809 907822784 653932508 573475045 615445140 167195538 343002481 602472441 578558713 380325456 811928663 362692914 221649559 34314508 294145152 89336021 112368817 960146240 889407410 746061851 839587950 349671710 539064722 118680101 167226370 185038064 513786099 787223332 220277980 30727642 805160245 673842903 338943098 361752745 611879872 164278083 343831699 933143735 424731591 494820779 461738477 663996363 129258703 158362883 693476490 845453369 288284721 814028325 354295597 370655828 956644277 464940257 290731126 13606741 276254354 205863329 548178834 393863273 850486589 422924367 219550697 198960131 792709713 65609972 801134057 993535260 65524232 199149192 586980656 723475444 595898069 3721555 683143697 978344053 879046373 314317912 868836845 562341216 723019898 618281827 289710556 752648560 179738518 651455241 371154917 306921554 940418496 691451790 184695790 284732829 818408185 749017226 101629098 739884844 815405996 844966681 4138070 443770334 473550719 748195884 689986855 839559330 202236752 85255649 762832487 181252555 371629487 837588841 122222543 262008002 662278155 470514437 797049325 717190697 320108805 418286935 960839695 737010531 97217981 340069210 449624396 232219704 160691973 498565599 411728179 358085316 664186458 160627478 57754182 563804024 930880894 19748608 68029001 446880008 862960268 64519870 539180610 58064899 733887769 913445615 412316108 528704185 537954810 581794330 889051815 38319283 560093467 695247704 190651082 968673192 421500059 901032126 197596865 317240760 77661210 311097994 585543218 986877431 759934459 233012868 377853911 801623208 715578265 769937157 709573999 96186730 510340338 496863533 653042858 517048205 199312432 819856517 317421578 487744727 573283386 600084339 994775166 314327541 67434134 554874191 791247416 526903504 535707809 41852086 126144975 110412460 596969025 375582587 392883806 316294037 438177838 433259421 407847312 763531618 995910055 169298344 495987552 232923314 151945324 798656280 910820681 585640021 683232011 923978643 12301666 452634331 53862223 199017589 245512929 54831528 969915624 245050604 508393477 737960433 820945824 301269093 265720816 506187831 478902377 405433326 572714130 184350818 331443651 6761033 594055293 451607111 197565216 626414909 837551007 194939327 855534026 147587150 26436059 707475908 143194440 260679631 686421167 685473944 946337338 561204375 264620510 693618033 240162093 428663259 84680453 408719754 700702125 561816305 98623791 107774680 156842260 445547286 159599506 331593415 349269154 941241436 114988180 676940196 531028704 68585691 125884452 198482516 456605733 152494905 242211632 840198282 224505385 193090641 903596615 770648492 364741538 256070305 961246856 27273728 990589423 130286370 307652164 744307105 897226341 541915979 806833872 662835054 212880155 11373270 1559163 18925792 755869046 479357959 864530529 148653807 179111987 179527040 502776056 812472489 488606520 792729599 328657077 854046500 690922821 655190582 403052193 101795879 384489780 12225682 827972400 579595567 678513865 889899092 624337534 4012298 160564132 807506672 148751098 49965954 888590739 60011662 969325277 8719855 845458946 775836535 189032191 738704333 644639823 94105488 445417674 421055648 835791798 127045402 463161736 731228198 140507866 476421594 841881889 982057233 704030784 884366134 242353242 391782440 721416933 623633809 822189305 395484870 970247861 803201686 464841329 315961296 130960838 293345535 357008252 409206325 715235138 199137963 878305630 422463888 758293268 50101658 668046684 174441370 608745112 272024673 487593489 66071877 506631856 288335770 978917907 837608396 654154893 314704506 272371596 738408070 22366545 691555679 276429016 707210894 709643517 402978766 312188250 263855127 673474634 293203002 974168255 882146850 636010552 777655416 910529483 395083840 846608950 497005437 839994086 928019436 742553193 150033281 44803883 365960744 844139678 513273140 800005322 44472669 54958183 588933991 485792477 269175163 905594417 672473420 263798218 179271035 812953894 480401048 227951616 91746087 652355116 988550816 429292998 713787384 520507002 290443202 451058375 863639587 560134585 161842388 620138850 669758720 817637250 506707176 94039513 653047799 900669353 935070897 84682992 868614809 420462829 186722516 263426639 76450812 962229705 345781355 842715946 112379854 384878008 998369253 121731764 582403120 257961789 954719230 104681771 249092797 989303675 502476775 605138987 15056579 861740740 572031417 507768509 935887112 603240527 697970213 305259641 866752171 973127858 351803879 914270712 19316268 10893711 526738375 116299766 188583145 306188898 380332703 799842442 715206366 792926777 118405138 796840355 343652437 921344628 44658097 322735728 189262750 534441861 44443992 424532366 659817594 675088861 535273688 9846005 714852705 823572095 746583227 832360080 567036709 549323217 810556291 621362625 315831694 232611278 606207114 506727911 988999224 740221958 230344116 163049122 689975851 732394939 829466194 100477383 599545733 535954282 852224221 203654418 252528810 280685945 437067623 668042493 51451267 693255528 76472791 624682784 339566224 646606904 168224347 965303317 438466818 234752819 924224689 680726881 967326668 885700660 34999669 673299186 61084198 332114717 738331476 780794799 56352901 263989232 596291587 202814423 32309645 214508531 507499966 714538565 698232822 844440642 759959113 815951096 381801863 847512982 331686158 142018144 867924711 395542084 67100579 161154891 95050545 464548009 770352207 41611541 966096703 759217026 964251748 959761700 958841703 901047517 945076929 467908156 713605737 324112813 527279362 504984135 175076467 81014988 304143106 409899109 214186529 790324480 465003590 838358713 452080300 936265889 899107725 759504829 451616452 982909489 1090619 954026021 685859921 500574910 871994036 401456740 94067488 74087201 409514463 147817749 403335511 914110102 606627183 217776459 241051758 207805933 561894887 675976015 855396113 597950059 658767930 363572482 667312438 185399542 834276128 217432008 19696429 914144358 147081855 515600877 193207163 567344499 116418931 243922482 801433547 213691509 760614151 921013093 42576378 273667520 468436223 293824257 404912431 292972761 918323044 980940538 436784353 524342863 177610552 318438399 189529329 928594143 902357595 792042145 217565939 751057448 582489249 723557338 320872556 341253207 979148497 538867709 991507418 933011067 51861066 464499731 180960431 151160982 621013290 880866352 145435143 661957947 932975859 569399465 811206461 630713722 945860210 510095999 94680954 125485064 116376713 763386711 627522158 834523089 403707727 869166369 295138679 112561593 103971693 445400560 269038218 492577484 556119606 613674486 875221333 91683019 112480237 129724286 720245077 389221279 518288183 779368316 225273958 389472431 796147017 605935868 780924185 318802793 263381311 771500699 519692344 506390614 630623894 493817968 549061650 608255903 524901279 232312272 940943176 646245632 864178418 573873106 829006211 627544231 475186808 562308692 324876497 607481605 212895138 259441351 280453823 670810948 706822031 371973991 53166652 286765517 153293788 843019406 683411427 84241257 298599197 422788466 281413213 179179883 748796230 697231531 910112826 541058700 908814633 679896096 10378690 424368218 435731868 440004287 66929862 919740504 906060317 943492991 83035155 144269292 90079021 183848694 797642427 328451223 521306234 151984992 921537198 45615212 997897592 380754907 924001148 436858009 884951486 857189070 705933966 519157450 60416167 447056107 440336892 425904910 598654951 560329747 740378342 757623989 678994478 306719863 376041554 546787640 184139100 567308313 952786636 735699820 285690012 226876774 193064907 492284346 349793370 772699207 830347457 247862093 411915319 835997768 195142600 526761957 520786348 314154443 605973778 583690286 520680407 12983001 891290701 595591736 489528783 352373573 179737485 835310801 567172433 414526860 378172506 440371773 360712291 326523210 84521038 277924493 397932690 768475119 584263630 83268154 188781420 910966705 786566176 741904669 650648706 702491904 653311724 911950655 835579550 556391149 749294903 403742171 774587108 800205620 835407466 996012854 612041914 936895400 982723319 963153217 155950683 781104626 1053795 196430606 210191861 844329440 250984158 744954734 102950903 185804950 296940646 91526902 280329253 72151890 716919228 866850990 622144976 714913930 521702800 736075204 763182745 613299107 565398228 248064370 500594329 417565219 515758723 794587371 747930476 60035815 65965764 898782243 197659198 254802154 231398630 645496421 194376533 438483823 610613675 626680884 445751844 173338060 177610279 639858352 331203350 836501913 493921110 24326513 261128723 716823606 618701349 816361389 922103016 90816559 590500081 360042557 273809728 374602910 246597542 23845032 877723294 487779696 628629578 784871313 899970478 322041642 43765880 583195355 883746946 901856331 459156581 89547245 900661375 941861941 707032963 332397093 814055782 46921329 575187682 97938211 297465045 532520522 312138283 141687077 702813662 547671293 150790287 667199990 448711511 907517910 864682994 760167670 960435493 351934001 35867725 179928528 329128314 168628308 5204851 160902912 335792071 599384435 469567861 359883384 701310593 796391161 414430332 388434130 850633442 438153004 756030166 220394932 919153931 342807040 399325304 280815851 562096245 438038114 783971476 963356933 561400625 434032043 731385860 337686915 545293352 187511796 65555996 686745140 957707801 494966455 55681305 436555733 930366881 381433700 920190427 829891680 940153658 592984989 92481556 61392707 177018520 207365276 535330389 388284015 829855893 64657483 412871557 200786912 24413876 120602560 899079637 63446330 751384209 137160495 785575596 97338150 715490407 161522541 18308875 678500287 856906591 585181786 964284742 585619611 162081262 813564635 411216299 386291124 937516862 574471275 313100929 842960394 690900233 26145360 594697276 424504148 200948851 234793575 852281528 995461215 890315759 434030879 174585927 430985729 702890291 177888811 147288545 171070709 863974801 993168623 190776664 622521983 33367407 130149967 961216922 272213762 889720183 222705781 569429037 461617366 380178956 85076574 743996710 952377409 80877806 993899009 890904593 788354478 18116273 897166127 841334195 24223866 151872979 338846246 194779729 778205457 605713733 36756151 772177401 801214343 801267894 65448136 212223845 501704354 410531803 304431442 45561643 680391342 542695108 59733064 241227419 308179014 729482713 663962527 766011205 610881207 37794696 32656421 861609945 733279979 322466551 994342982 711243430 960842761 115145548 125711235 824432954 138833042 635593430 484344790 656741919 695001916 695314111 228163920 744388703 833581120 954525173 597112498 468835762 705576210 784526666 78455387 673930380 994670186 398977762 17668483 891242110 601307301 548104072 223284395 244355016 312273056 846183643 762803201 9599646 252483480 229680691 690116539 821745601 913533889 454120759 680675872 94340882 914248363 343362049 792338840 44624197 787055336 444573009 896552581 894321474 806155953 133358565 831006474 185363185 625439304 201594650 371460378 481945097 612846350 769265545 583104744 8847067 730931408 542708955 632137503 435092700 488880431 125042391 373475941 189572563 388008202 228179270 903511410 481985311 800185897 275876828 216037319 892320074 896785377 387948413 329037854 732179837 15231148 39502758 979642971 821724869 282414146 566350170 699585864 270217653 870957485 987173147 784918950 902521676 548172143 511454475 128154954 198016045 181664239 354372174 870627534 764931683 223744158 668915642 405562536 177912929 433455462 192483696 981593123 378606244 875227172 579450856 351341021 150345546 612520881 920015860 924948789 503736911 189683146 24583932 334435684 178464166 552437888 155614556 317439071 109386736 224602136 817047160 279895908 306552126 453845393 344981160 703741192 546793063 421427332 590241872 900604009 909943874 129254437 229942882 164243395 59337392 22332694 805416190 597187383 261202960 956424515 650306813 250445696 161073172 600732937 465726187 454611297 940642262 485648626 517761577 587124904 522147697 518544641 703104568 30551193 278839032 139454136 55973342 762632295 262149616 257006368 486868729 178494962 234617660 467640596 562155701 192168935 971358857 732904694 192257902 977627158 984043375 976239708 12775801 483610171 355071072 908342157 662596893 951898759 24290398 635896727 809691872 461427387 127614059 229722152 700541747 152287557 780818399 793336607 842900138 411481690 670368878 690414907 631870447 349105904 547111394 358992305 832201904 297940736 12053739 601607688 699539629 535314043 83303552 824536680 602484420 673296490 889724025 477131493 566236046 177148849 353336695 875973514 545941935 753438263 5387121 790595517 130409363 164979350 689864558 111107236 29446175 661961922 105826060 746949759 193780672 215151975 141939233 644624986 916408286 161372766 182171280 625635194 257578918 552690027 882585492 189688729 689857090 283566081 910955118 698769982 870265245 65063442 331689027 541849181 887091322 147945984 439828970 205359293 501263091 758846467 84194935 259257383 686146331 912769698 758818359 371305326 873219663 273932446 824433103 732563816 520448535 243781001 191936474 5033215 49582230 414076460 154457459 768559003 540413721 903923113 994172044 769837559 344780518 137888142 667606360 273523627 589378130 68897871 645312725 836593366 301064249 220998540 658061701 615420236 116134030 755564610 194760509 254264274 559052736 847976471 573004657 768472684 107474339 313648710 930440942 40679980 438311208 721671363 686036259 399343513 691533633 275956343 720103283 692343857 439776394 888011154 498851340 641033533 536345727 988268522 604754037 539570806 683611680 365885372 62724678 418791946 547920779 347314107 611661595 132044463 504079963 844595089 752188492 841739396 658277738 663697986 298315048 629921929 37280179 165452995 20350763 354570402 686250719 136387215 238915536 996903252 658101225 39468413 318624129 55615694 352520726 676334472 521423827 644221978 549504886 469653630 673205479 830709028 535206958 849044713 335883103 58302116 520257119 644339475 376466609 726717130 763484727 519367529 903681268 859865947 426484919 646989665 873486681 294255464 764079859 376524202 322612402 688566168 197943757 188354963 202277495 466026597 599122218 893355096 384042284 284754909 521638417 708409784 280822920 905381997 563723866 430999500 56178230 148791241 693447876 618365446 924874126 659122142 547780113 138696681 121388814 198327852 12662661 157155802 727512591 379213910 8874591 18123404 405714315 915306621 364850954 322142578 834813147 340018255 51802249 22659773 145154104 576931894 315227505 600389295 211509660 970785264 365107009 344201806 296012440 298679310 117707257 774704207 206386242 647587720 926163612 103615711 15529495 782437131 534083354 907754260 99187214 44528385 453716024 505655393 114219721 859166020 253277067 717903646 839159328 430970282 560417547 145141291 12784992 143002359 2364945 952032058 369910109 919703278 437800640 558425209 624165270 372519183 149096327 33439357 776086451 820374387 692237210 302642341 625234844 304897927 709872174 217044894 984447935 933173240 642833004 814978306 782847512 350053213 197663964 719441291 905229646 829678227 990832503 55155508 355379400 484291972 671109232 807964085 709259574 910932916 274993552 466569745 103613389 366877274 679028143 630790141 402116000 307236362 938523759 104984536 113754481 997906276 533863283 649179363 978680584 489795042 150553530 878417196 460560709 702200791 493052691 893325753 219763170 801298152 748753398 717827254 720019522 701448007 979103948 904885453 627044663 980642130 799586118 155444382 478694899 45617983 927144951 152100950 83404610 156444260 308816837 226049538 280815736 214723590 712984839 907542203 572770456 714649348 557287422 826249625 904371389 273277633 885226305 63837012 696945759 907447464 385593880 667762498 463925542 62340951 101728392 129364486 786444931 63884837 506188582 742955736 600554900 547844369 253726634 693737073 118182430 786964047 582561848 784359141 938264518 108906397 750175256 981998139 124934594 577693721 382540235 544597507 61426872 246157703 330383940 726813667 509812658 913461992 786371698 849166748 499237122 917622369 574779471 479538197 863555784 926272061 810150602 281703045 590872290 468495067 491630407 653886700 723273257 475792249 91268378 49871232 648987431 911192326 171830713 50045647 8335304 592836995 474958426 49725209 539377149 133345106 524346129 342408064 422432330 980809319 439636674 397369715 651076151 463939011 531684828 30718979 720392628 505799327 103622036 728979390 243867823 911597472 297761767 652269176 704168993 380447403 466953794 383707574 329115146 304042341 399783917 631876770 434474941 52344797 359405767 178743892 565023565 504055378 701291381 6747669 422871547 644658365 289429936 861756218 128890738 854803179 835247231 404907544 503676268 164830304 18644991 483179163 166593417 16177153 24076688 78749497 675885365 596617766 222618102 869287832 213507021 393839232 767814106 499343184 452371925 421401310 41071017 96722112 931248751 433953043 202023998 2502699 156941728 76605211 669274393 370103344 611080454 159119334 603920207 244212110 169399561 352236695 397277104 986611790 157502712 454823533 608115071 770859070 334598879 750965265 664750049 134869865 684516966 780742349 182688315 838828511 623518024 392827294 766606833 120202658 432227804 177545405 311773152 728359997 662726524 132555182 818196469 234323854 442902831 667366960 632614926 188173844 933175316 175694383 468746093 894721702 323302872 404911813 983065437 320222706 280065042 629085706 637864476 867496253 464040567 226198585 929733885 168026883 872616876 101954351 242299937 357125655 286920722 563232601 867523203 507403160 905890659 685761180 478779073 497615845 447661100 45439672 208038337 854998547 146365443 384135820 733635541 311714554 434087645 492481140 507360878 507891879 888817819 338625230 601070923 518347085 668843450 418109619 122942219 506627758 14103762 1655446 809272534 663157907 50846080 611013899 134875273 774398913 615770017 745018259 77245836 923018654 851173188 836140581 818562553 326694598 97991354 260358672 55101939 592589696 16751670 208769039 913806253 368584226 738150345 507553013 536673480 699498987 229170906 333655397 299603795 300906983 454446636 897531669 75714977 414428490 516135968 872850246 454440071 141989741 922242980 858014458 985576586 923375018 819521965 808333903 258625481 638117141 242425613 923790713 457122980 211578894 686686032 299402079 278236636 383829297 80876894 17590226 190801892 772090408 170638755 699773870 659474425 602224109 570228400 643255260 506149680 596670604 99872168 995683066 157761959 845792762 293383013 299837880 365654074 932699484 110086733 653752822 627662715 769918526 352864836 543410961 129777095 196991303 217755068 626242804 507707012 304020560 870876086 772795238 146073914 125893156 259405468 51296982 448472765 999425956 262010423 996068869 467726289 710769661 220703588 7109313 252774280 68404855 273892507 546640023 95441958 718953062 335855973 531463599 723570664 645404996 100583845 960827081 141554246 632464682 850554427 1892899 848213225 99373649 839415353 3305072 226288912 650290176 510625536 886742903 986909075 805156425 183977326 132441080 233548097 994717639 163744944 823712765 378785930 642314036 524317864 534455361 277194027 138224141 343021339 959985937 330700939 631299628 559971064 223509016 358697970 724622871 338950374 496852623 911944173 539790870 122256650 604233107 733152718 896659584 60184086 421764519 842245226 996072566 149363000 323878174 443029704 461973668 933756688 482051574 530999174 631717089 661045835 203177170 827694680 830315640 201852903 557069586 902385988 42411523 139345170 528178889 71578666 937139508 234900346 719336474 724065262 903631952 937543421 9723038 15033732 432164956 899712756 440254163 646385964 406966891 211657884 272892149 519285943 256230887 596606195 592302068 54558727 293243437 397081106 825689613 650530657 355738419 310855645 127127212 137995982 150211244 437552995 74357141 828098138 691208002 911554761 567745118 289033094 315391046 814468808 102159077 867750277 884951853 974886809 743104610 57501418 678795939 921597491 609124988 543552037 822589529 609010189 514558795 408132069 915585273 483605142 622156066 890394017 274110940 114207204 596323505 954526948 195312508 526348677 328064924 974125384 132417749 824640073 955793563 176441421 212279980 872725115 656532412 267389204 180750611 147003503 694626303 366380858 460615086 259932183 45629172 86635021 395136274 636558431 757790826 197021023 38033936 952316267 159463702 769416362 663965168 932476864 295320536 352720152 903860121 158554058 195682745 400963640 464036611 512123078 10295579 626398340 439717762 652734524 819963906 935155740 470885368 517841713 366620849 247317707 365419617 745978194 695304455 497396404 300929841 360018643 101454302 975804573 547922539 158551008 35824317 505534324 583958737 406625806 89679376 677712738 7824172 402000335 607965355 999848670 346699627 832156475 241604375 674434741 475726327 996661054 126383060 234254598 251689354 617802798 780110746 153525801 179892036 221949911 47490875 148266088 580392835 769922699 939761232 320512937 156974843 125186680 350531414 812886284 975493355 55288596 857917954 774219610 269200470 199250963 14212898 323478305 864503991 939305666 186709525 795944003 284232545 480203774 546363210 898802326 175326418 957332718 744725378 857086896 828055630 813073393 104718026 137787533 424109844 449434046 348604543 670332892 756560386 687325225 458873530 484240358 506739460 445335933 817225164 536246569 508117235 353105801 286598296 954573236 557510271 499056817 24990134 570152942 297276467 895171271 72112988 94770914 52018815 441625409 795743246 633429431 588834284 563481150 179610573 950194172 926031782 345496395 375139378 438844342 151855860 937758299 512203817 555453622 858067132 475718642 196831235 351334693 134848036 437886515 534650898 81469056 20649876 640606164 666624270 863624008 26125832 282837355 337624025 312962644 543681240 148607396 728790455 590338536 67518547 247888168 851950020 572017079 653086486 528263647 50020647 894788146 674912738 473213610 283165873 551962591 948883248 274592917 759034335 939335978 685730979 136503231 329896369 780739548 569038782 147930570 813654633 33288733 801296817 18078029 773974907 594016195 48961106 970203665 232195452 641497292 421137946 859049184 585892728 565723882 531195562 438811076 622296824 312365183 176631151 941382506 776075821 317304948 605874893 209726817 667883436 85720219 862994151 503302429 840652834 506851228 469697499 389139329 493710483 649012428 141481036 444289697 799791376 585443998 279685082 616884784 117000012 624559240 337739549 270997211 507344183 600388933 547697480 125127763 516959993 891066682 897640013 388728815 122460640 923672520 172659017 512188008 205517422 769413144 578487305 652696099 376983268 288849136 239677294 484107227 566385808 235690129 251378800 559088630 546862792 930700837 28711875 485495267 644626472 63752145 269572780 578063315 841489513 939394720 770176920 966390274 515152155 945035786 718083400 909078928 261752744 164495513 560838342 13312760 836160457 185165803 501319804 373572137 845804144 134073876 510592660 210388844 702273752 534873795 148438608 250791676 620914832 490283704 629191263 890363200 452201221 77012997 420180486 609677638 510480256 385164536 181700369 385517593 657027767 861960384 286313178 92993143 907140814 129057983 242463521 494956188 117773589 160455197 609404805 169486001 616150319 138909909 959560038 147414114 334657289 785930759 918502909 585678228 397538447 894862904 605229378 157691101 575534433 927654281 985396245 120951674 391277376 180926394 832457965 50007305 367272548 331497173 526487878 777918248 296576874 359144567 683901549 153023749 961362614 466916167 244909703 224633604 294596182 806565091 806542786 558965130 83856144 526733417 600360097 646033430 353275071 930444404 13960239 83228050 69756054 720561480 148247939 159041798 733650533 369508192 807811592 61053026 303278525 343226987 25077820 599121361 228939626 87718466 721110415 674283983 737942189 526304530 173612816 795605473 910833043 71881467 378102402 513934203 154229971 413880183 199202767 418972645 931858068 255563441 979023536 253223050 727608042 742921837 327767562 105294036 238333600 109164131 512749228 630943086 425975333 454141370 796276499 841405017 885354027 59630666 376320017 426462512 733156191 10991458 148166331 528922142 13402778 533177310 237555993 745363163 203837772 562447683 328992215 236047165 445610446 950509373 915448662 728659647 395392848 949484364 181707288 893170092 295336429 446432380 772745540 748740459 793317760 825660391 926318201 91603508 935667121 434360423 616119316 261617277 449554330 838989118 475265487 204350804 175587721 391120413 381539996 747763923 186753574 905274202 983729191 263631178 511998804 398581783 945944997 592771805 386578155 92351102 863161781 901954626 882412868 46023991 251028728 334243946 576429553 530181726 596701889 191860467 430080117 270786987 550949745 432795039 256525010 63507553 86724017 404003217 411456803 594632629 2980149 612720280 668038352 71774382 937630900 544089974 525343542 999377835 8598443 861841018 493057864 995299633 31096766 26243777 623685034 377743067 682253623 380230604 798403459 627160970 986321324 993687710 975936720 93992583 576004867 123969120 887884439 157042821 614455839 607214845 2067952 693825665 320467713 102770976 111368203 286285171 274214254 87729415 663685317 214110872 155974203 259274683 94069331 472636836 114783838 421214939 508423823 860438175 422581032 582979434 295757530 508723220 552501444 412805323 699667712 44096639 953536286 93258398 287121992 189996376 969362993 211205268 231826728 899968117 974041939 463573998 639318770 785943014 544285376 515526644 930807743 442960275 545625818 352965719 862766853 392583898 332141530 423677786 769985684 462985018 816163332 961076305 402547668 14805887 190940994 284762996 493891780 107121264 336565801 929427548 300301820 403825705 924129831 977519824 535001220 852483769 487378792 474352145 766305914 258092310 52835349 752642048 733416352 234452564 622010448 555933434 570451402 385192576 961982624 148906549 424905632 262300343 878036319 962500140 857136426 817832776 774561397 521342616 49672599 927887977 734003815 421668542 716620715 678726210 199923458 404252515 552393188 592981127 296385922 236619822 604182641 797225101 774842218 272712472 493473792 326873753 989810406 490245647 488456616 694792705 370167718 263253538 972146519 458387114 793417300 559990347 431618055 576919405 571261884 67742103 173932160 704945686 417173998 542663388 156622218 395844348 557000419 524050156 598165454 246314214 844203881 201191109 40492273 881452022 399979246 392925683 795691291 21712949 478660942 214222054 887691030 676970956 289665040 432543922 752504548 346410923 733409443 834695500 783899805 361609577 40580874 160540497 892020349 667529914 267744188 544928127 308066982 194022010 389219640 627897774 36825547 908674608 242613598 933469059 389377874 868504499 6229412 119876078 570176353 389137213 899284275 812918851 135836568 440080850 854516512 946251749 468171046 745807658 487112366 548103271 32439472 845143202 509263594 386444296 835440780 634553283 67063555 670438075 9459383 121072159 322461619 414685260 70365591 242714739 999850098 117016258 15147923 511268196 862406164 46201654 810236721 805497656 991029876 851894601 892203274 131284013 887710066 17457226 362450474 386422422 410138992 202251613 553639197 767255371 225735962 41815046 414732873 155627234 226906005 973534319 681230381 679585714 316953861 66555268 435558456 279702421 314822470 295406631 428498235 992847712 859580420 798002215 325340577 322866799 60821003 194257350 900240301 367122690 942958205 258585244 559634701 751679692 189538637 88221187 501895517 166506679 293484713 292978175 277510186 734115015 461619841 757111462 604576632 267269684 773502571 750032366 511410139 928706650 437740094 852358499 355390141 981162528 71413824 533038836 29232997 370607170 813507481 680993004 877703148 308623502 600382820 832925149 65033521 878784743 925126357 822909050 552305659 882144794 983343771 637313086 551654992 632215902 901683672 122086613 547955849 511816555 143630595 42933438 336768419 692814645 597145106 730148887 278584907 203074206 943398241 989714580 263208659 288971164 873624738 174574939 4477144 880932457 516106256 781931774 925161416 615956308 27218548 874083582 366030096 825497280 924686884 165124490 373669113 758080682 148668567 130149635 241238412 304921 543621602 787059332 38087738 92380133 993351119 386309075 951834407 38044832 611001517 586836456 654540797 194732143 498559089 465854877 508057187 637481209 725748622 28307707 48080577 836690496 430774786 573720670 278311338 520895671 675526493 122294998 202180995 134958379 771606467 79794639 197515232 903131375 872470534 866667762 167350354 295302896 358288198 488601414 386728053 631326718 846719474 74158634 10066406 678846788 983119266 544235002 846683728 768684569 701831360 554866824 183900174 111055960 625945929 119621138 709148988 416130794 171518866 273718955 416609044 452374235 744764842 395632725 382561859 992473636 933740286 412727455 450143725 454339561 581754077 848277373 812195961 26683347 136034166 233706907 744927696 836148706 255514203 731121331 990135009 755169264 665087056 259179057 565431866 334020309 5028456 65309430 796631034 462439338 553875468 567517530 700981201 199338936 326827598 630985978 231958848 555284939 61324651 932953558 443894156 251445638 904071632 91616854 106668380 818641571 382278380 131884405 346469797 127073283 164737070 176658331 298175547 165533946 649675506 983996427 709001577 810807777 25825066 798213541 752921404 464021679 876180595 600035055 712910776 879589091 881482238 83762716 515868366 700819669 749117508 867624281 606256692 149148814 175152597 569748740 202891366 824275056 740406386 422358558 373294717 571413784 959355552 219744789 496660875 98640452 822306032 223460312 875417508 299288139 691411525 506126199 442903761 697090950 190115246 381616611 537728525 808858961 139413267 525613976 551467054 562690244 784588260 71178804 273661260 848953492 679967542 6752710 965398702 274518984 79670944 199729307 489471544 774108712 457708391 111330932 251298521 770436315 555266041 5089978 691094407 509396876 846309761 131947296 685481554 298453365 510087249 903166866 427770982 994183439 401701854 544371266 263035140 895455252 386263526 719596422 50015057 456776585 30422089 386042291 40640075 25015996 575206550 903978571 33902902 283060406 409508157 600996794 839065254 745308524 753355847 447552351 429334086 559586591 789067206 816707570 777534313 923619791 156767645 3490164 326825037 595232277 184631735 999765552 589701801 565738834 845115079 143556949 105561200 855414552 623639381 575029165 179765499 286493390 928518941 775700952 624847658 778984898 548850294 886811838 417280560 311968531 934729731 494213044 451762188 890309675 701242397 330873537 740530203 174448571 979533307 37411862 679728770 467675563 805901376 92427510 740846770 437881319 169854034 87382366 885893615 784041695 166648809 188068727 534065988 374671570 716880847 362115708 299599872 597293017 838628393 428475823 390336385 503868514 565643254 322468632 309921207 134532223 392796818 993933671 789794821 296319593 957815822 844680918 27128527 288580452 412242380 546169014 799158202 154121110 236131292 893759722 731128179 124739696 767480976 187686891 423070483 979703741 371633993 573859958 689324008 82002738 406355730 123740925 374083121 264148885 149106825 928860177 7019751 445279202 863892999 582265840 526436241 644839617 681356615 519653729 885392252 763839144 948444142 403545882 171346784 309307818 939644225 114245287 905230111 896058409 92668923 724088144 75299019 455146859 285397350 792563149 729046386 271682793 671393049 348115103 257871840 255117049 567445515 389968005 919838064 780210864 183098859 725285981 351926320 422078844 209368329 481759219 411679067 417628112 567784763 934701870 386516094 520146646 853149616 45549949 535497621 453607900 91155595 712944859 841672158 626463826 548181636 529202767 402802887 417427515 163582595 357846722 864252780 812257417 178765119 299087729 880789791 643230413 181998300 289878038 605338241 182338739 808602447 346745177 354165100 463898579 983868202 159493918 742189216 888974025 887382851 691605864 962201796 397681741 784607567 651467846 381576655 619056937 812410073 133241301 23942908 832862952 533288396 556190420 706330084 542772660 167324472 878687525 920139997 783122922 466208059 253105139 923240312 607451102 70323175 98705845 787425570 259898252 263867689 482898642 297991598 362064499 455883357 651414362 998382746 687911548 624135008 172758159 321587386 205832580 786845381 52544454 550589570 576184210 252842798 122954226 342772785 68656227 647814015 268646660 168379435 349225498 242800798 563202030 322246020 51608394 906187565 62890755 132973112 841724292 563175381 943700077 716990165 482468857 643726290 432675088 599801993 464952773 913417909 838440156 886845521 174297181 859423037 144080609 436256169 464224066 509399245 507327931 830482042 414296097 23540605 490275264 418755061 4128700 464134451 488848758 504220323 355725306 923031894 179294817 964952359 41907552 301458271 576458676 454688682 37383522 880160477 691196413 445051119 79201747 798238549 669575804 5092946 213184401 348990775 535401539 515618882 918552815 789191317 283992708 774914624 538609793 98518584 586115356 849956802 493409201 788087822 956725597 884142206 431331581 676564287 77029660 100990774 689028046 280120345 386761548 795679361 100051182 615152604 896087076 925816655 826543966 322420216 915860234 383362939 818613585 885954334 536904373 425445726 143609376 653198010 872511979 478062654 511710640 443467093 435523121 408960579 172393709 854702428 377349236 840623472 113996090 303963602 449476214 478205725 389361685 241170990 439753956 237950727 966192676 499837655 920729088 47301224 891133637 50172181 563098550 57327095 719779457 421829465 104874804 60681756 136863646 204215269 620003534 684089587 836105277 515713633 746032435 354027567 989954127 379230595 459190209 689083798 786282149 35384546 230218552 314367821 390558254 367499656 561952062 724851725 484970132 570875602 59531883 738800934 995204468 754840912 78963883 913298497 324173071 367700183 355311558 565690528 31010101 745333773 747092903 422622448 412422413 33003883 720499640 457859716 429333975 561589806 511071574 877582029 270234096 84369063 69758979 54220489 27350635 224556760 156336918 224712085 284481345 938714348 970467717 74439021 255911707 674067554 897036702 682891139 682334004 361583263 628532101 360651797 268192654 129822965 657147973 449700324 649672840 101217762 900029568 370911520 906006054 312223294 732848846 905303728 489395109 417163952 613014366 600955804 249295294 643440845 630729712 158118931 391785419 479758907 43388318 904055739 749205434 831351641 139125365 910335604 472133804 164698999 604559607 703115477 106260754 302421342 108794855 786379093 220040693 595991745 682682818 644858032 122561359 794366889 994371180 463704979 400356284 900944749 77593740 332846568 730544004 45391988 939448260 172849644 747459645 32446856 694122787 394254507 280735104 924021072 75867931 392450984 502590692 186648202 969291166 284711845 957056740 532032978 751715008 854992415 958205957 298247428 17964281 916219134 880629250 782722114 602723801 300312427 693836949 330945855 632857123 405034645 61646822 707691463 738244755 766460971 114687643 597230014 84356750 979604298 863785334 277608331 825615213 591273057 237215502 139495453 131447252 363017993 56734450 835830318 525723606 713068967 405198229 283626339 777092918 750140050 849828864 338535530 557751688 305179586 765296247 836496906 79755617 836475535 523386326 470967640 652524756 256534390 882878739 40462385 767292756 223998284 404242947 366632955 791595086 519338708 836888884 320758605 490302432 928580537 968109065 94763203 423129154 884905927 496781726 65831009 299052778 644328121 793751782 301084331 795864501 319999381 455075946 165965409 331452745 882039207 942643082 387908152 158847433 598577716 265818607 802194352 759091927 92168725 92595263 401790257 337358043 597626604 222269749 25304535 754197330 407094571 415038223 360474157 114374362 290798716 896371547 993872278 612425283 693145815 752975948 95568192 922122768 169872952 58074523 350605612 194727036 189767180 130292383 813378299 579707065 551582968 394351148 107873107 536096863 131358116 2959640 483546297 200504002 986154118 655734966 586151144 809831840 396738870 948834364 853619920 936958263 773926978 472481181 403222867 833002746 411860000 685110831 357407363 930605312 417734700 102952476 247313634 952155865 243285851 401132219 435945705 691595780 691240478 803591628 183949350 457835786 63146576 399144262 822139101 144690365 887230502 342850309 544175614 642339591 940667349 946708338 153599229 747639579 724896820 420701268 20877187 237183149 221047460 61873842 872947015 413057938 341433585 400868906 460288842 245080540 589376077 675842513 750811231 446347551 770809249 814671064 977390222 115807944 285435494 247740184 523986134 349921320 321366314 553372656 446728904 806143655 834656763 442244256 79686856 137921343 303939299 530209606 124317407 511146170 91156659 923198001 336567835 755823359 633470676 863749330 141601477 757352640 350699002 664975593 474146127 305763439 929643573 311011853 879098498 108050262 784587418 438244620 444498017 41118402 875839086 761783436 775156505 946593514 469910667 287905599 763573885 512816769 760765154 94812417 954385768 675810455 847225764 888370854 424202873 825052380 323392953 592084761 170666531 199861605 523678143 634977925 398835447 689518088 249375887 409134663 951238024 739485240 957722200 210215488 607298503 854972294 925915253 307353324 501225442 872383272 711019619 149572563 413314249 532896369 352075797 968516848 882063144 187572147 633756912 624204635 683260637 640196332 422843350 732262024 212623875 95843568 561537711 256243090 191627700 36347470 157755885 523996565 158465408 148050107 845169387 287457195 689850692 445075892 828728325 73738191 772457527 678751117 309077634 833110668 268677513 419616321 356730548 265634739 829153861 714824657 39746722 270237687 738954439 535780748 793267057 603425333 155624635 866971449 742497201 33196012 631690764 978517876 180145883 328860418 103067960 356607215 273076866 219237685 75489507 825338604 589813310 688106298 226368857 421460036 349954889 442970612 247907908 623928092 688570119 205417626 442876760 90259695 383873068 320967125 317037991 311460300 736274070 593869112 427023820 720226291 823122215 816408436 790574041 129576165 538672426 109695503 764007880 750635698 406175753 428536722 971860409 951681910 502297389 739796747 433615570 841559773 237726682 872819372 785889611 358169304 606896354 601223007 524362510 938949540 659838097 465112752 582947250 870354981 806657985 326962064 688479196 835549847 476831545 896745660 653576868 985381254 99034151 14109410 739872697 481704363 210701540 467325441 95764374 42016170 258746839 518509177 970045845 640930050 713258633 128202559 363718280 491235855 24608212 494211847 211057173 482210570 641867492 881912226 297348513 845667529 348071054 596602499 409956417 354278418 17560502 181544508 682523171 438416863 164965900 694811169 495731960 296725850 327471481 978877127 424409110 134498677 35670209 772024710 617658154 808605019 407948140 981238019 229678838 307035288 913994005 431577340 413032019 17248032 650365992 494447477 288092765 715582119 251355477 572204902 822640399 668357942 908580498 952822564 819942378 405385510 620359077 847605640 113900177 292992024 855118244 867109269 513066525 384072965 50677740 983458149 194465764 497878988 432622084 457340692 811629505 626221406 310179886 889304918 3199593 572582074 477729163 680002369 738576272 906444286 435530956 773217755 750752950 510340330 556474873 707518646 434656574 68083755 919038265 143919143 48606006 98990630 543479794 172956839 879136456 597289369 92297041 668041425 513267491 954193370 501590785 653978709 320792084 791210150 412234581 339463510 261436023 239255015 974311408 937451621 792507429 384222113 551438491 313172613 822276643 344161057 890270978 579764539 708773908 227558694 422194082 57856344 384567689 981003194 897145543 157776841 952616630 505406826 522445015 189438296 969324698 993804908 91858207 391460750 46948488 14476708 281930378 462028055 72609590 677819872 794550242 11680971 975079856 234248658 408040427 913264423 558584945 556697996 225728503 845187969 966088256 271545705 583472296 87788394 99474748 375484170 689158736 93784101 92978893 275775935 251556029 595590292 256944551 533235131 137488413 195754645 845043530 590133891 640160365 1233258 378515542 301110137 803246806 975038589 930551740 729245638 621376759 185463098 842978595 950111509 914784060 7246835 441885126 255187436 481719184 872472305 830375922 347221342 384875100 261518304 172451676 761503266 186366338 974093913 714969518 669501066 759128268 113337231 313193952 468791751 261011913 766458602 383717155 632790800 642002634 765817749 976231433 385628360 986177674 685156337 268128229 34965784 280152007 965594684 994153816 595034056 201383146 701701594 643973354 473277476 975977733 654342288 225708714 989396909 650354764 827109077 801173123 811127209 528686398 858075451 162103711 695698448 463496414 277644606 15293050 341690626 955812671 683770740 972869302 508091904 70132356 233323700 862423258 624131422 335081537 766477444 256205823 876324748 560572564 921488162 310823035 652713217 724648246 889971585 665964024 386193288 276839612 965798816 195561945 359938726 769168390 790138709 275885509 212162369 200935268 555240337 136490758 451915680 779814545 342654035 11455815 722478552 530814028 8241929 695226995 227469276 788269999 435161399 730699500 273550449 686769912 733775430 583441489 342091244 317894158 829035213 567473119 243065216 874731851 424300225 32583875 443635928 389668254 226942477 964288578 520255502 248002116 554682168 14286533 228744102 586194076 579804704 416425897 996926471 655261258 906721521 861038031 747295538 833932485 390392418 325070968 84297847 940202123 890682726 978318716 716761664 932032536 400667712 514440480 918411199 766944533 893226657 762242613 199149973 755516119 586123142 906332715 710798048 985421331 745403789 540851417 240302133 491247052 822748083 565269518 651299647 622215502 674874548 342557864 974628077 227027655 940886436 828371269 876374627 684867193 783280917 561837378 257928670 707329891 135132441 516333278 278925994 101458469 172701173 140118421 106779838 93582198 860544116 285348560 354624296 282322752 334377464 708923554 95021389 122597240 412836689 24548542 854899062 987014907 308413732 252664773 386214027 143639822 363851179 829509778 748215961 407217049 424899294 240098243 265498434 132798316 903476118 489601346 878952418 635044153 144921236 846295128 875110527 932736985 925333187 615424137 757129740 976252669 634186547 841086757 354877389 646570660 385920386 502319825 112455128 889144357 222482766 955293947 742338628 326517277 65539145 576903859 202572255 682496655 828963709 52651871 796708264 841147882 364214606 805803397 378114399 489639934 766254661 233193379 376712533 79467715 176951119 759257630 76099446 450841062 75629233 72955317 124409327 455726095 210047800 116964554 238401370 482441772 691017885 565223863 985415308 15766874 323831832 279534775 133478143 488739378 281365957 970136553 530537000 313895282 617049962 406139494 697231291 381386442 578866812 702310138 134622553 628651066 4291511 637416417 802817675 811125086 364853575 590265073 815521102 16541867 980198987 482423851 319429356 87960661 55640693 326768910 939357023 164704855 112855215 349409845 426502730 368418594 7364412 695822502 57896665 996628717 563618719 982389776 412513422 822317261 241879047 209864438 859605454 509482117 591811899 129002360 106458750 156528806 285023742 119870724 588063588 377258846 570049347 109840612 165324878 569488913 204082229 371378267 309728850 440863935 509626476 85430851 672281086 937755556 733015914 971062294 97605367 324429047 475271435 724259421 888038905 794705851 582058418 401349386 538197478 66559549 554696107 663723330 541759175 451499187 642517525 174649393 966198163 835879726 240764792 625607604 748085385 431723854 818138292 354141032 484681816 512156629 182731984 298668700 493326991 243683498 641138898 884647555 138141447 157447175 267883479 133129873 646511697 398068727 664038617 874990415 571530712 176127106 906047853 5370993 619971006 493798325 857655103 552310443 130541483 268324534 206828160 305821816 129318665 141103541 891156016 469197596 636667994 118194832 463036520 379044329 984126930 468468001 221807786 686071900 5178883 126637698 983697076 402216312 478300899 968824875 380072172 74109781 464938797 397471294 856115602 726704847 743096466 480451940 699959047 588111540 386091508 616742407 658896881 427145047 375922775 169294311 15051689 344057271 624936836 426765651 496423758 303415863 764515335 481983606 517378616 602700124 854903937 389648792 980194592 863131370 788761318 172611433 59313897 308397322 568343893 659475339 943548668 875742498 1403821 671354107 667945584 661480968 305934778 37979600 743691897 934070756 964047224 259334583 936859823 312822169 198812761 175463484 978567992 85072027 146331082 741646669 262045930 160843641 93113057 296868362 326003083 998855107 683835274 569255613 596635588 404087455 367424891 982329393 998684571 333456201 334224490 650528242 513447103 456546194 50734937 212203761 917823 922597158 171335403 414434902 884813483 568317326 1753998 98478350 971737116 164631798 913355230 40004478 415930905 510742175 720092026 467626428 903830078 523111229 293935652 150402870 600971969 483042430 825566876 734396987 438867637 362875637 554031423 685044344 410465919 476568682 364002508 311684444 757214364 440306569 957448270 109434243 163955854 693127080 876192666 138540469 303626853 242350320 214530021 599980611 593700744 255451697 601276364 776553771 720430626 26149559 836110212 349801333 63197892 370741829 276591838 924237739 395798852 849596948 733798716 681592475 268559279 312284957 743145921 129729880 977138984 102851001 832869277 224912557 521283065 69537698 969156119 944021091 48226230 51831056 70459122 17776550 887719306 283638613 163692979 750096824 923605584 686934760 914487145 26242474 43536782 133178323 368270639 27786302 174916969 733698023 457642478 240712500 690755624 164153920 286303784 869779992 71180820 26844006 215990555 203959567 780418261 668386254 138669529 151189580 588714309 575144202 993189116 553429540 585728990 106280210 18183065 873188816 26231160 551741300 559001880 919158034 878500333 242659670 556616224 850687581 546810855 133060028 434742955 308680073 76002099 118510411 714958416 94655662 160805847 579158777 778480346 931599825 245816925 716815754 160939727 951626740 762388169 199351340 219272253 269026701 283063874 197271339 7406254 306077165 837319701 879154680 502405141 76873195 407359461 872516970 650958080 925788175 370663103 658095189 976547895 927048871 366143308 677625028 72330612 335964254 300533295 442632489 278931681 836874002 376503451 744936514 238320289 444794397 587622126 314436350 56110437 514575391 889394097 837937356 179626014 511307119 600111736 51478899 195552252 757516008 718146494 820719163 909797956 945784093 49724877 417880828 837257172 579849084 937431333 43670186 597555678 863661373 157043316 498176896 384792315 717576442 229338966 511393789 308057874 275761226 72858219 852642566 841580473 261529815 30001494 965453314 188276305 290861648 837199269 552550178 60973693 302583059 913188625 562393784 187446821 731024700 318822022 217699643 917588647 638442148 136566985 656592433 275640700 115768890 645315898 23295178 982575908 787648959 171820402 307841644 651819815 58084838 607627937 269216184 16940564 783973886 341586481 525169399 617309473 733457589 402680315 511956929 484726911 483161402 394172606 931253963 631443077 232472931 863892413 447986245 331825298 404031733 961272318 485891018 563203072 288249206 21801035 707005035 476354457 447230887 364410818 142323088 306002951 81850103 435605194 464555924 813018049 187460340 162606189 826842624 732325403 571998037 241344696 315665977 46529373 818806727 166740697 929931681 430752025 69821739 273554561 164679938 338143577 247830979 385394387 576302698 789990273 585035771 934620136 981168032 574531975 275365379 512400973 301556446 772823720 806863733 709690561 147768932 49678404 285506093 118143851 404774762 157481923 451180988 354891079 783055028 488172872 369077784 664617861 169217265 114746575 104766801 822707468 860983751 632223041 348885982 828540260 347392812 736180888 628219850 930798697 168225200 64899425 745361952 387302149 792127990 532189496 641005112 629126743 141632943 548575481 323743856 99309434 881856541 978186446 605264231 475175269 410351394 920219087 497727059 593270215 436205148 902969209 549435479 588161725 430529727 504137213 529555530 270243277 147052587 885466888 528393542 920530216 945338873 77970902 162815292 617770219 160590810 854351173 503733377 158645309 128964689 659183004 51729992 137171526 337518080 769568879 445986492 944489747 180476961 766976387 109547699 293094722 891345863 605675197 109972017 396301871 821950451 358525703 688647093 508660556 558902709 853917150 115149046 98471358 624940792 338601064 326280297 250060976 192469948 413337011 674750745 829644670 340394555 398107313 642408632 671220470 679585583 50735768 560644824 302874463 439299407 949757887 859876679 122140146 394404303 575157055 665279002 102779996 884856833 98047580 332209053 63801759 963603130 494622240 827734183 822068370 751686445 905883812 410603380 578016701 990173770 201167713 427822098 123399304 683547486 701681358 959232034 712362748 520044272 664805700 620328253 82458881 338289680 808420759 836754236 358359239 459324214 207850262 980915065 704240589 907222146 870115987 701979195 225289099 854069142 178120430 765864155 946914750 515815665 901332225 572910016 742583983 929811595 242852772 949750808 936300241 813630151 291839945 670937193 400446616 54707582 584725955 698307667 308835260 343585713 261186784 215739535 121392199 337998956 497220221 958148839 782076649 344172304 676914014 1489441 744648597 404593682 748604981 400689574 119140158 482919478 725339737 781248541 600862799 996917571 612168056 44510819 627126786 645424345 655276226 713978707 456318990 446792597 644870404 498581963 209463205 311462394 702744158 387382593 813881359 732948498 137430473 918169165 778217035 238182399 348691814 219826840 672132596 793875903 655912662 445920717 524830589 140113194 261922575 365890200 364686827 1080802 248214644 122534979 146349501 806686651 635879446 602617881 28413579 214401741 698418659 994580435 629105453 630207792 140630556 57352459 582317139 638902675 677792158 421451541 602945066 830679482 380344973 53050798 838073518 781955987 763293529 389108055 596479784 758615754 571743435 793285450 508735026 169481728 72758915 975159617 747464430 532954346 140453940 86668096 433870271 121910718 700516476 978021417 652294915 928405622 69897430 819221632 297415239 813290685 227994730 122280835 74748383 865051597 131274131 423266569 478768877 41056206 330961951 183079013 176471896 72735330 573416414 162676501 448174453 619334746 908353889 834225376 780358581 503757561 457719369 656896416 294185769 75262699 217217405 17927181 932832967 849623971 586055570 699906737 554025093 375636846 214117918 158430235 692200044 81063063 888525848 95354993 506897534 740328240 675428882 597530991 637595408 275261165 213093197 925366122 485834340 209237092 697241808 216834291 66706654 120237688 690592223 398081448 565395471 521168765 860205686 329795073 230318991 393510264 236301910 177765448 190569559 35862593 685424941 575996454 237870883 400676009 293214728 891358476 926467209 884506743 4615389 730780631 460588300 829261671 622330482 326642688 528911410 269423966 521037981 55263118 357399017 724172038 801748559 689727459 962786612 850214594 147300408 54924908 653711166 323292487 109027584 173349664 828015871 451494735 671936969 289391188 714273110 305278156 630226781 2523232 892293245 906469152 928747428 181669333 768714461 596288776 764238666 70361476 75206455 710929909 921195870 612032919 372000936 258404752 772467998 254434731 280142640 303873401 288740899 449902614 111918510 139686658 661607235 512814929 928377834 213779953 92788836 76488820 111835168 904316852 481204049 898997767 914008610 13701756 147031867 381625025 319371359 780988517 67911775 706182217 968892156 13656431 20253422 680134885 920243056 868683955 374758968 53926177 103518860 885425125 399253385 486240124 471424168 121210546 786469567 363986110 872749273 962705553 715366006 108930374 508907834 195339352 240810470 337187614 704605161 788672008 810113762 586880179 452728954 192117889 551138645 239462894 425812155 593345886 943860668 568412423 605543124 946905165 56765199 532730200 419549311 774781875 635898886 360171516 920939957 930903643 615449156 145079318 558868727 130926470 665222780 517583719 3801572 15439355 996279002 964766322 173506156 543107091 58314884 30846079 497399865 319967939 931395357 463809790 828311378 47461601 43588549 372099483 610558973 115760955 441453467 709519803 618284906 747219613 761702366 412605410 43092154 289453386 562419507 406080083 18215401 816598517 986781765 493160029 978855139 184109782 270239988 23342693 64170008 926178733 235653494 736643339 133140789 730193108 225118912 516283788 789597607 779974251 420519012 28515135 64772748 654796858 938582588 616107955 390562814 96016097 635063138 959233605 93138541 214727625 104207354 182777777 552636361 285117889 754814583 421986481 196535437 337501817 126830776 648784264 736225301 286594267 279645365 489788671 210585163 274046835 335262171 155262917 987634301 505054488 249616347 657914405 494106383 867873525 969953660 584099198 19907095 558995066 124946507 530795978 984716688 327713344 799788226 323456289 890504978 599766912 236703835 556935219 227568617 954090182 141086590 269197047 592137043 288593953 786886063 471037899 528007080 615023394 127130030 260961157 268564671 129671816 404879770 689495351 852568334 892035134 307941562 879197510 568960586 748976688 951856679 23501621 482623504 724861635 47763247 288240948 862410631 881266050 605486314 723508548 711102432 71744674 731612649 600561514 648404183 281854535 254414468 49385232 65116458 571905998 492496854 58603480 519666999 515099720 885277266 272562395 635931552 447784049 27307694 183170416 460448036 588134240 954590904 259606237 102626020 916838914 82117193 921101696 96379651 696232154 703677469 561080401 946899840 196207951 356537532 740024834 751288366 925299059 996857552 235218777 173885455 778221136 902005161 564257155 811841214 617327040 541460675 472845902 577442715 30761727 570293972 423469350 952670488 246257054 282774880 458145781 218303436 333684396 706257803 694512516 232627518 74542961 357877115 799294033 319563860 900979559 72747804 856849357 937073942 564812939 239356401 293632311 226406132 158099176 945845548 753319293 311626712 506375601 603262029 753978011 425562708 44835875 424998073 450506265 9530917 82919702 15179402 115826353 874920406 896373812 265336333 926767099 157842311 655607853 744156400 69615985 54793671 618606221 958403877 981017355 436859231 864866267 886273496 17893294 219779375 718541206 362717879 951660650 462751426 764524090 507971143 244124712 303738347 376593863 917029929 62586496 65091113 93557439 703818265 798070342 810331586 154789382 356849360 471950773 758999402 463544851 304226012 752046284 807671971 123378365 898737139 389492004 825879028 194042383 465681232 163067139 838035054 158092134 57073712 949425670 937212153 763438179 529394448 287774183 152205359 911242377 614449470 878497870 182659815 359447891 343827412 340218814 182917417 492096035 779521843 382568677 696707404 811263874 712385648 356984898 582983578 205432912 235128312 90134622 817358363 264472683 749631698 539797729 471083446 791920029 604639982 337488788 855886124 320206907 707695083 782681361 751822615 489913330 845985620 557756066 108412099 1598993 269125333 958890161 506551174 895523881 220471427 44830179 698085371 833456237 393254725 942254445 487565280 36262306 777467081 903278155 200897515 525177690 550207701 268244185 690697893 293301719 746223934 566566980 778673825 232285302 580014232 801968781 829937600 808376017 832536540 868506232 719540009 138543183 473854719 773494989 292597252 793556929 180654002 286589559 869171240 148490404 90284340 65279144 814686946 725629799 679792957 640956914 425388266 809314364 191355041 692173885 683528727 751514638 369799304 228988556 964173073 191343264 211873710 1383649 748283152 757155530 931951122 103080840 366934444 348037834 859605361 237907262 898940707 459528059 638590508 957942923 526861536 149213988 985050486 770420022 960463872 569890983 679217399 883792561 326461414 735329667 156496036 453211728 141148430 546134919 480873748 63118216 398884332 576020686 29359804 311711176 272905429 703057407 497091732 341213799 612398293 132671952 908418299 982291694 86048049 481620245 952374988 484481387 50382310 422662007 867328514 111466368 672300391 491721574 198127181 855536344 498465535 362020380 411924298 225245653 107128050 537741742 661137528 180438342 95947293 623588833 952088357 416344156 926123148 212098550 847178209 60910819 860390819 889379108 281571224 565087394 780059285 799274022 499963904 893200490 252291344 798671382 855948847 709283440 129364720 171251444 809669013 895267585 810976987 597499165 905980760 608988410 281144871 75027929 515393440 15286553 163408691 480517971 326951111 514008799 420518056 713844374 852413103 596976019 384303290 882856633 844145127 635147753 542911203 806001209 557746684 811065877 769011594 527401692 170433939 844616418 355095070 368604906 566515411 27248418 569841174 862066879 744010948 686695572 280121325 318316787 606767998 497249499 142021377 631951243 162643289 866646808 674956664 607152221 631888171 947194790 247265874 722891054 615372203 4036595 249491921 18604878 917397534 936235217 970895890 85762174 453416494 586050611 461736994 937847247 692911812 128434769 822745056 504991142 539103510 737039806 356395161 379485209 380203864 946212913 112574644 210084793 164972437 632453710 912643220 307321018 864772126 426172908 617485761 845589785 144764994 128480561 471826672 812805577 741008494 481936382 891822879 112744976 143838923 453127910 226911995 32337507 140004949 193643601 309320904 475191147 438609987 610141391 72920858 778293016 574233532 190067909 72755796 681454146 72948512 484073435 341203943 734647181 214779622 666831890 978116559 498519065 814026799 502977756 70294848 725273799 154503743 93001863 678324228 973664657 400934060 114619494 502217376 1487521 504452463 198376392 555781316 745828728 326445843 262754982 435502294 715118553 621034256 405073529 83542973 413126836 795655217 511949152 914802497 744386778 367921508 469560611 731658920 729748150 564743316 462562643 491878291 822068703 79335157 735059454 58243066 453303942 78987126 621954785 953857345 478927192 810313779 59298877 614085474 992805672 701172737 953612633 982056659 660100535 534764235 178875544 685129219 617801278 849902591 912830339 678286723 998123936 183536314 999023163 698892432 880799751 551855547 895727182 275440834 633483085 802459115 56379166 328923685 77965721 252878938 677806656 635305370 162076033 654222222 192377032 945636652 27167285 729862053 598923060 328909626 758686145 788180043 296181501 82377808 177811902 598660846 963436122 193366616 776545496 458603001 828622965 12338747 83506722 222913948 367498224 264039090 155294599 784594557 722376407 364932486 566431305 794410375 439832879 891997780 783120942 213838385 168669312 949510979 481412206 977739667 788027159 674121759 553585374 677535311 747092026 599808818 848040522 790275457 779274850 546823552 233621925 805334950 332623128 904255970 260775002 323113826 152671154 24264494 416423226 206762287 222771406 145310175 909824921 499408091 359573837 98058619 771400244 619584750 967775134 635217447 249708470 313611982 959209777 757846189 523131625 675760657 458088367 906116947 337733970 898463496 358619929 440750770 592194474 142055212 925923061 889164296 131252804 326111994 679199784 972616597 112994997 755105535 651404881 300355212 580384474 265611474 556506477 725055751 107193967 189661558 328939617 939989169 182015825 491073197 235667727 779717520 936048550 273924873 245676196 508220589 771227970 763091223 411641896 864825097 780968582 297352995 651491339 840902887 717906051 790624671 881742494 708907603 808811962 143991759 958709971 177938507 369138537 821340865 227254514 242788212 866920379 28343925 699814567 190605894 532114296 905493834 421634054 773272002 522623153 810977350 492685659 14842158 27577262 31732924 474696756 850609928 12913541 227521417 615454807 464218015 860500070 142806626 965364626 56698160 202228413 877395705 176840401 929349370 352489614 504947016 589954884 352104814 959738769 487560213 282875711 209747761 659538998 26790515 658658556 937398945 462285129 791771762 47227670 669619658 459091984 902010996 809770557 807889457 805068397 347276491 769843947 660882440 231987532 384411588 79397124 310764405 959433351 748563709 117454915 114672703 487703634 595041806 863780456 49753999 555558482 991751651 679496189 566880313 485421200 7976984 242044550 424823385 187592465 193371000 844306467 653749503 488780298 664717288 589080225 943034149 939754114 473757375 542994489 290346052 358802635 226733889 401451432 191596252 614139210 577959262 42157943 327697452 337305708 691510200 783618980 25264942 704454201 726013200 631676282 473670753 202235642 969496386 97441889 87619997 504623286 259633351 750088405 658160594 586697264 547715687 864830637 259397477 867191978 883807865 817605266 824917747 145061550 150331368 131590631 6926933 33676825 689489805 805596526 340356304 422382128 647303466 149908296 889859904 647487483 687515676 361429408 823935458 737454098 459334792 417596231 679758269 529773945 284079931 128827006 225219640 125199969 360625958 824127957 639743893 49528260 984539139 756452335 399478570 400669107 890529518 896656834 520293790 951496657 625014798 971213493 266696631 704788621 551013636 913627788 737397838 318934537 600209116 7824350 878118736 471105190 588915971 959254556 16678907 942963374 881043366 632444260 359967727 613108903 440288828 829049216 510708060 746265119 97173749 975759330 755726095 873331737 848706893 64754829 26630314 66076259 597135016 399656881 246382689 698264849 260229220 296446088 537349238 539920261 192807400 661683748 92302836 707240453 344777419 500226932 591901511 57243678 245097722 712768171 910888144 808775590 397012328 741868138 589285333 741097761 854170868 566224078 580950061 284476659 929361749 469891970 134889440 206233997 180263113 809845613 147729069 708455161 985672166 446025033 859802248 403458525 340054117 497938831 591749207 399306649 576027633 956604535 150663485 204816980 898769690 356426559 220205453 212056456 161599379 35437223 211353481 510157853 709632783 461701460 741339257 869077319 302959954 46774321 757698084 62849026 739975426 812691417 790265386 701835598 426116076 126479869 432500010 350898703 567269688 505640407 788971011 629424335 157584635 660133916 720590206 939458518 428531017 542397105 543715814 435192968 833156629 188726077 742225671 331663173 62992640 655542518 909819656 919385084 594564131 875759048 808042937 986987505 100645029 917477002 186832233 303547142 954085669 943995706 29909271 439778457 418179733 315626096 646336880 341572669 829195751 295747516 599396438 555345991 709072184 922213654 740148552 952597998 827684545 867515991 569234694 836973524 495983436 764589824 88423800 832567176 998244063 137963062 102987503 354435069 951356045 10890485 305208379 424135218 352337491 607600225 194320238 303082770 186024687 625843821 83205926 828680484 210238632 999250437 799618998 422295151 115857343 222828760 730058987 729548463 827448744 390250771 176348446 503052890 622888265 440829083 525191437 162250863 817268340 480527910 974420393 996635551 490099199 808716058 849269208 15195448 601121879 725092629 288977676 299909229 507950676 724331539 27594001 473623598 490303535 115163460 450380676 637401655 225960493 872132488 224252498 229784189 31132588 979043821 800816653 586337845 54071813 130697000 525601401 173973903 930077263 292040921 86834864 198035953 806248625 780180919 559676427 453925649 216226177 634128851 383243266 357539557 322681631 609853230 612371207 244128375 295556840 114722308 656185394 493089155 507182918 347127460 221739852 302013050 204771015 295841469 171848851 998012208 972793098 682045392 658534752 404541225 682036991 388112594 962139611 759837664 501319923 44958441 534099006 56584091 637799194 768463010 469789208 4917401 691472659 210191133 15990657 441581547 230885835 174033168 312744630 261563645 495451862 744760155 777223772 445322335 33465635 763742548 831323615 620687958 825299471 298761542 856769158 725287876 702974944 607110244 711500808 630153935 48009467 742827597 66965376 220853994 169956920 59345114 513823073 97532357 982344661 198094234 447748482 203746275 597824735 912384456 379835077 795674061 960500466 75408460 538116761 953496383 273881061 173474230 536529040 566492385 624201851 343044819 912004528 409248208 150496450 816047895 474215397 600573596 387514959 375988635 508746880 697114281 971169490 872075015 834343907 733710263 917600202 904882998 777575093 261384458 788261958 790714837 111187563 446179120 559828946 779025465 551090174 438240453 207522499 75024100 244934462 876561502 365131228 485339535 864419901 702231315 879082650 826632418 63615633 569131026 265137238 624035001 644772467 488616580 595429391 977712616 317429586 862309723 984620631 831710361 310357689 448785309 853928654 670237490 741407215 795420421 480947027 963939515 838154541 231310855 894794586 454428491 180993445 161939704 56676402 701924056 786761579 397802726 34969645 721465928 320004871 869682379 804163336 131581513 93574639 880568479 584200933 59944323 961555417 81824898 709944448 258478961 204794019 468200158 751668477 31220626 129924879 707401788 571897624 868310506 242271138 165551328 729841481 195717061 484978005 685885673 863602979 620156166 462962509 916172342 576808898 90404428 670624611 167688049 818030783 768548783 224766651 98123023 609150956 257105755 254943994 130894531 296626925 450414628 36777390 408183525 764488609 351924259 861979779 194274866 460061774 44242436 42494809 234835664 796168196 828013625 943844089 387584538 863353614 711374673 461292923 386988626 222108884 677072694 396652785 422401393 360773166 863103894 96450957 93274469 665660794 239360693 884946300 570217239 124880975 962296118 7312928 515840427 598392041 147693218 306633440 599230968 159244814 764552204 838648040 632916584 523043192 57793234 304128304 347266285 915829507 831457278 102042218 236039045 319457988 935535426 107233299 415463704 15746934 907257323 912158905 960660288 817119490 321036290 279454059 155873040 615999270 540341101 294965086 722979950 654991094 170206419 131814851 595799170 665043820 152194657 205526281 671180871 142682208 586295505 666875894 192730410 146453144 609034681 819732093 775856756 146528659 997124636 920536828 345905427 422639457 235116112 497321687 482269414 989998256 108114524 480343345 404051139 959557610 121748397 52836405 426175058 979902196 266882381 776396878 503550655 38496280 532343890 616634516 75310739 448213358 712094204 464599973 947276834 542512294 181360941 419860934 300233546 133862811 547423291 851852850 991553633 542758328 173793296 295272537 301056752 319706189 180879902 848949429 847183959 203899543 431896462 550077525 20728659 386921905 400440994 379303937 420209312 478010034 507130795 137455087 160851466 352423463 218823069 520271998 819043055 162785254 777840095 730179449 182639023 514438468 113405207 908712943 936845739 162601924 166973574 382780175 223463922 547227232 311723418 103572887 481487428 209902236 679198123 957928442 688545921 257984189 328621534 665650904 670168578 879574449 253036859 388246769 387685269 747285640 48057900 688343500 431747561 460447337 651209009 146497549 478546054 899017669 260731191 393045325 367049479 135711213 371135233 5113506 150846267 966538386 718102755 189016950 905907506 968023589 847611566 280291018 939912834 518898947 444056935 289913284 69414539 385252853 540944213 276375084 793411431 164268140 257354878 577799063 996839485 219258625 856376498 573022490 531662457 277275618 201201431 910360642 928889122 862802806 224428324 130637569 139806104 422809174 850658744 478156113 652472976 778630611 86807574 928832746 409181025 290871785 274304304 136128624 506855268 419956220 978841933 998173884 805632676 735424438 763445156 857240552 927054515 603032956 376918683 257228250 84068937 944711083 310364144 585969010 157577949 510183267 488209083 524940730 91432223 861382356 216488063 805535980 208054471 795609033 699993010 442621751 404358825 717805046 142031689 75129185 342056428 716498094 977188585 810338166 933147799 955264568 370585682 642002593 391377050 818388172 99230602 19256170 390263276 855338047 55280463 988228309 970256965 466444671 261230607 844493133 569445642 927535888 737572198 833004378 227529760 433254179 229390553 852293057 710608581 469380078 485361095 678805850 119383114 828930780 936931026 70848144 836050542 743407712 584066279 463299296 311408611 890777611 134334075 375846833 835110776 900158607 832445584 258823722 725839878 537441406 466489776 249836398 247251609 117026137 144362646 247373700 438355280 136443087 139374689 188746093 147650218 419920766 338367755 391403298 98547950 634162767 160179453 49424577 274734719 308016038 708872979 319402241 299142499 53802853 987341810 58803205 555700944 611417127 215866155 950078525 351264314 379548235 310730428 38304564 483897851 977412345 904522369 290114517 736543920 14087877 597263942 636373457 381071062 3038304 471735644 657846413 101565433 321857415 983538702 7515336 437805597 310009787 733507602 308849703 36144700 251807711 74577769 427985014 567110434 792635638 115293922 69296129 34149291 671199599 216602783 796276288 528939078 860162337 186823500 119080427 974049055 835870370 851769364 830820918 487541893 742057220 693569251 509097956 176112530 372612885 634095796 47813227 148897518 828063614 498963583 345687128 594141046 255753481 88353779 278834389 892072237 574430486 344615618 830133370 981858937 522710174 727479116 570958295 856207735 723539492 360201298 502264158 937554827 892257956 709099268 801278684 773939269 456222653 810361590 104547475 575295525 24423321 308063743 233305066 452397781 624384171 652858056 456738866 197010624 892375430 709402388 544432744 194551116 396110233 100399108 611005053 746972464 624376678 884925683 561700072 126491005 486270948 527964352 343584925 18672680 217800716 606720219 57303906 350374085 642688879 748118474 731431478 553823112 727421281 972081587 475851999 78076765 211268949 888720182 160911147 924185431 886620542 166965982 392088909 417225303 413054811 850595781 620519741 619160386 632860931 578830890 830839816 279114058 431997069 597161040 540707032 75544143 677709788 784774266 320174443 957126392 534289083 333639030 761284842 480585742 86901420 387170706 694301075 284624306 218446364 970435728 430526310 855456284 817366514 146542147 214458519 922874431 829875918 133399193 769946794 583466990 295854154 370189723 534081634 252429555 164502158 383102229 674889722 985849860 417716988 55152431 398773866 545486454 333086388 235952466 63423485 767641218 794625418 855347359 742128067 582092329 561197096 41847900 734688283 157184979 686421999 545285275 15194649 639673728 659358669 766259959 252714663 344999058 815022534 286544416 170403985 833213400 613726417 249040232 32868288 391224881 177215679 668224441 710007722 112502071 119706129 567911087 375458277 115606545 48408168 188891489 604611546 833243717 909256674 721514422 664679307 609922699 600808100 575064427 689129695 710394454 407184500 965056894 330940431 920020836 947234026 90081380 351499381 134966741 592559165 781004015 460766418 133080186 965682890 777224723 943751042 289632138 938449378 647939569 130840209 575456017 959985201 402271767 365538203 233807446 956499318 482620864 641387921 77434670 68321114 713177450 696988512 145510594 182435313 873424409 828990603 293455258 344066409 518384373 590745335 205124224 404413293 997790650 550039805 879830475 602382683 294630 372327099 185306462 558187721 421940469 243436810 926725571 451161371 626726894 443439420 671639956 991403025 818050225 204768186 417131071 406376525 721329 634632798 980211792 733878883 2236152 834073144 642791411 629596595 997843925 611706554 261168491 1580987 596113019 655450997 445528196 619350777 580180935 304517425 981391824 409039279 45355997 349139808 872123378 138240789 747503148 597359094 964792781 268295906 690608762 385330162 331904194 764134251 188618807 196836728 435322546 912035500 79244900 103860778 628398263 716471185 329723013 676168393 55650935 194370682 730903773 245075504 299903833 27660413 641590563 184103060 783564296 194825990 125386033 4504053 548546692 704737998 263748185 202152708 478486425 679383774 768408068 657661644 663371846 257905137 231301240 35593839 582127642 57025878 808878701 681145520 250244626 860258277 848878984 431701543 870118704 411025279 830775532 82339146 769812437 446969475 46201581 832937071 225587804 681312130 123362392 342417678 854504943 262370410 871061086 293317654 620990488 227558984 945403407 975981133 626527017 719838698 628047711 12955165 11103850 812200298 42193269 215524474 771025383 952080517 555141727 778757989 637947946 508421608 948637346 740086661 432086408 98348857 345330431 338548307 327498942 160224088 417279347 684803514 93949082 200331988 266698657 881354804 718410046 799990519 647088289 391722066 485793777 559892112 111980394 348398623 4557856 863549015 856980623 492116870 205693955 549529415 717348101 257298198 696083319 133551140 147467395 946681558 197794531 160392084 330255416 86276409 107698040 89051393 524480389 612351762 436507180 22848173 677437975 35661333 768378275 742495328 421345302 753148298 172489444 241080470 186716158 160729645 713170459 104893903 48033986 667312354 877401025 145860891 450032604 452949571 665683737 135781949 421241944 264137219 587907255 988606183 680196441 435938073 448946474 406628991 984501253 991283904 694126273 675012069 610095192 237954793 572655328 734690916 314453193 987000828 343692986 868008262 10674436 904513065 836447004 728861357 527568918 711550536 539839502 177472091 762774301 922696140 961674375 529901928 651020554 598279253 700368232 698083798 207950993 543024555 718270230 24500767 402069178 457147870 914120454 856901877 324700580 505228432 748633464 465929177 532250197 462175776 382519681 388682129 129041333 201036254 307074075 743636448 135800718 559131771 565995752 269659438 582199996 140099514 431204919 509943249 96187531 40939101 368572096 609456561 203186384 824430435 640769725 994064322 150258429 855644455 288625223 825979569 530329828 782237770 119748424 612011489 886453618 935433615 839802027 909604851 553389986 563803502 479182434 415498314 361678060 465059210 703307058 220657940 246643654 960051077 621014071 13788075 920849633 544178886 11248495 58129713 373388231 568713624 927335864 849496998 233802064 140484984 880458081 187770828 803591597 103518418 984797058 612685043 526135657 579139647 817176896 624150594 688957178 518561656 320516209 137136819 473772889 68912082 895225350 223961748 973462078 103055435 173700298 338555527 255390025 926547521 673752379 66797969 882465197 190886625 156272358 626463154 812559951 228280229 665385375 174826225 229771315 24935150 766161199 749920442 454355495 591035733 791578948 854221404 609576197 617857003 108508337 221750450 561326563 665750242 669187168 828925961 799006832 159045114 852898835 306769893 293178485 711368059 760760531 381242641 987009974 631739042 408824290 56602693 885143036 310460574 390795397 913963650 766631223 824762230 536937796 26970527 329947622 886043270 381140283 705184951 180265949 850123404 130262247 122925466 985452244 184049959 590989889 139649683 491252413 610726506 697364936 483310094 922437860 297056300 960374348 369410006 770216522 401691342 158612925 437800831 632693859 122227432 750777725 181791998 830866681 974294978 926975286 348210473 54466414 370097420 552496354 834093523 527476319 943301683 886439808 580296300 740493543 370670956 285574191 752140330 935080678 376457067 803963377 943140394 393266765 959470638 859628877 283770924 473453554 769179862 914976777 680239131 922823323 668535911 377608820 148516096 607218710 377992598 907816223 499759126 644286969 296012591 769498124 831184270 356989782 62990255 299055510 190987212 225539411 682854703 524212782 929759186 490221515 372653764 239564211 89822365 519818547 186293174 751408097 386961709 925494272 593573068 120218926 28227773 473703712 907108728 149643875 610022887 580242796 883152246 956546155 430881587 887862182 201379161 583330472 714660698 619479265 405127017 423176910 906835184 926095281 387253957 878105363 516948211 821849766 595732773 581844762 24808099 917636484 843442060 132766453 440706244 569402355 302619070 800760577 957819080 178317959 888481378 315614908 208248862 788733934 559114353 98548750 336173053 288136076 928491460 164036853 38755414 23722256 183202480 162531317 957394073 505910463 365993555 438379853 91238097 703838406 223580426 588997885 967514669 776145241 673515110 394656638 58019358 587074192 514424376 472200879 750202294 88865160 853078548 935335106 139828739 302807931 245999200 329167173 38523905 790113386 226306997 273450206 115074118 897471169 510004151 489018735 698720014 808961784 129762450 102499860 853537574 294667961 236555407 498346464 226179847 666298577 626264649 203063627 418691437 621437374 803963904 798282986 240879602 561322346 785321783 136809424 853025399 423638953 872974737 914271714 172866045 793585384 434436939 179530114 847220852 895979953 673892176 666131049 887938064 271593482 537937009 927078397 756703965 385992186 58022200 453864163 219499062 883383298 521103617 71544961 848054297 596305422 114122244 503766376 244623410 60162498 924768404 689751432 232941062 105853323 46055658 69733665 670700482 951011960 749167840 12106209 678704487 58186953 309606214 976277466 883590110 244813349 725735548 47097859 372394998 123859986 714415788 562602433 49043615 824979463 541642926 625177278 759028304 133888784 311266163 41205409 156214871 123228815 734281672 395506403 775009725 102579572 405433720 519805444 45406174 250559957 571514618 60027831 154126473 710554021 963603582 452016208 271764013 726745120 738404125 661536241 996201858 702593590 14837598 80023756 122460142 904076839 62260060 55909098 457450740 69962059 385348370 511634148 226963657 986765234 825232203 793380668 246770839 333154736 252339320 434406977 978330113 884297743 437304785 509719937 593649832 718561882 553928632 111192443 418004013 5237123 372433585 585399605 491063494 531322979 250182699 224241155 327451325 497347607 306698926 269319856 310685426 566687496 794542521 339157419 17008986 370603192 339730639 683377205 337924241 973486905 945434310 245318321 705658663 401546049 29293925 125145262 380749399 585861739 224613389 195982484 445002375 710627163 723807843 868160808 368962179 373176555 911798249 119163942 256537858 428575316 338700967 222785184 779513587 323094720 454409481 199448129 523401897 923504649 289891558 965337490 798666337 769074024 566736078 841278541 706070151 647385044 771312422 369172719 363243320 901083137 94609437 915844221 136072295 778663670 943283431 978604467 610900310 957128064 929673193 366549719 982601658 487240087 884667505 955048446 813305974 383216724 871594836 702150825 483968778 828661354 354128644 294489587 566307536 70678937 357072865 641990841 189168698 986317665 504443440 466352068 867605794 632298076 401251052 194373814 264402045 823583090 698700289 56078181 725158474 562499776 930159210 746962633 885210326 482260070 488353351 807198521 108476233 41882104 922057648 327191515 356956137 69350361 630481101 53402499 380170925 92660693 421070336 51033936 884699317 311089201 745232150 907094814 826561067 769141369 538249586 920068634 848090376 421343528 844323803 728150004 543834746 76121902 13222909 549637874 27722865 330889150 497591656 335053832 730215523 348163544 773830469 114993727 476456630 854745799 846971320 140346759 384772208 893962087 201669406 787679680 632544239 336663119 25926208 893261372 519958679 812587256 488219104 200996447 830963168 803014641 797218098 994672163 257665251 22148275 549229280 31252432 585176639 682770897 383050015 412952638 597508386 706482555 454310597 610600829 883616336 705886886 528993794 74061281 221280882 581753466 224175312 597616947 273500513 679353148 816747487 225154474 428929954 612382264 149733267 123370860 689171330 458323777 120650577 678251029 189125967 64528265 495256385 503602094 822955585 579148778 889017820 28949558 331429865 75370458 562082590 561704587 333623283 701802202 623735287 914926450 107262671 237732771 609837931 842581753 340838833 221111605 530195050 129918824 703325747 52134319 58913467 514033005 463569951 149358375 814527716 941123340 803815786 482134961 730941311 550184699 126239679 647232606 516224865 271418358 966723874 263885623 623272022 870579984 978477221 385790202 81626245 502543472 404703210 67081842 858963359 468893635 52643634 258973976 107379385 531347010 742435435 82058106 5548214 206839481 717878702 834424598 812862100 368438668 460120816 116549591 913857366 871689640 580235649 329721251 836691198 7060987 26662818 825686956 592430495 299926284 225540651 831855984 894823466 509719968 176312970 270078962 403556727 854898278 104934426 939659750 686387876 261091661 388987168 599376684 43743768 312956545 922623481 2062234 188270719 117948144 397159939 292502193 354422524 260393614 601188934 649481588 140608226 750322856 461188461 50763631 997951898 432614344 271871098 371304309 92724016 812861819 230113448 136367660 429496276 37316392 765568382 479329494 852681539 711283853 236429354 676379342 397106023 995060546 764859320 915215834 563504505 636099426 461011622 210968547 410339123 203462624 118176900 9383709 915251067 224214372 948334044 554821080 232019916 385340181 814334635 479488867 194510391 678771265 152304591 861881757 468238680 816498838 768924177 668498186 971522997 428557771 549493409 636135714 758453645 245444621 883674531 265562106 230009124 440537917 69221967 314923340 900564816 615160235 805683303 527292372 655922154 112538723 58927658 966323231 485086791 776184786 435500664 322717794 618726939 267851245 828413484 588426664 258055616 240588008 511367075 162104793 102435706 149481614 298037752 475866138 484062457 168031632 531476108 737993558 473517020 469014244 913594021 127749596 38814761 197962071 866954002 406214712 508926089 503525911 784576857 211190987 824883333 446080186 165317934 465315442 549887520 953715998 952724277 165916934 374801589 968585446 47495269 54738104 995694439 777394755 804173045 137968272 182441067 264293352 661056376 985258388 606670701 494697970 901258333 64304346 386595077 932576567 868133918 839604192 246575746 524873031 928934535 895156971 919960176 434181763 718571822 236840394 762114428 959207906 25989368 137270059 132213003 12325733 387167466 241018807 670847009 800651149 502668688 128699949 197637764 223075910 938440895 512756630 208677284 107897570 834024760 714640555 325767533 196871978 123185252 951820808 74229623 670190811 862246037 283776506 907760291 707146814 908122857 259459732 899808550 808820591 341421837 445956519 251738481 357356604 593311725 61137821 77267254 652268990 314640567 984518292 487078641 714331477 181517605 973492545 71994285 764186649 326015522 100385293 550645501 13709620 129586946 273747546 769360452 316856390 139177535 380094856 907222743 142319369 733926492 635479556 715350788 97528260 458969123 366206081 801900443 962725336 180515547 731550877 336739257 510986621 134520043 86075075 393936989 686756205 724447231 373183264 356046658 398936414 459579513 403774161 79621150 927683381 554815394 253563088 652655041 935272353 479925643 599970709 675917706 264821252 647834135 295031749 763834725 76021301 667867961 155870347 907187921 639671367 314397212 60829344 68072834 43724690 930304200 319868334 814033927 669334420 207854932 685523678 447975090 108254394 679487852 669341962 286323897 10765470 273606410 302670763 891145391 489532015 614608287 545055913 911712715 238549398 494175421 3916999 54830535 552348126 937480559 931941555 726480637 309225174 311758368 950667313 293750253 589454562 957087337 87550229 257270286 576789059 294803200 377607586 30415537 396329413 425410696 978269629 450310100 496858417 955998433 876783757 633371038 529490953 490936825 373431465 698970182 611079417 626121737 531604062 161180155 609963274 856412032 268727624 201004322 138713405 941517865 182044927 428604222 284472971 583873712 162891152 303589748 518938357 812546012 345505081 856310020 489182806 2675288 595387396 327284006 545253328 706156997 92166562 476572662 474244790 345169415 267899747 599276155 312475408 697830999 479385282 284823699 642181747 59909083 18683458 71817292 57170248 26426848 986547958 850527108 629082936 233671539 896400094 953473228 113958793 820064229 759996200 730748662 214825894 191305274 588834221 238849952 632994385 251980442 377032688 765916943 587013225 136345636 501933009 886700324 408006023 632373678 268688358 779657123 203039614 645539937 855898489 666828264 149655067 845565090 902843639 553211424 995680912 936868229 267601251 372964508 805554272 101382248 322460808 199842982 949823704 93341251 422373462 181795808 76149597 185486874 658098613 225752657 141430323 843802355 603278111 427587284 104766783 265440072 789544360 631421143 174560852 77155517 42240482 957345436 430476270 837618585 418312746 380921553 578250203 997886884 284966890 533227124 684031570 584665903 430924749 446630435 132264938 718442579 20364800 456907675 179987806 753982380 582293991 422898036 279241041 127970847 115217503 704879046 512208642 164828835 209212001 394621401 750430442 77131882 916155579 384156801 495321442 104938382 895837924 345296726 283260617 275124043 233506456 244632498 311282022 187101610 756262233 894010201 841138194 807770434 805392414 317315836 518061935 702010494 273628105 561959370 59404017 854455163 455486465 486968791 656572798 125716751 440958150 86479876 736073718 6893904 604124599 953141728 552293721 218380673 285748270 524185253 61974377 574168678 270011936 85379327 49669459 585556777 728554480 14710229 942114438 396152118 208549401 136371948 840198491 664082904 125212574 112680857 198600598 981391754 372846593 641085887 249231764 841709758 772994601 537917559 665141960 235720202 454775588 100413775 331854423 822928134 122920162 42510000 184158278 654302433 865959470 724644213 394824401 413021443 433604612 848285526 299735724 612526614 152378456 595057493 109393320 608191417 126440304 769325713 3150127 310090333 501315537 591212143 708936677 251675226 157571092 701568361 232404238 997829324 695652618 826994771 375671919 544092510 309034341 635165117 953202094 348281120 598067210 140263550 812344495 380831188 419608799 725147701 556010165 218671390 6468789 388923472 167613602 830101176 225320701 242088520 992331475 598955998 512052982 920529323 937970865 62355481 660224570 416824282 543045511 237747175 812640833 603020130 204376766 695098453 179989236 291944019 362643239 295397467 786509436 230946661 578401202 826671279 913983648 697625751 975413153 386210461 515709304 954561357 530506110 998425117 225971117 380538831 713110825 540692603 362902889 618397903 352209659 946762580 569184712 131911829 678370973 943955705 152047751 541475428 864223078 284848612 358470551 484498613 194097671 787825106 480786913 323020177 124252742 188362070 950349845 178058106 856294831 211903693 201198020 715605284 811011710 750479684 721264562 129096024 246275702 102787371 145591981 471867081 665086462 918354338 664935690 82999679 77916645 470822835 245340813 341464222 352656158 826669969 891677090 475329774 56597054 230243823 293253504 71703679 384663277 903425654 905672051 283915919 8693812 471217357 733807748 348265501 271886109 338921794 560633655 814535407 903975261 731276772 30584478 101716038 925465059 380991600 149934187 430337595 237966225 348813639 356541178 501007128 422786370 447841428 174202838 208809078 867332167 712746046 580299031 256916576 650228357 234433763 947555042 389957608 798557149 110175942 780408009 566393068 7126863 829167046 353030830 265525567 618666816 917793633 809593082 143026448 309418184 354676772 738483670 851426595 226474180 82982781 752273775 299372135 266769273 799902650 156075293 284231778 273802557 197024596 471188388 973616244 423606603 520136917 891696102 387414643 258366562 975495203 822743215 926075800 252306624 347589190 505044793 264196980 523468627 629895512 535746216 70286234 165912332 377073591 406764902 91220365 514395094 439748190 194473603 48936184 578091991 269744148 335950044 510901034 517372453 815841675 244556899 716667410 779657651 352374826 969493667 150208592 764170898 282996476 448967087 149765468 323812645 880500831 294173224 829741859 223918929 104674319 761411511 167024584 816398827 580808151 303022714 969357927 623419264 721945996 155748275 116577988 492765843 991478615 39461603 545243387 238232918 785779114 552561933 860242785 729486340 178768040 5812215 708199411 779024862 324302232 617833331 469936245 686992532 123915400 477251736 834045258 261141219 505647180 873675538 139978205 608311133 446551184 317909019 344427554 90114541 532166708 257396822 214602103 909425219 159093520 482730482 109955496 721770264 433269867 992690761 31754951 88393152 831190851 506903412 627464980 162833981 911812878 395542565 492274402 653206243 884090362 934039075 449347431 266415786 942928559 27479798 877788838 722468421 731881578 814982080 535261935 246474435 524372652 430084739 461194253 688332710 139884942 121026526 295182107 86340706 833910750 527224674 880319495 347730900 480025440 158483501 97611902 548605829 61964824 665245486 78399257 205784342 528851683 845958580 927937427 307157497 356683629 176412958 854232012 234385381 75931156 21362032 699264593 316872452 643796643 297175283 710407900 229290480 888672659 782588494 441725288 912451270 565056444 250359337 739749393 50667668 514197277 233966946 226117538 285107495 416769779 309202300 748115372 454892502 989699538 909995884 213877952 924299830 763862886 701159335 675977058 929488290 779810702 578542644 667767551 331422692 355121928 280717026 651682066 928457897 162796486 87599884 106284907 813346955 71694732 2981403 686080646 171856003 846991778 412856326 39703301 445929303 903635317 363598392 101195999 221302255 814695277 87752873 886761466 361085153 368218022 135603636 274878368 372237323 262817235 753359338 738420247 355746697 358943356 930087650 178890408 14075409 37893861 652321019 608730355 447004136 145602995 335101377 489629163 1008349 147652198 509288475 692739193 404954785 133466677 646016253 758697778 249067995 772129638 389657888 937497539 483261265 33599046 490591942 244797903 729155118 694422535 809113460 924609699 537146546 296509820 973293995 528921537 261094668 224458688 578377372 661403534 469530225 17785958 315942725 961578898 30378743 498758785 610736878 382679604 478236903 37049821 355563650 323806686 547110229 504972210 194332181 876131457 890684169 620532646 675348942 822958955 845761593 302042918 36852793 161911923 467184199 942747932 590928363 689790594 84714912 685181418 727204151 580453074 929969581 564194681 691687235 195101234 346150750 979389179 126870310 472530344 132280515 239715744 145658053 862215230 359705081 736102142 603112620 671694071 720327116 686081817 516551424 15831156 77415007 854590262 946808327 971574598 360667093 387566956 412781061 578282066 512825588 53070390 279647123 579199824 606515663 124726806 890876628 201005615 23731651 674060065 248567730 320346939 258731099 674286027 169467308 402030901 265880040 524320112 329730646 24082903 640695880 46986721 875058011 369546737 374059277 821804281 119987276 81030984 551039989 705444991 737109203 487123867 537355230 350354423 80719702 643533568 784129445 435508051 377470420 437921437 26952890 607450068 317089424 315764173 15469723 932299645 598006560 953215862 907715968 71141535 625147474 467974498 537650294 706086816 360295142 884848038 118877543 709366052 219922347 501445085 802183068 613296403 472561760 301692653 344526588 508166646 269516271 489341014 973564068 174454952 851560037 737011176 111176755 104903910 603404397 623556874 734114265 853521024 110891428 546557905 847555347 578371029 737545552 808768032 391632037 642024215 142299313 576566269 220851977 69792790 664577254 562288065 936616275 616620504 302760855 986250396 924018001 187009592 694281767 101965016 71795751 620118857 797739168 121214777 230309323 78717806 997674017 134231960 393926887 853729346 859747428 792172642 54116780 656458126 407476264 390560159 846298659 962228315 361415565 177631518 961229855 689113873 458408490 402945917 280109915 143931486 573539314 839712210 557031028 398001532 612637511 357695056 463860950 923811175 881130385 19025286 947719645 740206116 108891906 121651729 162127749 490789107 404275646 457536953 517515749 783634236 898163887 696151118 968563871 919181656 635652214 487614013 93895867 449328117 684583342 421358377 422701500 169469602 402834465 20945418 683264321 424904069 176963286 227288970 566099764 495009862 691067999 372795739 351065189 237549244 274680080 107688395 500614988 769001926 120974665 565053685 493191612 315830857 60965792 779082088 700044077 289967050 165691842 865796629 699650683 366642304 157354157 179689091 796118843 824193597 513238189 843599878 646793757 546930965 204935666 61525928 310805596 47174 332437171 141577291 971023531 719422790 981241350 433909889 339090932 681739594 584518735 509147600 874740855 547379045 935988904 27703788 499911155 619095944 937558534 368778648 294395765 305490952 734588864 267027030 567609405 495054391 287203212 340469552 820858810 62338242 735222602 458790663 72281059 474078655 364669279 698488606 203930288 324407951 193467955 40296890 814594573 492358391 421792199 692892569 195656597 322490117 387862403 761276333 679151491 824618039 522941360 32610774 691224435 868337346 790457740 619119155 350175891 912550008 544905661 597385333 611555179 112795510 868334245 214688947 534300132 46333382 588393522 622616489 738323313 596183168 95206459 950991120 77440289 253394635 138580167 184170020 759974339 697517623 276666684 158100337 926231263 667512163 977174115 799461385 116419186 961255812 348276423 795134337 229218095 726561762 544763860 356639112 840433669 808538557 392630030 853694324 998976576 778645462 179744787 385447770 485393133 824497029 739678896 967074888 663562813 64041490 418915438 891358640 401823969 154000553 664018555 15679265 524167975 584358388 334871305 588814048 79355251 535295238 373505186 711458518 605580994 70471683 706613379 389939104 6005312 154303192 695482007 242826083 637038583 117266773 672327757 431832442 513339638 811922421 110060157 66381877 933268455 565907025 397081676 758555316 373888010 862487803 554312700 842913038 759008237 383291396 203220381 13196276 496310412 3623856 726904452 332521131 355009098 613561205 557538330 140896419 924152749 276040326 459594416 787358490 179509691 457960961 286837274 155478043 485635019 566391926 90211638 10339184 76392572 177053519 402272833 480327335 864766125 497143885 671119376 784322889 19711803 303235106 952930228 238439540 568181068 834455264 277846560 818652764 804007040 601691093 400358922 137042883 247447852 448412314 644479524 708561267 550795938 324378680 108334950 268975292 103192962 419514475 845571126 657840617 183863287 564318018 675908822 235995831 645245868 101135894 768738377 876307459 89441848 936418536 6835901 488470529 912104550 819755700 677783786 630974076 22106428 386262624 204775254 671380113 363375607 423070543 253089699 903471318 943179272 659714092 611182026 68354972 50444081 70673247 114198951 486151230 885671463 853914142 561607441 943450483 343479685 502801717 978909231 135430160 128261508 514172922 726159607 694633656 446987681 519732570 293872607 93315965 930538934 941460023 221167368 253459837 171464236 557714266 383605744 886695710 832717211 731642605 31628490 92176067 945317615 56904818 907980369 818843116 55246923 80315140 667812549 532495463 849068168 782599497 692677658 978737771 847236658 56010095 394427949 789544822 532941596 383104223 802754222 911170980 727315648 869774143 817051545 329995467 239321575 245930694 66381475 314245898 436548746 150539870 88058428 675145148 793129361 148559565 123984210 260762448 80240917 373418200 503078487 737726628 346049557 290838347 477418278 476110295 373944948 881982090 799045406 145476422 864622802 43150975 944491315 147675993 128712665 395807393 36192854 775004922 837577703 147816334 386044552 589403210 111606505 500982029 548891646 896267002 444375866 170743314 565977771 840027774 199714848 383989999 84010753 910939976 474795487 716190313 529013562 934642063 309391083 988322024 910524072 657273610 618480497 289547386 936661078 156626108 927162935 848359924 380373954 649484699 353733817 721379573 388753559 50615567 194735156 86527200 148141524 421526523 556434866 750540239 876097954 357059549 407735239 447393520 15862927 353071335 122812998 704983585 159189039 315054083 476328361 786366207 159369642 969801804 353910129 215975785 48604475 972519832 365554359 130797061 313820137 730615195 584917359 554724520 274611333 241425468 784216072 287778230 348629130 741101843 559171977 490017016 876678663 440640934 423374956 985596099 545789841 665667314 344452781 531276962 818004751 980137651 858986453 704757518 810623648 349925445 168313215 43521042 835831761 657635492 827934136 679697979 990280635 310497281 409543394 999016091 375234547 762429216 962698231 33726684 452853582 301108719 124453633 65008220 822234446 811009836 227120677 647458736 88757009 621887501 909523681 317715562 151502956 275229199 234205437 154930021 936061945 703018014 606063404 119846601 534584247 106138893 346619354 411785643 702766159 764420125 337882237 602226349 416479536 205267397 961535380 886378092 561518657 29876165 639566275 749682978 61600386 249982194 663686612 687306652 726106295 57037911 980813450 307167789 594512088 440716398 993976081 359874835 484049449 234003282 821378789 594151747 116552324 805222246 425713838 159137981 555942708 388660260 441533328 843662090 566324381 668646609 766529441 238658441 879715654 758753341 184541792 866892867 610228243 778106525 611234478 81781093 176777839 278635677 420515748 685143542 998606955 356575517 659386375 546187250 947051121 252927828 495100476 267910138 503749721 53274323 681031250 92680322 861181608 7811909 161805360 669273684 767907235 356392440 665080170 125601919 870762507 37447683 513389208 664301068 132638848 538849713 216999714 884972390 741188233 496005005 225563399 452993681 795225203 618940019 585974317 999395102 126799205 625064794 5377394 121389574 443544032 135081879 796424427 633959075 754265819 851648559 497002660 327745157 857720906 757533694 234741064 148819911 757699142 843894292 539232626 116292761 835030748 889814052 699323955 321834264 717764940 769404368 591867884 851890736 193940012 448700421 360486944 482568387 497116714 365548897 352257364 15953031 543843478 954062318 296520981 355196660 535752479 201515780 68617806 7365536 968963689 908417875 273181522 14251244 872439092 688656565 823355411 151666781 768045094 200985533 216093755 119879381 792136973 978684953 107465104 837590876 915889056 932135395 389045617 518210134 664397166 878542686 336184410 72140927 968439926 621527606 635865147 367627694 233991706 306255300 566430516 773681433 720046440 236857912 169555249 183193677 352577357 613858082 568150636 807108513 39686784 860013389 299585550 579156161 898981815 311480357 574567371 105977114 962359709 93574120 176717552 33428519 425740570 340934056 490402323 223534653 292508156 502979438 104465873 698116414 890801642 67660324 72512766 307930881 688255912 488310136 217274917 136616648 685854514 586645741 613977767 806444049 438401860 984520883 357716887 880506835 56528595 770927537 960521670 169383778 918530495 300089889 798493604 868390240 924745663 730565004 267264478 446401348 18261380 221435658 49751170 154055370 69799758 995462110 764140171 946258427 668574330 234083512 368193074 752755268 602277082 787184142 939925603 65675581 966311147 341447353 741703891 132106749 673717511 202919007 977674153 983702218 292368801 498224959 61672301 648055133 404958397 998991641 978449897 165119924 250763009 117787919 914928706 176545344 87390398 931847789 495609611 519711466 217655226 461580117 928189299 297985565 813894130 291181222 168481469 623798056 782600145 973421497 880124985 654284923 830015504 342886284 792140896 626267770 388684824 782746656 859650127 517192041 60976674 888775451 989085566 333388338 33894669 668190602 593752652 181856545 466408580 45509437 758963107 495017831 982955516 746566865 694163614 530980978 102230139 646945139 574106650 499397078 57065174 32165922 979390862 2625857 27888181 382114584 361484900 524527973 218341781 797434729 217118055 238675935 487211332 895305800 665774994 691212124 846480470 358480982 601696779 891171029 112420045 595224399 523617951 916144628 317023832 507478491 32436138 420150100 253374113 846972408 95718084 973028051 233815764 318932925 790620705 229352586 917927991 553588772 901299339 735492025 942622361 467899954 526664329 155066281 224303382 873153698 578533033 697674163 758567526 515630645 563533801 148606387 712677555 962966859 454903078 646638329 676945098 841751774 398552998 974355676 340724943 194067283 853076302 795376589 205133302 31971545 942924659 882990991 496638645 237370559 980697068 775961501 352751434 566433986 476783500 513466659 903197496 786956806 456626939 639485709 747862718 596228151 517320972 727520676 857733441 456550666 11501699 412746103 308941366 444191020 798498490 686914841 855393015 561992398 667079615 821200158 895485919 221025844 343092550 246315349 276875796 85506948 746706372 503542316 884575003 608890461 171291706 653665636 486871741 106835696 398323688 415318666 676325712 431992952 534791933 625098599 385708404 381803401 921800173 147318411 718128892 107364787 691313479 92880619 184258073 550650645 83964555 569050981 755699636 448864456 141688856 312575146 930943956 666469931 777572965 548437934 668395409 583597355 940148207 559558880 109723566 348341365 834543539 495919116 426918232 932320559 158154806 345218937 449216562 884271704 539143135 134492839 423431466 304033867 833120064 939604667 935683330 35798312 403412563 206780188 667285755 159841372 765553930 3131 906349673 129127436 64968250 796023835 113962788 12300582 341683169 273852533 14612038 256933990 746419852 560002086 700509572 743858956 153296541 669603232 804946752 60457844 575994876 455159187 497649996 351610511 562552486 470581265 612885829 613289466 210562931 462823216 756924504 255487985 516711468 104604620 514210957 386245529 625103810 420203225 530622774 843138850 856231695 676047826 87556329 136992937 636765148 305927583 972938363 367116267 79393509 417245718 825900073 838587540 717006966 233205808 392688333 658648909 27594282 322572566 134963056 437851592 911931989 963266457 621104926 377136380 237682229 491228059 990322949 317521853 238752172 967544000 282620456 675649766 771174109 123706954 490090453 825358028 755443426 939157863 112230598 230099672 174928352 692124501 736283690 128909037 610992132 182547195 549935354 553366921 853821697 536015084 705575798 956392471 775238547 494695163 460921025 395573873 543204009 22916825 28879849 492150334 820173797 992196959 979560583 817807184 757382491 457000191 889274249 809402041 78648727 835495960 155973890 218985573 60113075 119193993 569060880 743523425 741804389 954932820 295803291 194199050 754053341 178707445 529287259 35838322 973135580 692822592 627024156 607728806 118357860 728542285 288853088 910917120 914950343 741595268 202024016 675089815 637073458 866534259 785360624 989634478 542089947 880105456 748847996 165821009 755718394 568658592 346157335 585746214 678125408 788537219 522422313 62380677 579406095 82779373 875558415 985503180 130848172 656900411 74731669 140387583 583100561 708718100 373025751 267827784 826724157 392935171 262340437 971581078 843067197 124461948 437119030 586836571 28081906 982311516 740311583 793256324 518309331 868527615 981323703 609000152 202157154 957331334 653491353 536563533 311757275 194941941 990399631 973989538 877717704 989910347 229291802 60942964 423203337 279995788 779683254 231265771 872844036 340437953 500517303 303100201 69452751 678872988 884815209 693727540 606542656 266183152 442445245 616309081 991887057 5451480 405654394 45239301 817220754 521235097 395285192 49462434 497613033 40019064 355678522 340620225 902652294 764537083 761304822 695173609 487596832 857341524 326960263 244682093 268917222 33393153 615325048 522364578 613659550 111466162 570847174 971162107 529897050 436896759 47950770 301159230 175936994 313839133 415762628 402904360 134261628 877051272 772817784 326533253 623383021 797760239 796084059 301401543 13483483 914922415 772300418 652054861 552122329 74894198 549843872 346816274 142267656 864983029 530538542 456183373 909935192 458502681 58037448 988859253 481886555 822880881 708306659 980975521 709883153 153256736 744611729 734409233 637260866 610180537 951161841 206682155 932061295 492934542 933746938 549517654 700229179 554200645 890471345 55600796 449689220 645004726 569833026 511448556 174300484 611888268 296334796 454682368 754229481 895040799 345581549 710662230 580285317 593742243 772079893 28773176 973948737 574107596 855002679 673158856 327552855 147117829 341924659 545006069 181313477 798705875 490516183 250356213 702262845 717815239 776563315 483737506 266838727 455556601 937254193 6683336 371772802 924674951 525846915 272560073 720484709 282451687 282652726 624329816 633522474 653973025 683393951 787302796 506422982 471593345 955717915 740098264 747049152 708729927 494880202 697564422 842970160 953289455 937892015 931065253 79388937 32616721 539921140 114207646 106713873 405567702 946233290 273763870 466970663 368962765 866874301 782375077 268332186 79216544 579662947 15858831 151210724 712439385 40553077 755970536 237334253 727956375 740321375 419792920 880368618 64314291 274757430 88182115 243926568 289889560 994614959 764641319 286824595 811741827 564691124 577506223 918435705 479073353 922323854 825418217 446792327 517374465 8749115 19864650 42195026 115004976 917180135 888337892 608581133 27651236 314822797 734789513 38529392 843003515 348614804 506040280 435873789 586439149 823184877 357283751 148448464 879918525 471911205 748548853 754087580 75273905 246179708 16847635 892885758 557290624 982791470 663736439 710737764 592266588 724358976 61294598 861797180 728034609 652501652 25332426 464824207 328813273 729366688 425362481 90159313 552910968 50750294 217012621 5613506 106564838 805791485 592759116 281884307 789496983 966394222 277870831 467790470 996684563 137368359 855163965 924894783 469063894 769554441 717579045 357804405 159241416 447325918 232840366 904078718 765711957 623884038 698800927 435337202 412657244 798339394 988895738 563570845 937310490 153999089 579931110 604171790 71446390 444463683 142859905 295783662 449235362 900622617 612990643 58341090 275056574 5584717 769134521 641837715 779591654 654780714 799516692 102289143 371440190 884341595 151999394 576517364 948554546 552428996 521542467 517877687 916055481 26135897 61244298 120604831 514656819 632176633 585271129 86422971 500317368 834758714 511127699 674421857 637296628 411314249 741805234 890549208 933088020 299329982 370246626 498634891 817434562 919141053 582301127 318496589 264617569 162658738 101034717 581856277 97394281 541625629 944175459 272623364 764415670 266797028 724988304 729300474 825876362 977723867 610498843 944193064 242854956 48474221 833353200 82730891 575740278 585216587 136469483 658139475 40877699 525262561 92887660 439159525 439804754 402718462 94867391 714353568 602997346 12738855 232449819 674238087 723862063 174548925 896647658 856138127 795856881 243571242 938540697 296005928 6297124 776444777 613339027 981827394 37926298 521374070 436566704 655636594 640147586 542633322 904671841 982170608 865491772 35337960 789468352 624051427 36136399 128573862 237867260 133929877 775909412 486056193 106494738 606745175 484153662 708714496 74277432 309244380 61166840 728632630 922286127 613895150 845859887 504900198 594574136 370664478 873116084 226070435 980059828 728802033 182528097 868607233 835441217 513360838 946311661 724104924 532577319 724936973 269937504 398968011 818733947 988865282 245207966 708057937 60703420 770346207 996076833 868589561 368326262 598801600 299540456 882955192 1751125 127890991 837610648 50457855 830374625 582416147 145035387 130062129 678438496 510777172 967507368 891759290 839485107 38319591 596163205 136157832 124166856 285055326 58922971 864239680 606278047 818702772 43470978 166280667 911462320 24248922 519379686 735760185 941102508 913391151 90099596 256343347 407805515 15994543 714474293 453998669 374160527 701453924 120411754 438929178 106707160 196554777 721795967 310784023 284058985 89685435 328227057 483745339 811769983 646290907 293428907 64340075 904814732 480128064 822980905 33623067 487610259 217659156 999360307 236754765 445596416 712907348 179194112 947618707 533895081 87020737 974309536 375279304 327994270 616001653 197960541 124683656 87384283 22532578 296939714 668601128 722366935 560170264 708730334 74535270 711748729 942612116 793108176 943023514 147822205 465115348 955486650 26774874 496069522 902946134 973757623 728523764 889646379 32054776 483484113 424963094 150305483 994740185 893245094 780950961 383504751 588234374 471037503 239276767 159649065 762881678 945351177 174163334 517493537 820509740 135419519 649535758 439573676 659916302 1907209 834694349 11131389 847979295 182746777 299802085 219508219 740213999 842923527 181575700 644636446 537751847 268803492 506417804 75457425 268427279 527297125 355234434 132342660 703283452 91072629 513262168 130519422 167321206 209622412 371920506 860866997 841319982 41814611 131172641 447134752 262280984 921324058 423910137 545646882 361333307 317853975 872888415 546033882 93279595 3276242 460769380 98725081 840440620 4804702 539128 804233067 659814532 202267905 133251403 646167049 697147951 931785234 739615555 208061216 840299229 925118963 158940017 685253541 818860506 27244524 281523105 567083266 384621323 781947706 177541070 829599148 100954018 497340769 96232999 830918321 317056500 344034941 203762390 454605176 559302866 395384784 507210116 593333693 306453181 991925759 857011988 826163157 663512263 54180294 442710492 216628734 61579909 835855103 649683348 972283041 804703412 412663740 770705571 264205208 91753840 953278620 749585644 640327967 359552047 484066482 649104348 90353730 236345314 607235618 797115827 171795305 641382376 84892634 878608600 503668629 211480026 684466249 554058543 22091481 139469984 472326034 332450488 394136412 48236911 323650328 388438958 954505903 839308827 722250206 155425846 93825781 703866388 591830559 858642584 645597134 89448999 520885451 574050554 27240034 316030183 111028209 950055288 553462241 434613533 540117538 840331456 899775408 539790528 737254598 838765706 420868098 70154043 719912767 43557331 271361818 158053065 750567100 409411391 711981203 89506593 590784488 267679506 867245199 688394375 527513633 138039019 614440402 494160720 235096487 846265745 389003500 22681593 336254953 365888104 977774709 14756122 608058943 272675124 906271181 230618157 719849376 436296702 704676239 152273076 717592981 660015666 133279879 534326268 914629846 644466640 663396071 489884205 596810168 513610548 24205722 118303229 888298606 458614903 147538685 248886794 93673589 978112791 157446586 877565394 876310022 11076832 273788402 266236396 249477479 652072379 321335393 426519985 745307432 429215886 478609109 56554054 441102678 524673827 562428360 692081644 118825197 178533756 451716324 388081001 521575498 582526275 712389952 196777126 963162455 224163693 427128497 849906299 909277909 158802257 70629046 701058089 250280382 481968983 741862233 216894391 948227243 152685340 487223688 218768530 389770072 726757546 967843960 29091162 890163960 834000912 564304592 545689957 353383483 852662709 724368354 693988605 533756297 66068443 73950372 348313955 803315175 139529269 486441660 592879806 897050960 429227611 976780282 548468364 79367913 969183014 318605855 126637487 296369315 908154746 617813083 209149857 600330494 256750948 484347416 371600922 858168870 518000120 774793451 377892264 91341480 714738502 307952259 32857610 799960104 487540653 239070137 376226541 61707837 951359110 498676240 680057635 782189083 391956676 520242949 837264873 126592785 319650565 386358410 830000228 255066541 933505469 83178383 388167920 91182470 380201640 163112040 300583575 2644475 905278327 249626584 250230823 197386402 817851531 277486232 402310523 21011575 241391990 526555114 186550116 570821895 661513718 585498754 956394353 458299160 956379338 659447809 165710272 699778067 696314939 727198547 832610381 591259554 207208285 151199841 829655158 728050273 28528996 467924160 685390702 716499209 673271915 335872892 354886255 449981144 866324195 420182190 833260953 394019138 942856922 351457175 578356037 158739740 713132290 645077610 774569526 696535573 619011497 516919833 322901497 917815605 335485847 121485677 661561254 990124049 413397886 686202082 701789342 400899865 63460017 966662941 165199107 300050459 583628857 125460256 807920950 176770781 209393758 593752667 554739048 500222891 687751436 339728738 600471761 203496510 649354643 699647809 488914726 405518421 778955279 61315555 990216306 340213135 901850388 90932485 969690261 343309312 844247154 304624263 94516669 884931324 359579379 876130706 144890940 933833400 502747042 990728515 383928726 503270304 682551464 479248940 162623188 618623749 722425435 149908555 974607064 425713144 744699387 262606891 78246775 942032980 588515482 121491677 634166053 459922656 941140285 286208690 893763732 712957993 962497673 487721494 163381108 189852528 109535734 876414509 169840073 952191090 207468856 702013694 692090734 714833622 796537892 228430419 292277923 965393852 23871380 501838757 84886508 419510691 109098353 225142129 397607254 972510420 838972288 232604919 90654727 559450047 930455378 19076053 166567981 471507131 124146503 151297499 89759998 897434084 851904256 694778958 179604732 917645798 475932017 627263487 293637621 231903804 773994572 505665282 295098160 359068209 289989180 912413142 33788168 421705864 764587258 762388983 558908251 385289762 381510218 814243127 340644235 430245937 426243353 439054636 482906622 117270431 961289189 172468535 357505892 987345513 721705442 959090285 140526370 996051601 963576646 513683978 260717936 698544568 933771843 424362356 418959607 811517600 840007337 638356718 264488599 819287849 194652639 759120789 940484366 753661095 583303332 180587623 977225932 455377824 809935731 854620318 619504129 265801788 925119037 373458559 845994651 651272680 423580158 820771672 557234794 132528217 364308607 351417628 676672787 684253033 922892969 877934257 992575460 544702730 925060337 326036493 249614056 895176359 866235019 254969714 325550958 849690038 318756688 882606810 864098407 555483444 131240106 698933545 808815652 317040062 489082627 462425640 239579792 595316476 427620941 847289817 363059543 528176094 356819079 819252497 577716751 499053709 296174495 765291768 113759340 933209623 948922296 868303516 746397967 312260946 224388335 409178949 669568653 708823454 995904046 882281025 485451515 498005391 549088630 640099349 866743084 298235105 512191580 431319629 253453085 330672747 887859548 684172764 689347516 917572749 836060393 812362724 836025033 621873739 943502862 610869481 341594489 872566277 98896847 968366168 118244653 835721549 659595611 484886156 996514092 745276408 117961823 58858643 487256659 69706984 870242747 335958601 574257373 382655038 262490579 910771073 175911394 952593482 783410750 986558971 13686846 147050352 929878104 552080259 484226869 242199399 864767267 79182676 892509204 73340563 886863288 910694704 222699298 793630309 947740882 352938167 924056932 418200389 880039301 547143431 909963328 612469388 685554184 333410526 812927087 584074770 600681633 982011383 227029777 907629237 782272386 120277631 187037031 553754571 300799329 777697836 981305192 415013836 792448774 883915460 840258526 781019375 100478971 38957043 365824169 775834621 662737364 15236932 317643103 948632761 301005075 407813149 612601874 422369984 603882184 612266458 954353227 127045780 823904599 945824245 233740831 249152822 327781661 132460247 839765305 645484652 232977323 520303206 919902535 329016068 161865676 591540150 819812184 421669033 664537945 440985808 822981089 71121443 61811886 647616712 573484306 587227489 390509765 129769408 388292549 512041985 83666992 273634853 3510296 992947139 669673943 548528294 121320284 881164230 447727692 491683453 666589273 581314761 4292310 958644614 675033189 188121222 929075106 819467905 735148780 673376930 912485851 340776620 426020158 342662849 943445555 662252533 30453764 932767089 851164970 464518769 271160787 236315308 362159595 872837549 995993608 141817787 979971763 164991022 721278848 290376821 786120310 97643087 90425780 952996574 43608561 857027525 494201615 206242033 736430899 328730617 970956233 463474432 768091062 697517637 716874720 41742841 977970686 289599876 10888228 801455852 815878468 92585098 534658739 281138692 982307704 896857272 149172854 909970056 525497057 438673949 395660306 266584750 357615106 60359514 805146043 367143109 373187727 85242609 528927097 215351587 925797703 511194040 608238462 391541032 337272077 511650345 167562586 59765400 10823974 179865629 990296225 146994299 120345677 621953171 881293051 515783066 417297991 886316400 267251921 83384450 490071237 878709037 977745865 111311654 524594733 748914194 697237027 328193820 836258420 720524961 307674656 386827314 899421338 771302176 143828334 78189748 410081162 337961598 966593505 118543798 838455915 524010284 395972563 531434898 610697358 418543527 323758905 208326172 292754581 701986972 900234949 146885664 115199896 914006358 529164747 834740578 696906452 609717511 646369070 922160930 609742038 231544588 150192202 566076231 328455411 302352915 213806843 939633775 372844246 505706914 871782886 398871150 956896485 194281382 534519082 646819026 986303569 768718569 257480296 104418430 706593778 435831945 756798650 209099865 4790830 904393007 413411038 840925159 254255933 254307838 704869763 801157021 502134850 244428129 23253949 720441439 709144177 757304910 820828561 888034382 30457058 545765009 629471765 907372224 782977060 404278211 148271653 387595181 677733871 873819921 224556568 869330057 146535062 466577706 871070874 103193215 590028304 608783271 185766781 601282060 191257301 316681866 156104073 968703874 536546324 390811842 337810067 389869 766661646 314115721 565353317 457630066 838837526 324823592 460153027 81636496 848208590 388547756 100633436 973818445 259873783 176737029 869115195 393279440 505268318 159817832 23315418 163391645 254403567 610380042 799631323 816364646 985139439 580156170 951760725 865822552 318893706 737925827 187542593 913981267 206606950 635611196 380784144 856646951 47534413 386596406 110503881 133632457 465316026 601711892 690314375 625131200 900197488 520507016 584070818 460042753 693277326 712648100 914523095 177281884 618901623 198907486 629256911 565917922 186108533 873760039 28044823 257904743 691252852 300709505 528827591 114618450 314155951 223886104 272511464 444990439 252492217 71519 971824574 631403169 367428990 937125833 94476957 285525085 342196786 638945784 349290523 278844825 349319494 642832743 594909047 13893731 487344245 209874957 808890536 947214711 230366872 238159539 776734 422365343 170365310 135958349 802103556 302078792 900869102 669236022 560863529 137718107 858972306 414790863 764883366 819043074 819928701 465067832 440788207 898884214 923966301 479310371 261165381 379531261 148561849 422501967 646316310 427563583 951889247 320872164 388322032 701673085 975787898 861112843 739397208 137076299 671301644 518501859 494646076 736826969 99155561 293620471 127963111 234293864 954630316 823161027 291167749 174956045 704951147 190460124 8377946 735309638 131944935 856992550 253588223 371021810 208373270 756380702 618525626 537579207 158685997 304895587 804838418 329755049 460247504 282456798 319878760 969581694 16281019 699412795 144748738 867608957 504393549 688657297 168490442 173623346 92749791 529795298 750541919 708394701 78546513 330121125 57703289 268225055 189813574 942243684 510337681 63044985 91772975 4548619 219471511 483605770 233687188 740706142 171584496 194146473 382611581 368624752 856543294 367094083 728647030 746247652 287310287 572327274 164706965 648148308 944352399 714870567 485632078 827886952 125310495 494280958 700494849 609548881 789319398 102263776 182549041 78930832 68868466 451153929 908535256 249731387 759364568 756893110 868616854 680218099 882329696 111218269 806379821 556695621 712785981 47272084 611999781 965318388 840828033 512197471 918398244 995136161 43257949 44055821 108142464 82613792 130688492 946307834 36777998 79235761 931556486 451936936 215634304 435324098 115507903 65023542 13950470 509123181 348720049 707264265 67094638 772919244 32641172 930768829 585985763 867974216 590705386 189779217 614484218 405995407 435797512 99185884 579037470 803492492 641199838 306434833 211412576 521573944 231677540 328322512 234707770 950514409 457103064 671082959 109424929 986915240 472058714 180028840 805242269 590740445 350292676 725885246 550916310 347322301 157463147 604047701 15753090 191102814 999639846 928623987 478234703 947041782 184518392 576728618 468207738 514037303 268842525 64659156 746699019 232252895 226348354 3990641 570710361 950934939 928495449 333098269 128671787 331267518 773808052 392104581 115641091 94306901 584917696 603816062 326490532 949447594 785102509 240060524 201508183 334703976 603610093 645281227 673975853 464978738 392306631 713731800 795906761 445189600 581816377 182717825 199398270 866521784 895529457 924741896 870767033 699173381 972513513 361949253 247200006 834896802 838942783 55886133 706113895 56669805 791258204 566342999 911431881 838336962 307620658 650155211 654848916 349554626 947668138 562594683 120779610 584482377 710112885 611853068 388604739 198149271 634918107 635660256 333217819 552166942 218902149 855996783 403511034 599471382 383482682 713965475 447744178 612183923 729371019 86131591 354750146 741747464 839458703 483092139 721310110 938598928 667631600 880889375 610069704 620291370 63152390 139460851 190978580 510811660 228547170 126064317 264958464 456610226 160217462 745100396 344503563 511450689 657501727 841674694 745980774 755607149 355482195 110414137 556939816 836318277 2949904 622425148 43804054 75007987 198704920 753924144 116555670 749985114 361506293 235179017 563742805 226647067 451849039 766294069 500235607 444267631 13309765 398495693 559181683 681004780 349070165 340502123 926723449 886703366 2624960 406983220 122029246 404397649 343459599 320855795 115471054 882272678 657119644 57161713 744393056 222479304 158689870 370610273 609521477 713997907 258983242 281728452 536955869 74218652 949059679 261272849 982769607 76683901 582028373 5560836 292071711 197279290 638037101 346245898 745107366 272946634 291143803 999488699 713389703 368732055 53251505 497281318 783374608 801809464 263943791 926812783 298852558 814290418 304986170 654289662 731700928 537529375 739185349 352741495 560205732 294766212 965575187 667367473 751737645 669948371 822501529 218363377 489692289 180201034 998709760 294476665 821443286 457548008 287225374 168468029 443397580 30136445 60510588 59030105 780499976 630517847 796555775 166473557 900746917 312743918 748324603 168707850 61102171 973531432 643043001 29913892 880948470 416043302 608555852 850148821 244773267 216556216 852348256 876384678 149712699 31196353 231441924 263732999 329029661 866906656 30458170 982541723 733368668 320869746 558538842 628489544 862125897 26882518 647011693 227691311 672536679 24919741 607778935 309236551 909778619 558717255 542123424 118706998 393805696 801158521 181317746 396378468 154681081 182194109 320063979 374452830 555403122 650720030 762987607 743357510 297784060 220170432 950384542 185588213 731633538 235550936 735027078 517575727 329733054 743383503 335549334 559575010 840902065 259810177 247856978 67674681 171515721 808293951 823866273 610902713 793427108 857468335 562025356 313380015 645287582 330355701 647482676 262992895 437286254 105155927 448045247 923688491 729508065 889984173 47439411 590939412 515228215 362317486 277700677 264995414 576933028 429627261 411253468 953186186 9722708 129986132 769497902 472830636 829673978 367726470 93225478 135439663 950009288 515001147 961290459 29191681 352448240 128988351 713645290 961558400 482445161 188248873 874708139 912032819 623308412 470269236 640295243 213857515 764241101 933515061 508871593 724289243 670553505 267509044 44127377 249211049 30713637 497794637 254975805 206885813 625188211 621532775 390717345 397530627 7470753 474412621 558677251 193500141 670210822 239171102 480074387 85644084 691487396 377067791 673821134 374420106 411174386 51034292 179613266 642293059 408816152 895918466 648896607 202656194 466879733 938406495 808570638 908913862 971717517 566087608 266709520 897539387 384723078 259110255 726874894 106061226 704283251 724472252 518113720 779355610 822134979 585823911 57455065 886779886 83165356 682500092 332243568 103138098 303711462 700217365 628200943 145924229 748812295 500483844 708541824 150559305 763052221 422404504 158263157 948371556 682653132 613481855 99978687 585934338 508984843 297593392 433108462 889269848 416959312 829081191 882209278 985668185 217768072 510448129 713722109 305906197 246652896 894277300 10018460 10049327 46031196 652559124 907575695 23477414 546119112 911632121 510253428 902112629 983620701 129551313 92455453 735989603 459120124 374150343 289546062 870364725 121189391 61742677 828972542 698708835 426196044 483821316 845478631 440485431 594277251 505898224 323553404 140030349 241478191 720531946 861447948 45689011 583797369 705507423 910934864 688329014 589628752 336063707 338334684 966249451 902254326 863145866 513665189 153299130 303659977 562144700 870186086 225764211 375686499 620864776 705838885 201486911 905675185 842035552 906471915 205051219 443237790 33184768 759269588 822164359 345112845 321885698 360074975 544144201 139428382 322153094 582531943 992388498 232864115 171104438 718029188 368671751 898608134 115056414 776779956 619035293 284673255 40248978 891119694 998975841 426740349 182763946 126975841 660792863 133519401 110439450 398811064 78645815 222577663 920308657 723139964 314543925 148217252 740068745 127571237 493714189 198455894 941196986 563459040 288262707 404263270 672582780 823510373 544580914 250345743 193070371 929566309 476496895 492993086 133364663 684355385 579803061 557466301 944724701 44033957 804700478 426404834 914264001 901132445 704207216 853678374 843126596 521094656 615128671 497542210 721070434 766531363 233352151 906039717 993948258 903835602 729701414 590120130 642238271 14777256 282189696 960318315 680275414 144585044 244187253 96114903 586426934 386936531 247842003 968923908 901525728 229937822 183254718 296329900 931929713 25935728 974733739 3632041 388247823 277843019 377383639 786486781 432821153 197173361 74888050 373638961 128353916 341403384 310324132 290181379 634661219 3456443 217015436 618899754 726471838 842512738 229736320 990082425 666852174 217094948 195095000 729366180 110485054 28184162 513839156 330040340 299251933 87339017 240467859 652654720 197962091 93398296 143342034 93312401 577405468 997945306 351032788 395839420 140059610 646527670 140628164 445899640 183763653 147510381 376954518 801478166 671616159 6869528 7104051 549029897 911516728 4310703 224365372 383645109 913536460 418546189 514824657 291110518 283177418 147740227 816861297 446655993 697198893 641008527 689949217 667013245 397806507 250038276 389163604 77337222 110501670 533604746 463277918 341342903 548781514 374851858 278138083 501103562 501295969 190153145 257065025 972380573 18266912 473278185 623433441 722773431 616337147 899184191 727499307 944680969 725052158 943384707 293321357 334964790 902517944 706493707 988687951 260842833 79181592 385805547 910890726 870078716 252030399 638875617 906675455 476760199 479808108 235864756 71568994 96291813 634236037 711379200 470974313 729701457 381960278 781778415 715013813 213642645 124406656 685162383 826279598 104852199 753420448 188839124 142738515 993211473 813130907 168989191 278484895 813496896 44669128 541088028 357405269 520556618 960064614 64645981 476812306 914803521 502858801 584831055 240540050 353984856 541835664 545027710 17814597 603214285 775038117 812457613 582493903 588897282 36297030 723372001 917202859 404734733 266355212 760371581 131795257 531366167 883954373 923095359 751898347 977952486 645726735 911445954 640608390 427262402 572277438 989912447 787402517 599406000 224466966 390264081 348833446 967667149 699737289 401395891 74524540 827962763 672629224 718512012 471453709 96965418 693794230 23860646 324700934 289155414 683319571 258238004 32056164 986933338 80694089 242433518 354587238 997963335 747000633 612296820 820021683 908294942 334813339 847395007 28296965 147316329 155811179 174148010 339701484 130638373 371426337 498357183 919608402 829636055 722184904 223278921 366966834 912245449 689150802 807567881 366655120 730019953 466559669 447874760 131839254 103302624 16960436 84608063 198061378 432211470 705726278 542959578 205478833 879125407 75536421 566975758 172178911 612289436 556373670 580083622 885628544 644442392 723862326 524526538 90026915 60048515 857645235 173734040 246682770 205449103 329349795 970467078 617732344 164331725 912028746 79997538 48868567 893255916 673415159 837574886 85712948 226115072 245660246 754605071 385598516 440518401 84309967 385543871 919540805 721933407 797130017 570340298 288874289 62452456 775141222 293831951 901369397 430275677 558136574 847895028 509690414 374100708 557399925 364113511 161002594 154866821 709842454 589606477 343708006 487630686 198949343 7416032 652129244 631292588 725543369 822112722 682038548 876609358 700307229 723246810 881942346 87212661 743270095 751814278 432798129 368612655 674189038 591492244 831307122 841446492 751200322 516131310 81162849 933192711 830661990 392598706 327837605 273505344 774265440 173897541 433976419 769139567 293892644 347520606 615686675 472683091 302095116 719833478 529531285 563138180 106353469 626147807 503549786 884607374 656450272 330893157 283964938 691335625 812486691 711401098 266327941 313191810 860552928 756380150 692783370 565997448 456206537 425911029 426090786 707218962 843229156 749080146 309343945 291346187 675253766 929171938 644426001 263322894 487539232 701258995 281700276 285839136 830299249 275289580 220956488 510929153 116576856 197226642 445032014 552556502 267826106 184917339 111752150 209749121 498377152 23268958 838952755 835035155 883202779 529702542 956558406 86714702 347380940 286101039 547309595 982797244 123992191 653540983 335208834 666778409 601660621 682597082 942658162 468987001 453424974 62164304 361284732 710792958 463120796 636403550 258417291 151943130 80097565 201061468 765029611 63723539 302144577 971143861 908777794 53198242 452338761 11462089 817722021 37735001 48664337 25274421 129760092 136310840 614321155 705085983 806155376 807235261 618393481 630253384 324385824 814099447 25876682 730589831 278568773 676745278 255963623 171535062 960748806 186262513 859108317 218118446 952318116 497505036 415969363 31004510 993841061 815031806 102272775 283094648 998772160 955014004 948430666 69818329 560309961 183421057 25041880 446358376 402363417 927243645 906940688 452219328 129892790 848795689 689133084 84992164 228419146 622048554 255774653 33744226 388095405 703903521 224432424 266646727 928343011 742341935 116493260 741345153 871751946 688170402 533116024 539906925 260913254 498890117 965081850 858297259 782422865 753978792 932909049 254214953 14908577 893119941 367424432 893366309 462158876 885811376 5503858 765094171 480968223 326121852 423919431 761561706 731978714 494555847 577291874 443893541 539538066 255070639 83301868 332901942 665478922 564931059 326946543 755999198 306949817 314574798 881244482 15971043 398314193 520908833 988027537 797436267 513125801 48004574 461068102 934646128 258857095 892169734 494659186 587010566 172097020 152637787 441899429 429227785 846166344 514045208 704468924 99616427 650467588 932501622 813872148 67306503 678463076 174062547 525354361 496063414 939153881 474077613 60475149 85049980 688634896 330123193 371280388 255751288 790172104 912576126 634909418 196197688 152857802 768508957 877190548 950749117 392943253 40275700 250322995 3900620 604246361 844324803 714249711 213311016 433529797 423461665 683051178 829645746 905512882 252650896 164017920 43587537 705413675 140787532 433497007 633856209 932936581 115590684 833788046 980268318 921870564 233421697 641044819 844359924 258514097 538565852 525202762 814118129 17690647 966131077 107407546 331770740 807982994 688623020 804399104 462845066 21941441 38492339 147066166 474927932 719480228 878181162 264311736 345466140 533663556 956710476 253967600 244891336 530917842 99562755 818398828 95312140 938835566 879063515 250405097 502591002 383728474 948815730 619937275 733040156 769639488 381781225 667013020 253081798 146453600 901747385 362166804 484498742 26003665 757204745 592065708 428454988 233717692 460755447 781945322 273017251 854595193 652363120 123777933 881810314 424451850 777955564 163210660 541667436 711879298 83641800 861062279 666293749 167800724 978268549 516426704 468271976 25558435 122007198 576206572 346057577 705966875 555544774 896324703 824411154 412649135 833290498 327192297 40101069 840317061 895467164 12633349 699405452 712649997 379322938 787882795 135301567 320395195 190888315 887124049 61228436 450699492 538253872 501067768 121547353 645057080 758421306 815180629 658530810 858317572 286171966 92358518 799735237 530762322 39517861 301235484 81433133 248270399 497188966 222186088 192497374 424129117 374931555 954797062 893471222 365292804 265434505 198662331 847873367 214177967 978377833 557426316 623054834 315848421 829949515 725821719 867745292 734260624 403366681 640902628 60026792 817802719 592254843 219769536 915704821 734490955 196597832 952952473 741386272 804829514 256410751 489519901 663123212 752564654 361972460 129296949 729966533 870566805 692672042 349814864 617546465 714175098 721189398 739407072 790833942 643983141 728382588 909973681 44139531 153802932 250057929 628238577 852401694 950110985 703542159 865829114 738755003 662477272 994073329 137350747 202728204 529248910 293517434 111065483 740303313 541176756 222465334 356196655 216196695 162929729 797658218 379780969 680452963 666858952 66843821 28004947 531749097 286396986 820118886 433854481 360290957 262676978 8730021 114556182 511073892 555027574 27974185 516705242 316425095 604762460 229675666 310289485 493624137 376083513 461757552 409291022 593111394 695024322 18336514 988558148 835068454 117371273 694839199 444698791 672341441 582733158 140780778 161485569 966754324 560832315 990600250 264439354 530426072 327231281 323477039 39755777 745989586 181783849 490148305 932565364 87463295 559928861 772820276 689805572 180424637 3474111 378358840 262989899 895179975 225816844 960718736 103268137 204544338 101811786 922315944 860890621 768988339 363047698 742678389 717150792 562255239 316574500 253764930 430842332 211699929 713705310 242985816 53112362 6780277 363096627 775978442 362328575 899191188 549705686 841004421 680338451 967549662 332381972 115476716 467540706 202416441 344840429 23262906 148895735 553503247 517782199 610331757 16880718 705515581 827295252 827929045 889079176 263196211 612827176 429324196 894341879 946365324 506546129 101425833 327148892 54326480 587488747 550010729 777949065 153774502 984355976 811361145 628986228 488778844 969104720 988799018 739698497 584625359 231665075 215606111 550581377 514007306 829385206 872416082 554944380 174614448 541488777 774271492 847897712 67553769 510368731 167695199 312937772 607848235 52506303 309495355 578540822 98727703 9890868 145395435 628230821 583400108 578844815 67369477 413793027 789948022 991073445 943806987 866917308 11037038 978633198 16995896 771956984 729974956 580537697 919184558 322188267 103675712 447220349 933579160 182584805 542236259 476490053 822590082 200439240 850729510 930523044 555623830 796051897 3678658 400524532 226515141 612173568 154359273 319788795 380720891 364067589 3052027 595931079 39692508 501203908 989742351 211129408 470070771 334097384 782260303 900494441 394795310 591161972 310826008 791501252 968804742 924304499 780389753 903213522 671261343 980084345 64632807 847378611 917330527 175501190 57251740 832066466 924269156 971849974 600037157 983186726 328342008 12733132 711753713 113892014 530931594 97502811 961033790 883631528 434796987 291502971 930138710 997653014 436061505 50000847 39870464 857383315 476081025 652271958 300110210 238793257 982403443 432690622 332018785 959141966 382739432 761761398 809085744 605094141 944014202 804814091 82808573 702931600 244573551 180708448 508299242 883382968 46514122 496612540 944652789 751542880 502561550 665113627 169198646 141639983 954220145 62100068 874141576 995361497 391977970 181650193 384561878 232496605 431710671 39336957 889885542 118391669 282250386 297788378 473980835 911812578 146161327 896041054 484839982 90103805 208505552 893320260 241839617 489965105 366829821 652633131 940943284 18805801 70421487 332353883 105639779 633678337 639357121 695319967 529254334 455557728 685916041 333478040 363501959 792666893 365091254 718576726 595375305 547220028 130366484 780681942 401899773 738062406 99429085 569398029 827797749 403045587 566468802 628746826 458158462 868537409 298210504 4944897 585911526 661296423 75509369 874209341 146977324 265236171 187488507 20722595 24767603 520685999 837735787 286629389 336211511 958067413 409537718 458182181 895287368 436018506 377677712 224777894 114375376 503609164 106752961 58646411 321462643 268216762 489682565 398492789 530806062 768821296 145128562 994718436 560192152 926000698 889595072 879334334 509152637 764956611 250298113 180839551 734751746 439798693 600423671 11803666 835832612 482506673 931653498 341420081 799497285 968044362 573000843 131771326 407324250 940713866 203851038 897975270 541250592 451831680 67058523 159895285 983639639 84126488 280051692 225955889 251920490 505971671 873803799 205190844 540050063 733869004 607531281 727471049 817262501 662814180 547994150 287547555 935111764 532744889 843835801 467858577 358282306 269768560 435675576 167871155 20266751 710984798 630445929 832066048 234639678 182277438 433160990 60661295 504769888 543398130 310953889 771063453 173511134 891068010 93490346 696218672 859420028 568881345 62044934 729016247 522721113 875825650 908528005 798307982 293549552 999681729 258114720 268705353 143553067 787004914 338016933 547985916 371953213 260510583 274142944 745688507 256503398 523313342 431323361 15436246 151913763 266545160 346482681 120955141 632342749 394473775 693269620 859036848 815208389 874553958 557513879 147334811 881200703 337191203 182366922 814516340 645956555 922825306 487648588 716677001 233991530 586820489 697923899 626940802 862396414 413274482 586964519 112827925 133350159 298051622 311920818 114403866 249153507 683049930 858782613 279687786 155349142 354999451 432203407 994676299 756292026 863154431 18793348 984139743 268618903 14405188 45464320 954703971 232415500 528042423 895875597 930399664 204095174 85227255 781644314 197725955 241310298 202849952 474540887 465343547 756469033 63719392 965799288 363917292 475101933 313859069 643974987 503627310 167516572 15164217 879143388 287843769 621620689 242993794 414937804 696921453 351836726 21750788 37892434 529648890 669649673 378590070 93321654 673340915 617127431 700654984 416696017 996776009 542954946 442377454 657957002 381158276 703981759 637201864 192860647 259161415 642473964 916555609 380293844 185146225 424287317 575059474 768230408 353216978 345765096 95043953 544875986 384403077 912663699 858733861 537505642 968553767 763797576 139428163 982064497 247272898 521974379 933205399 114944239 916280877 87387797 532822511 8255713 491979627 691800994 671366811 505804171 688846490 669064410 493812351 283878206 380852398 697869490 921993619 14549993 738771044 580871275 237836371 45742210 241527056 50769234 949298024 518760049 827255156 764593837 454813542 147854051 280266705 453907680 369687578 105835243 423527796 48121117 9515010 353597189 10551920 653494814 782170282 969024249 671932988 240132005 665126485 362220558 484349059 217453099 535918074 889944118 886136146 235021161 580641999 123863917 783972951 265500261 981820995 596689312 878463970 560956366 439175212 99889043 909218018 439253768 114434605 779786220 687274618 86185724 326969761 259074592 277439727 949057469 726543560 572664328 426387697 662189686 901835457 765271583 543526060 363332365 70634558 858979225 47986440 326999443 964932460 508405470 342206520 916605100 549892179 856036725 784037212 317979764 281270842 858249862 856903989 503969291 145901466 41731429 911154345 550600951 381988304 279185999 827342572 202586383 131061381 641827129 269971081 408201132 125414091 734201154 722382387 114934283 110783612 575070488 662460229 657466659 994122477 127668205 325060041 563863590 593871505 965543544 849280955 55334980 461624504 388987673 903571376 186122798 99044202 74824591 374110930 745250876 275041968 182962580 474940878 268865406 271391390 780941093 853055876 854183543 169052957 647815565 407379919 752753442 604614377 536762334 684611370 796538541 351593556 8046730 752843879 685623468 143229516 77393574 359284565 667075222 83245669 386869772 253055931 552282681 973480309 14297530 677866308 762166786 809936173 651753018 920273160 828854315 402524860 853283091 223476951 707216673 602517989 666631022 458328436 314193085 472535619 904165209 374891952 887771610 106998921 895641472 559989313 276242992 859668704 11813992 997286186 882848115 815629452 905781205 293433028 217811362 267430389 31475067 701418694 381215898 231755987 949664185 373644479 114084569 139788652 495657378 223412406 624858117 420291356 474603374 103801880 303312423 891448001 975548596 44666201 768555026 510849691 100527478 167222608 822439819 881026103 226832430 845069466 670514105 952038107 336782623 252199555 871065735 37441052 327946163 762572121 536196334 703092938 66658064 700066134 259961307 390638429 668230798 718295928 525964840 92993581 618514102 981085867 154480204 754857613 824090280 258755654 906908678 777382313 63679462 823270334 158546135 465957119 73190307 465391531 580171121 80063766 233824399 245987043 801503852 383889060 539891310 486497232 847338340 18553065 834304924 583226609 787971603 337233117 739524237 157760396 92920961 482086909 945012559 820656441 949934521 808770744 594781870 995015569 654687533 355707244 146553105 216095942 700670027 939400626 834412407 566442223 529585483 865472441 487116983 224806055 931697866 862266735 52566174 881323319 720211753 57546226 514192745 208993777 716798968 969790619 606560334 968612729 965271791 117859925 635314449 275190090 891248883 963369909 961490564 260942597 317192230 189238885 143322603 853667583 559763116 438825300 52032707 748334570 531029060 449329262 344157518 310821819 853253220 320248605 724941488 120761618 511039725 475356658 358992891 968448338 802344098 670724780 350167427 279839998 124764107 340693427 337556568 393105003 24704525 280471125 244177166 667313693 539185928 463406758 15774467 714257184 33594429 961257205 635976462 831626517 859522675 958404971 778412702 31661110 366634082 660539306 524499196 533759845 258418697 132494778 646182030 680448522 406651883 349563595 925439769 479646769 971792695 805607542 896807791 236633579 720568974 136762434 686270356 458856283 507317401 341647940 350857569 666270767 977630525 211088635 260098532 267873908 162485769 628863673 705657894 948250391 24895041 29502732 572184842 301187992 481444610 762330243 684420315 833726037 495744650 628648678 387353971 104523718 593253127 850090096 182736304 144426188 406280865 62823681 392197205 501949683 468950381 189680747 40889446 157610021 554821880 748668200 542877961 132214711 10792304 43231821 547972480 177185193 181319043 931572433 97516217 359555364 544245388 377006259 292585802 348513262 266361674 579615968 151541719 560347473 721800795 225206234 514933097 138686181 53541000 757927538 425069943 729357762 67399158 788059661 686418844 674565128 864295503 939672162 513268811 197984494 391232924 980648467 645391485 307630751 40961578 769443270 803848246 11758872 86919647 911635131 251465126 357701698 901604923 510657700 790218720 175511729 886516196 689989287 185891692 976836148 919309669 780621778 564528980 541992859 993570421 33011514 221744517 470238832 948953822 205257027 861707237 593363161 640383363 380396752 15213428 212753887 216101126 310044314 143794136 744862575 22881675 606775077 228100425 507531662 955491064 304565609 863269911 86089591 254976466 969112893 581644136 347715429 40710213 415092804 224742168 667710947 454011359 625552921 263090280 62501762 681979805 72993380 476274822 540052924 319879102 918716654 958964442 255686151 285595840 576292993 4802767 754908468 602612646 629188278 672792515 277813239 866409712 807555400 284490915 453027185 666733159 573844365 400053236 712308876 983838834 213310422 32560323 977138055 955364002 248888959 679436305 1479005 32248342 528580973 764018155 673987534 533096278 698898977 17018629 390018197 858146490 664630495 304892331 678758526 43818096 430880190 188760309 821678473 99487935 768872459 722985743 511368508 358196283 986279314 466761042 289006857 346480664 712953867 565828989 756527927 905225819 734093100 886006667 406567927 208643867 168345063 257424658 448072760 183238841 554660601 770874672 654825424 639465648 988338421 998540232 32967991 227991639 346420098 874456498 824864820 417861005 831178813 539720753 951511532 878924585 706857510 648793587 683396522 514732079 831119077 751856461 937650942 529416563 714068394 360413151 772987246 183284238 652514003 6054673 116958117 672831967 466800971 993088700 564224859 3353133 446636679 992729219 859689921 963384941 928542922 138539467 884529842 782849398 71721345 759234849 132495558 699322081 665160009 365821873 662584309 173529260 433807219 426038047 784714278 605651369 265789897 881455290 547857356 93650863 959278074 253329786 803839841 544621709 593139845 644863396 891463292 566677695 19562640 473149788 79610970 314383941 522032276 487501477 907597155 383042048 594281259 576505943 627319819 9740839 493987519 199079104 574049705 71083013 581194469 550636587 538313330 513620096 40828356 990576673 975811895 23625078 939629577 898477409 149295127 563880908 411736285 221293359 347536658 268264960 288631537 140558818 51918439 497291317 575884772 785953082 28633627 292285849 671904789 898973657 600293335 210990015 166720019 97934176 909030255 537219828 948683029 593719222 516414375 101472923 384155138 175977490 714140572 663430771 672984172 243631610 42147595 742121356 477388904 944266716 654340677 451691612 383278113 857294467 841298561 842515212 193755580 489563805 547257825 256581405 940415165 423718277 516416014 596251135 497957628 684121413 510437822 255629197 923733408 568250412 172368487 868712199 941228416 279383331 717463236 348483265 123583462 526090196 932364029 802212197 291417358 303022982 512352736 451985841 853079524 203947311 691966043 323164204 422685231 350659065 385079711 109885034 142705823 749795958 682791008 724399628 7442725 153626550 925306100 790017178 878477947 231341202 609956706 965490535 253360594 625470234 891935198 977144436 597678832 735728036 225982350 584904588 784725090 442367173 962845021 186234025 965759490 446187742 208724859 150048522 780107675 96473346 562171590 318817019 923814871 25730183 122068315 984732608 647263318 276228974 401769366 364166207 118115592 943654738 55466451 508315149 841366996 373945986 18983808 307384099 501496540 217566650 262070846 896762610 914143328 898540168 644628906 248093677 930973691 411749607 745060290 933087525 519139589 580059623 193070309 156276111 176780799 632159464 277919631 853102909 892337662 992700207 30572499 395901166 5087924 688968040 786799187 712158465 277495791 594287669 448576271 132347628 899984052 559500031 371718650 299500422 872056323 182745316 445330587 6212625 549876422 777570100 498262215 909123412 132150933 903855038 502310701 3960279 439279446 399641297 52544459 339459367 694180130 109658643 531112233 284961694 759036427 753890013 19609340 338974957 745639178 563135464 62018723 834829838 376337628 265176731 519057470 340725671 409307848 712331302 47197966 206554460 790468493 267085905 811579651 736141204 592616754 15902819 359490285 283793714 841042206 861612371 676207457 126793356 797948331 592080535 182009670 954780754 432541022 567735721 250474466 962624242 589825820 784342691 4286552 820655109 692311166 712038188 24314565 726089150 771388940 589631257 867438784 578630222 788726377 257685593 183406545 353894955 835250246 278730457 833865212 518260080 102055498 42505018 908807043 901491566 922771478 953467231 396214039 648169447 562639834 202556898 557096665 550200433 350994520 231682118 685885972 330963764 749306283 894513306 868896976 932840708 747906895 728458118 893090008 945636339 775512609 298318256 483498815 410940230 974417057 510884131 268477464 19642015 81541476 281019922 73475249 375095042 305360011 243668660 440637704 476908075 998130224 33328721 355535247 859767725 792049156 314208503 554246842 133404695 350243659 452369287 82507003 764791403 335335512 828256240 910418468 338498816 429267444 37258409 876222642 758072821 760830842 1119379 373813296 708166884 377719990 588555073 422208826 497464462 106896461 134363070 800322427 225243458 402651061 58292825 114470646 154502250 411194863 64277394