142857144 287878790 448529415 818181824 806267812 909274200 114114115 209059235 200740057 996229268 984962413 914859869 986883770 116197184 652084762 40951521 230954292 597945537 900343649 721607460 274731090 112129988 790450934 192792306 344331961 835183906 614426797 736989317 475258600 744597426 182100279 387853695 649664531 386848908 613251160 815797468 171698006 249181939 645602408 274321464 707471512 665071989 28844513 821695004 146660950 336356175 487663595 2811975 487640305 404951625 354571987 145857098 166089382 785353815 3557788 351631713 750566512 593724996 944307951 132538339 561239918 273744746 434652401 562450421 112399393 593036804 333898547 77789783 557195453 150365839 178075726 769241370 929482891 931179904 391895708 6609776 612724429 660538133 659160883 532474787 657762559 788474718 141117876 885017624 681641768 292440064 67558206 895106767 953110429 533926578 417290494 111192496 739566777 868841994 268749011 908661940 215386047 901669074 457324596 834108681 839324561 738204812 847225352 935336561 958131622 68568314 605269745 796011219 738882086 988933172 743758320 934293750 854843239 838370917 366936263 640399600 372903236 202365438 87855385 781626420 688523882 3514008 217200953 354401937 635079571 393673898 425273741 775642620 576727075 992597521 59806215 449602592 82098591 779047802 486850274 659298690 161648441 786139721 219627634 637587334 798518263 698055442 552161010 246714130 578982274 671985383 766444463 886959786 243547920 487920365 262600213 207487042 538240274 338242511 878716720 669189286 538806500 229542583 90944056 871195924 221388 527989532 409868724 425002448 965478076 832341138 982970630 424765792 57979631 239113886 185432776 390933763 362298923 700620930 188495443 354027198 693727562 262674077 535475398 579287369 869749879 721264954 453857989 617411052 319444738 814023876 986764458 526462569 331582322 128836078 142246299 427021838 271084507 949441209 434283608 290347563 842598821 490464588 432546639 905734990 98530960 229872589 285345971 748642505 787169433 785346136 512869396 324754179 24670323 231637081 359278693 333951024 763127499 890005511 226776156 569234009 572289967 945563609 365149814 92728769 221908586 381426095 982110948 974120707 515490129 380174213 41027166 655180040 299599382 84939727 395564238 605092949 280470223 724862510 761991463 316474469 776329011 590182807 88037821 426333577 578764563 242656018 84439736 724338538 560624134 693925596 139106253 478342621 522184225 306273833 172263352 354510736 443172229 574525337 737914347 152021445 161295937 705056205 161817 853731804 569471023 648184457 35740250 995759191 892290422 296718584 944293917 786206220 767301951 345123492 108240241 232567400 865676092 276496909 968232261 932251956 702479533 370320908 462710724 941253503 676797889 952382441 665793497 211715766 693376885 101613710 738586080 43137327 133457787 624359950 140571852 730172825 153457931 529121904 976692306 907265313 874686047 617399666 668438486 670724626 441721725 567465574 909124911 69381701 602960606 88289366 9772826 316760810 951347647 350436535 161017580 447784960 727527612 366652740 139299384 598952003 643709018 362593138 896717379 54151549 898674160 932836908 258178881 524609571 83345241 802762205 585278101 941464207 28411317 826204830 582476921 95021268 88301188 543737244 32290017 599064459 317245620 468343046 902747363 823550955 266035106 375771536 866182552 246819876 459096582 478480984 924548131 916651231 869621042 590212642 220287741 342210889 171540532 63453330 434952119 918352538 524371303 992059137 912660677 275032186 995575231 93953069 180168212 337763297 228964224 460450064 761232146 691629501 223571827 697918823 326416358 199725153 607338726 682980106 521809860 171507006 625200840 420083228 661639858 553160635 657076628 757197928 263508681 97526599 220991961 244048559 36445556 316455947 369986558 497992311 15990002 364834458 776215496 644086212 979032156 582484668 284087254 842482442 415445817 489785081 525987065 626569281 876014203 192164764 503371322 215146045 850838087 900937257 598974447 382051548 267949057 352018059 999991577 285106986 322287502 301681055 524601231 742011430 968056882 626236616 747898184 467059723 870365300 975216648 416186462 510636344 905129708 777626890 143405199 629622001 52985362 732056934 634707386 935336728 478214762 6576672 778470557 350911745 423010185 291851489 685992526 362461491 991177469 341334316 38796507 571452846 294661345 34145901 789872403 389932482 2787231 815225775 488127950 569157740 407323023 126095195 210794706 849448451 317531277 219723153 625553065 648271997 919588868 156722077 784551687 719524602 149172632 511531530 525275600 977546470 705382880 362593387 18117887 479050546 978171853 488102181 293615426 117804155 579829549 316171345 853486702 867172852 912783902 550094126 257685337 249342716 717460637 374645066 707604992 492617459 448807439 593461084 572142389 623503519 258015750 492580034 269996421 293951647 188415844 13908106 403031451 135265026 444645097 522418351 89795373 935110794 818976939 699665073 794270239 385435243 80241236 967615482 762041821 390209197 540813748 140018326 485010576 823365609 114487916 177840606 560632412 900561185 525762514 906235246 594325265 2869978 61593997 670526590 159402922 286668057 254363334 187888276 119804699 554189547 760991187 913159726 619224804 478435082 491096276 980672242 83200026 323300192 715154628 359619756 507517153 838182138 601674694 652090754 70445121 448613034 446854112 393984856 183674916 506270889 192076953 656613861 391407293 941840542 624620293 808915757 766706851 558134249 884729893 41528669 884924745 644956120 299994086 322944590 3451501 550202118 378555205 610271735 406145834 219872582 859917253 961253003 583072112 998562580 307958130 682363153 404944188 798515536 519134560 216402924 233417583 797329256 622002103 39482818 824093501 438423109 805861467 121549991 657209757 256299683 906913584 280824837 482184132 714684388 434569419 994802317 41942277 354305795 464247253 917370822 190367985 661902866 501511229 152400430 983972488 307322269 392906507 874421496 949351211 651754192 363676899 142790557 485501157 330623316 789044000 853765903 211106095 672656901 160396650 980184252 120256140 344102544 252454251 206437073 581402569 968750762 792679520 351786211 551569101 404329235 867661861 837916880 744821590 451186140 67259552 884769971 581512568 538709949 473838458 882874092 858261947 541920822 649735201 536893039 433602204 763951716 604138209 362628138 316860080 210790874 952098903 874399560 765590712 399006203 216834370 90711275 299863479 518720540 73243332 679118946 152496901 311062584 836393642 850420520 607932883 431478976 61454496 914465918 26090144 249487730 892711645 604387832 196489794 861975275 245495837 584232155 811363988 1256022 669910543 767903102 159690117 262397252 372761599 50632215 347026638 183549499 497093930 596906259 270904088 146935870 718534395 305903998 662685817 898695326 154033959 645498370 941540282 797888873 274139619 547596392 104940239 532356357 270929043 195053956 550408816 725598333 620522664 749179817 258716211 494490899 947136791 657933627 966818432 896629262 875079443 318787075 748661825 907678280 872534082 953553813 933541742 987798571 951972053 873168800 331954324 967961342 126198431 856271351 333521981 724968091 87400934 487247302 223645692 990360296 161888604 622255061 316984497 978218450 474651859 461292281 770075938 226171877 437614139 247166942 755291692 804143350 974589435 570218909 616006521 330464284 856807265 989116454 893090487 113180702 829803525 830546274 631572152 706551813 244777723 695301152 508932396 456924723 825687436 347850620 718913555 686799404 908424308 446140222 884538966 206659742 691262253 701647591 95953084 815931598 928102970 177764748 954917402 686745977 494918959 179006049 652790144 696970741 25581775 449007568 434153577 106111737 357858355 496373721 125856522 117148801 467232870 893510000 426534635 83624152 371268444 361104629 166011528 400273503 490105303 659225916 414432588 799253337 417654538 803568231 381740821 19941087 64481047 5545054 362062606 442101257 563477161 775831793 353382341 193961641 904413678 833651310 997888326 248308966 967858985 78900382 785572852 223930672 345106133 342721228 29981862 439822638 888475977 589889000 822675392 985574396 529689592 818259626 952975630 407063781 94938439 688981380 828206420 401525718 385422880 809404406 439089260 857621357 811169560 488790143 808423585 831488607 145559460 846046196 496094663 531581890 843606671 450603623 471736224 377505382 906132170 466145368 319731618 414104944 461908148 785570213 501276007 588697029 464486057 42544649 19763539 214574681 634646172 37542656 119539994 296539952 848116657 246039625 353236584 645874950 627378089 21585384 523407499 554521863 15012813 986809293 446017851 741973910 608956413 937120050 737805423 157539026 999477963 820397231 421651902 624590538 438237301 558197086 602683876 108651954 319256731 989121532 561308935 468241642 30348886 168245178 60738530 363477122 137895393 483539817 26235638 970104590 970130765 991406381 453036465 149999915 448702928 139983237 209743193 289216159 268538552 881413179 53680419 105314454 595521641 900746893 73522197 230755957 528610611 420512675 801394098 287061023 190994307 377597234 594415142 875465297 928099274 310297358 692244725 564081466 172262263 917615298 433776826 591775151 707301281 998358473 556895271 729490106 27330846 199461949 66771917 756492259 783499971 988526147 464272183 440720896 985642405 328815155 667982599 760994988 640410165 30950532 681183665 404691610 802885964 857307801 45269345 768770628 713602743 989264568 452343744 876595172 870964958 531703957 333906156 895510836 579353831 138060524 731351806 473443475 784795552 673619432 272301915 835340815 226996955 700543026 675033900 654192089 278297474 464845848 713590837 530990871 34579059 25380800 220670604 12688153 506422150 291399492 7168900 468031643 844125857 826704557 256459051 39450892 660538547 66292531 255268303 344046311 122578457 801986617 535392710 189806796 789128698 168240099 1037176 410992511 718204562 976094077 733628105 722923455 267734612 92408753 250952814 911257439 340194164 423282787 598110231 130814807 88998407 776524921 91716832 501730849 508483949 394635504 361026164 732628712 839674888 70331439 920974354 265096609 373680658 677433418 820074879 987821683 771866084 946204823 805414810 897523202 855195409 677860975 504593946 763611991 715830144 867311756 918742271 986143216 273078824 880956082 991082916 659360408 192970675 106685509 565030009 801062080 347885107 401259284 239781497 46047143 438666844 303407102 797207075 511277 66924028 410361043 141115531 913354292 218670595 834759623 509774438 141223717 814996832 112764157 695171840 16224874 778989640 663871606 909633514 674414754 950667835 911836269 483817899 842983365 692362869 184202464 798915552 936308343 320444915 851869080 554998987 877888238 429476217 204531337 546697787 291437802 361175367 72575697 368704057 678971936 334351689 199490226 223002669 167322206 946435100 317337873 29247327 779456076 312330600 365693960 601967386 99786597 10834887 643181395 370726523 883898325 38155048 473605955 761796570 431715335 923624641 312012121 180173850 358265299 379455884 41633444 45612488 124192650 183283001 23278002 592645700 240196475 138828129 684440111 973149646 819266187 650739317 527663822 279999574 788684099 178323483 746830410 819774789 228247787 211560081 383841953 149388783 945335291 144421613 1104531 473037918 933505675 716406291 247839092 516312351 630698270 438630827 129015782 258115492 804340575 186977440 992568715 723730492 956123793 939522121 515170039 796639638 371665643 467696105 485761849 439717768 177228657 503334112 210950493 586092623 149902717 32685219 903199750 616728450 423890545 511341720 781683659 536564709 365416779 118546393 28400474 100894578 991003096 473141665 931550902 790701794 985696402 218227242 997331995 266759843 203430609 608590124 869285620 704476835 810170634 897000674 306781198 579738079 422042642 782493275 205387910 997092722 98422757 765091689 721661748 850746009 44420037 260018463 614826946 618217137 189032342 986796452 476314882 510870930 403169544 351281592 109271925 15853631 909756916 461434518 489079135 389404796 295633061 267895349 583382007 251983447 326610244 461347331 202633271 95363745 335925317 975423486 273159597 596735633 68495450 984830107 361765921 880759786 829538295 182792406 861560061 267240871 795429154 955819360 506419125 59367565 113566710 845278735 407273336 754457658 772068672 424616427 917677345 296561092 471559344 533905336 499028005 328754324 917098697 801940823 209291946 546676133 654233407 452169092 674974292 939836573 148745595 142368403 310785660 931906639 98702647 873836008 30197742 180423948 75755205 432209209 283654125 60538280 13903136 960259962 125880918 248307542 146456573 278649966 3272835 282070878 982621111 878991152 339770532 264436259 837648523 254190088 330169433 954096724 605687414 904797800 964653669 998609094 397165017 138735503 118820374 552562654 694649616 392662412 739917715 881053172 173737573 522734102 39433381 840447397 286650440 894851499 555137789 259663784 980397709 288220258 976008240 582442938 218179782 696759933 223171444 945802220 221309366 451185609 311703817 508774826 965293793 3148792 906023669 644012864 76823972 398807234 473041995 676547501 924212477 901219735 437263 851739388 125644418 658083718 956882585 421390052 63467855 695323927 520403675 719310334 509568525 676881634 414558547 338726005 958655701 455861737 84327194 277575693 373712835 915251185 553046268 58320707 788423494 487417683 518552040 942725646 830676420 201593447 258898743 970736929 563765610 515132609 868909172 87153650 980489228 22690056 828534763 142026639 89879285 805010342 435503273 386139563 59662491 313628107 331531321 743810246 560706511 455667266 425538316 337692005 599749964 620498551 39261070 818005707 219143532 327632958 206501234 672581599 767946035 808566555 507142149 607575835 850420880 380955679 996435352 433574770 270002060 566142690 689159757 683687778 795687788 387738441 929184800 93029081 856817322 739770015 533081353 202783164 91081879 609117532 182017472 374797626 531690333 62418449 204493274 105299070 491607599 801968144 387117462 146178048 768658066 273374433 43656615 840993258 808423625 267840684 49469287 141083412 393641609 681281213 959069349 885816660 943037854 970475061 6014189 667008695 99372931 712463581 733726481 434743888 981467978 141042554 968137431 192087440 377170216 38249853 460890826 989263847 397836182 532363090 362121341 831597887 139068236 186883529 329149290 599083476 149593350 756930654 8362772 500442726 129101979 503096979 880597576 304879113 591291759 434480815 565926606 820010915 627912767 18072512 524457908 439779318 276726235 733364830 141534087 268486767 800358552 26039681 402716420 317372188 683481027 699903446 921579066 309342683 115408421 754185627 310341274 355497032 317096656 324728541 369139529 201812415 790935352 718645575 276840400 354255303 290769542 559814789 473010107 805884557 53996244 634641460 677886593 98191166 814797936 39391007 687098964 839757045 442504226 861805576 480607473 930763892 537722013 344990610 991058900 208966399 867838847 132563359 488900364 53390605 906640559 863681642 373807654 45677406 82343025 170774547 956955675 283875726 53619598 167899708 341961246 982888614 483923244 738029157 68647903 252295923 181358914 987227453 995942434 46011329 491243650 651939438 954392004 122643651 882745767 876069731 561542090 202878441 907904527 154623806 296189990 589858375 321066648 289561371 939743124 335994884 296363887 379217637 547400105 154646341 921433488 855708791 667440868 717974769 34142724 450324931 514404277 177495925 935819974 171107549 408866206 207989103 778521511 782193673 67256913 814607732 330157679 445581477 936459926 569187308 417363255 418266692 829475260 374886263 75409224 72126389 437165552 114865899 17120903 640158819 911394881 168090149 190046860 62344303 817484044 646863788 469282400 478581800 457592973 463613795 914439546 956791070 14809714 451293083 188712876 601315511 508040158 247431681 575516739 185479580 815163112 230436103 778908453 720297518 910477494 308961824 891574820 630158276 879629698 17620149 631484728 959654899 359665427 149406300 471296889 446319458 416692581 292655383 863132127 644182772 189644926 632327046 538805230 764221603 247546064 491286613 42961606 62756414 523507442 175894821 663161151 198443709 586043244 595169233 267832034 722381827 219311710 878309159 884359735 64459815 688328550 565297428 76877599 745867980 700903939 198909647 323988163 125444553 590293436 963897129 925600272 330697418 93011907 812857451 421392443 835128844 927954741 13102523 384657665 841079264 139280457 114026423 333520982 788262327 147098401 693590743 577457038 58765567 299233314 706335841 80256133 423847767 639723467 641325070 25659132 313015378 536525450 227932872 90708524 292224359 22181667 527634966 741855780 650594150 253986999 775683724 857978268 33865595 172977098 908435969 603017175 759453733 115114078 390968904 846446631 38792673 742522567 761497642 804932450 261322481 297324348 273549129 406132316 888134883 466121667 826425505 471535706 28991638 771802801 157737473 160614259 731889037 270217210 306648845 171242644 912439633 288574900 625674605 636341094 545193311 570755673 787835242 266257492 659027791 53734205 112196707 490923368 435786673 436026899 991324205 826738735 243608225 506887542 839596757 445104006 839015208 777923979 417453706 619289880 753458970 165925441 505453474 379792243 448416428 356427336 805926422 834492932 809635781 518003076 13790696 16081455 39531361 343893188 829009888 934184979 60498512 599875104 166614405 55667648 887829302 703241288 938455227 182105578 148109169 48814717 864006733 793650897 546306836 80624818 507517067 928467141 802613686 774479468 426738504 737516258 149907484 606325860 595697407 856730336 139537578 13702977 220023464 128319656 523857011 221867375 932903862 954220999 867083966 964841788 827885162 339787386 604567896 49053379 635466189 15656468 607078461 803177383 426725509 73262661 311406032 508659809 988469026 516180931 560820102 750402866 781366928 231767265 463887436 186092103 828439154 293050388 148852870 140018560 704296299 737052063 327456641 32500875 22029069 725765100 561326816 277586959 964318561 149381800 174598623 385707610 167723941 558188358 268214615 489508125 311812597 231578873 621469688 407123889 672894001 901048223 539871951 469730907 827044086 737918800 217584018 757665222 53653345 839299684 437817999 564115448 887426157 881877904 569094321 330741210 839150367 436230832 973727813 296522795 114068727 161424166 231500015 505789973 994546286 226255008 339120093 86498614 141257030 989613849 950726243 124010605 943391429 248149908 229247706 148511426 24474307 753225810 764693994 376503581 369709245 297032873 314677502 593102927 326216376 529794879 513205905 566647448 635124159 148963686 747043122 132627875 275908170 821851425 864728240 616202718 315637315 157167058 457390397 328940146 387346959 708504642 858275851 507161779 683929796 591922700 279583998 298565922 75900855 384082587 823385706 351454039 352511496 8364784 101486078 323289632 181054944 347803861 452904819 359001041 958492090 360263751 796742558 419872595 511218849 988376801 696091626 950928973 729913659 281357236 26551826 821762790 853622480 926371524 509487137 605335374 493606655 752332960 826872047 896074916 521050767 429125558 895259976 982976685 372422409 993134922 828389120 198088296 254890590 938630046 73983835 406192140 685268647 273809805 360323626 250515817 328779607 379211735 445741741 335617395 700981222 610234661 197354744 516970653 156699820 8796314 918616923 942949257 966974415 839829702 180507804 249494723 489642243 265335301 260665082 921661173 855074775 982748175 127967345 429526304 186299630 624848264 299647665 636405022 440050034 624311533 800200952 814424472 473443477 711821717 241385203 691548501 215023757 900582072 139882748 829579357 649937704 902128257 339629394 181589729 7635682 707461470 489917285 362996831