#!/usr/bin/env python3 print(dict(enumerate(map(int, ''' -1 1 2 7 44 366 3747 45228 630312 9953064 175687524 423979368 54676675 623084808 979843860 206550461 727203573 748572526 892708980 66690477 839692840 210114936 268182417 333496097 211122107 312612316 127503277 806259773 909104373 288131729 23186819 757701040 691908757 84043504 912445188 196796726 63183211 537658555 167930691 474863932 832142813 331203079 102380965 590957020 869242301 794063866 7092126 814625624 222749982 163779870 157679864 228382029 638365736 588097170 195650618 191860470 416685569 572382993 319416250 739989190 84039820 497608319 296171912 647666921 727128287 984502016 416717460 148215444 493244175 438960809 303204862 609161266 421785418 619664903 663813217 279834550 705847304 701631447 260361469 746042549 687518042 644227267 651851842 471361210 925793286 592802745 837113559 12032344 948708480 49745207 116252466 481673192 725682676 254798072 705547154 603129711 205539474 316484667 444170718 845193459 35646100 619906792 370815558 540625170 638563380 934526607 459942330 356480452 451289505 179222514 300361925 516884000 909401854 159808360 586938877 204386784 762528284 250251523 733148485 23905194 352066133 208189998 907389249 848679765 302691619 481587481 438906610 480339975 458999631 226927430 477026440 432607466 987302403 248576180 253731738 747263932 666728583 524772295 57033301 939196183 858540923 136069568 781048477 99429079 567678471 494343462 13513410 657362208 656906211 815067302 631661817 377773971 694182321 236176184 827490560 741401325 586878894 137617915 651488565 627922102 218882572 382088885 347211886 185179454 572739509 555313454 718863447 218998742 264200532 726890098 711695754 497134543 969547257 716132187 237201567 882123295 995491645 25942911 540669177 595715934 795850372 998158650 87584248 268650126 268679967 194562025 791767165 841098466 200827174 784143630 146540655 952537656 124518354 901155531 751355536 939439920 735213420 981897177 138931087 218596536 601655048 486985559 1157878 802699078 389096225 691037796 927105936 831932286 890577074 86130267 202186391 156150384 644628698 956950732 944547494 146222600 504539991 443912343 764023794 715073451 781622272 481738521 11318478 992889513 990616485 727108103 137047196 583265007 844326238 616343265 897022188 984341960 319503342 51335996 109805315 936431123 814555711 379664552 301729722 911720315 903220658 975096604 706720986 277698618 149568940 280821783 781318997 850994140 390509138 813232272 262551071 298947651 493816981 926272583 305618414 634931431 871104352 596397839 877159448 649979854 664773590 808303445 590572265 220492042 507607376 339644637 626736591 868732155 572731439 305666597 578502118 871855628 146715458 359110752 698250641 155517226 785692758 276858740 669874579 459034566 36287030 490136993 555857778 905926538 794737296 156325325 200494198 327909073 249124866 421852103 606545733 562634410 416575030 780066233 921439149 461472561 596810919 510805874 750195263 984110895 492662117 402593793 83228494 9313974 994095123 784933359 900912259 379950544 275448298 464786566 272818192 273523056 755646954 714359292 526867484 477590764 541432722 822497811 782242831 844887940 560475080 738753796 618385018 833698102 771262702 528347311 17176189 798774241 709857736 668827267 559772759 515246062 474864554 185591645 153881258 335002293 841971345 599357944 579733016 427781259 506991218 608771807 814359335 984120301 663092625 895372588 746096551 380866841 21587370 288460963 731166298 243636038 704668645 535493895 842924063 335166926 898983887 642178159 944498290 194742297 255448644 660393181 118818579 859768976 70100337 862617440 52166151 749692895 396576699 982640519 958551154 375495369 694124385 646494055 476516980 402881607 263471311 662172441 352013621 343599089 769593717 295823677 972781265 546752057 331347898 516171482 530734151 166517526 27197999 488370622 827100622 762970759 636267745 103934362 325439881 297845705 4590507 793832176 891899984 833248784 344266169 9391494 539734180 282767247 904900416 82479489 264410459 453546955 721832026 188722212 711701696 16568039 638783098 95820099 147322278 921500898 572370033 912700159 944972420 453690750 532259958 854414458 875702943 526331859 581532975 282035062 899342263 342368680 877178337 561382291 679162831 435173137 230412651 679860035 392577949 732145747 455424411 219506020 822134202 589703735 323591668 139757310 734906485 162127137 392424881 126932906 372149200 183360248 546094540 78028616 637377046 419201708 45710668 192422991 188803558 586206890 377543519 136692504 915806266 467799034 405811056 899978202 283193768 675448176 999485529 503148751 126797890 545508541 305999066 391420635 609290655 184459972 528505381 342800158 448912830 415758732 637371230 916538502 417771378 670618492 91232695 539369217 320240370 51253956 72925156 545270090 174885130 846180107 821992190 588839099 486585347 815303157 175719200 212017699 934606787 83198938 912876485 366855402 175394712 839534163 352312845 899158363 630312388 749157590 749131275 305879580 98331879 573725418 124678653 464606619 748710224 365933914 536480508 579511333 873981764 504048107 461079269 678713243 584072458 128199081 898441552 730659183 508175938 691452813 109933538 960235680 476714229 689678483 741647198 851806871 570697091 188203640 554502875 202287862 814375705 537861038 795738922 59366967 334955441 619399734 96329775 953696543 473758236 831789342 397187095 42003836 54123422 630559703 689346452 804357788 730629442 382152791 791666008 911387954 781062666 231777579 488775129 390368292 28370933 846332170 270534951 840573510 786136210 52060807 984464509 608613413 285733655 933009093 160932145 910497 754810697 558487300 374488891 421535385 711496898 575578509 669407352 36344250 486320170 758920171 717561307 664814764 978165367 562506305 787111041 728309781 670448966 552373274 591699889 375471227 231980533 778784670 284796073 130283023 217204002 162375008 500485167 734748096 90293731 557419500 26612636 601056559 817881142 910692861 806990825 455081201 368307932 182764974 761153219 237775277 773162027 453509363 342878698 478883685 95582850 816319627 754502892 787673824 750623251 372569587 325090285 368688022 697924424 270746482 456258314 312510641 852445569 689644924 370907561 450344089 437972179 609616526 557089943 157293232 958926402 530621720 416631140 393255507 427790906 840372629 548369169 458491536 639071344 808156082 433803605 533049775 53428729 735540503 32203795 827175554 444781114 65896942 821293390 611270757 836100229 502439670 708322381 985041372 133844248 150088104 947237550 781230956 911376710 582650776 710758870 329943968 377457781 733702347 813905840 901505190 501541767 53958417 853406226 518091426 303054318 818509229 138042781 481731356 353773254 338302923 81281620 15837503 118691251 950249428 482223044 91383445 384119702 75735604 137533753 453064006 252221710 618761994 688576153 485397663 151931493 214193290 820479406 752273966 494397773 473468743 182357624 679084333 449218629 108295097 949778796 14853590 382140874 465715853 232396436 291172779 479255215 461452508 382222655 949822008 493055008 856021944 759854120 38276780 73435263 236392489 887680923 601603978 973622517 633956246 596602895 97867516 800410835 195533896 316839114 323389109 6995353 636212488 889317443 660551353 794935737 6791909 511617575 177622048 207841751 313641544 578015806 562071495 932929922 159734928 852049568 711760195 602702635 548838077 312507353 909227548 197108370 617177396 258963071 335032997 317456483 405376552 142851387 888245902 140995024 367853341 665723665 142124497 345271414 77714808 510200598 458117330 972642716 320525773 814728350 323993876 451481503 67847705 70049428 881016071 701255524 805586934 911662530 647953026 342094670 344678715 773255040 781037813 46390433 336797954 205570952 215944559 1944020 38412223 907552514 437011602 586349816 783539052 571031107 775430530 336374877 447966746 257374178 584007873 700355747 5208188 112954865 628920399 501986867 695044667 955863004 85477079 380655114 584037517 151122009 363791020 104306144 750108053 120814629 618406128 50562990 608973329 303894947 754708390 197451627 128830148 817287654 277670258 412468964 543098425 144882498 811343306 409644810 337251819 154711189 179941323 349409998 51921336 598415392 367635674 344383040 261258994 35312992 661186551 691989994 926563628 743066854 162896737 299126252 552249286 729155404 449539419 796547487 96429215 615667266 429221244 566794886 796280468 594348050 17107778 888511005 591527863 521063530 585396392 977556829 524765641 232158337 900344513 327800538 259638442 556093397 176802103 481264447 333983376 185800436 475257599 779381991 150144728 350538851 192426467 604075827 146714343 657208916 159174225 149270467 541899756 676516667 673037539 499388116 182582344 769951466 521968322 764855162 496946974 653331362 736569417 585650966 334050256 851402090 842702544 628488540 999547597 244651227 268388388 234417781 14455030 532180797 214597478 922804750 802867453 444169199 266269240 75687075 239622867 943484783 414558450 924462226 760276586 411115771 869545317 626753900 946660769 190884318 855792491 800673699 952544227 651416226 154771963 307484981 627653838 756169635 101397144 96679118 232126228 696799527 176960098 230830514 781435121 13321186 373827529 452436880 927953111 728551710 326377176 709967576 295935349 657834682 825522617 96016520 708462798 361336369 715384615 30046958 842757205 42166011 224691960 979995639 414922864 569794283 3615532 740277083 189374625 213013469 652037977 998096536 530128689 472643466 40903033 421108960 92678080 26595446 235677642 515023722 747905451 65935447 951223451 696748173 652531187 137484380 78247583 593262425 856984388 760251735 251132839 478922101 482878005 253171117 232940257 347209047 907768519 864560068 628550109 704087205 546213561 240705971 93508194 386333398 735735949 963230759 35893063 686335956 646037457 512802044 909723436 897832769 82558677 126547426 959723820 873983392 983025803 295050299 500240564 189602503 542183030 49462754 836774246 819351795 357363191 973571116 777075630 919137077 810544625 94991782 537315038 823070763 599066057 78030693 694880041 145936657 17560233 618924690 508565041 898404313 221174762 228024864 451805907 717502923 983094199 512660603 438774469 285276296 252936405 586196772 457451140 528982378 162775265 66009684 542645583 976861506 204423653 65363081 615689546 869655751 510073422 795745251 338644294 260515858 68506082 398598139 611838633 84225544 375729541 219147502 772728864 726865345 790531112 625339116 508124483 654914450 696788097 265486525 842710781 563567880 852417302 805893718 386883927 538338483 792042406 313735170 612860870 819017550 243980347 587731726 160198530 663772213 212273945 194108225 705154065 523199165 642219182 717089585 772906745 455078254 961109702 445500698 731635212 251934467 622458876 53397020 974695277 840098015 566775011 369925147 84087422 437297823 492432405 230516826 270150872 447175559 784083046 764181441 636466951 361031452 215376093 764446577 71882492 944891205 648506894 201712577 470608583 499700412 405348683 640674545 784217555 35310093 833619949 356935623 865841117 811518790 64714276 331850239 741743410 90344706 132609539 551852351 740128356 205561736 578232384 857408482 995714822 644665936 373156467 15994732 375919890 857206823 845463268 868613724 661402665 501746314 190972023 291680225 974776667 255848923 108486139 458758795 185580224 612746469 885197495 774132652 885792576 205946853 643909926 956630812 631467123 798880507 499378834 738015768 271377996 265858612 482358690 96213883 686591070 153147154 606626193 365346823 612327170 346677743 175785604 311272943 148543363 224793695 272174824 409602321 586416194 826300143 77545865 46886903 838912800 584283628 618247973 392150468 745967564 242418867 693315973 38671701 419590601 269479869 334653364 602431280 952430940 355950889 696204876 813218432 935336938 917339285 629658380 578961512 991274864 429987851 39776307 395138365 330622975 658754866 858440623 188712475 674551352 516379609 28815511 110117013 591875477 954761456 732121935 359962622 664816921 481692566 713978138 595073301 931606467 155388386 549706895 775934884 473903037 544363694 860640865 532445432 62282206 365829288 60867546 861653155 110632846 531006732 652201003 985371040 236300707 476137824 277473939 835946534 780981955 647114265 882360023 905064346 73470660 599025053 851085383 449817704 770816949 278559947 298314256 930010626 548233076 269556134 555442732 255514326 124904406 911866646 786782816 173038970 935658839 15703139 856704836 842632566 588119433 481988317 693758721 735201143 664360168 39349078 847297115 849418344 55768033 555784067 201312822 314672887 266229722 684160533 194310752 374042357 282654207 614233991 968977585 250101595 799470155 241326507 798323691 174642076 644170735 526418120 711289954 782473039 30216174 183868555 231455683 692174790 994385082 23791325 964976207 689608637 456456252 407837036 70794471 9053210 204913948 238649993 979143210 182386611 313723126 394218653 240549561 251248202 487022127 244964267 395674225 50367100 684928144 497363024 596512828 743701657 393832204 957916874 533117037 769611659 834242352 506829886 951373385 554501745 893096121 877464183 668562105 140060318 219949337 122196355 403407245 733604766 443315432 288366871 310116398 730617428 796117968 845553633 922082034 254879658 294349164 247602409 820400093 462226760 196338153 241189034 310517725 818021598 868850635 878913333 150459197 967500216 853306741 573667251 402602297 257447612 921611063 429429527 136222753 973124919 764728959 436384786 889718177 649309813 652187173 19373800 636382405 35253098 40755486 88231038 406827427 253672810 655740259 977601738 434969338 170539175 31325791 772041412 966487257 859866024 319522976 549978905 193076792 174259904 769727168 3282902 452765470 15938508 653825646 394312816 535201087 899750067 908536146 916037331 36130530 913802117 161463235 755762306 810496795 429399182 853660622 65143294 286545888 750730232 217261350 786213958 741208396 891619891 69332434 567642831 596942972 870185877 687239542 84107057 87017623 596962070 663687744 524272412 962672728 925945338 731063348 118946568 144249504 57207074 98943257 132483646 743531374 778203803 887943713 114617391 357754364 68901379 617930725 304521681 843887763 744466101 917429474 59811025 317294321 102940990 215166038 85711164 409186854 300783050 728545806 609036128 931217778 972701276 810423120 281837485 857228235 549546086 837520437 324364445 763250459 436964011 204050291 588690245 135589487 495739021 910361947 560106803 763584157 293993446 192751432 839785820 70800861 532371038 886479061 488961967 116610511 761368704 473653020 449879694 498270502 682275797 663533358 288817282 744508796 205750331 745783670 451463239 432396159 709848436 844970413 416995995 706560224 919546093 498863327 678271833 32808569 64368316 317979751 828050575 655922454 422470464 86247018 265412803 962200886 462348858 350751094 675810502 837972675 169839103 477083845 165815942 834061809 488317237 136962674 613234602 414946072 767748458 571768454 830192632 238350343 659811584 341438554 843158649 990674326 402976651 660346944 315293012 246685964 432280342 884300750 119460025 82819466 945078566 969897675 324232301 690947736 177311464 137129733 125299222 483579847 176829938 521059024 492573969 397103920 477267597 698048290 179138622 876270268 934296959 788562640 554310742 385368874 81941816 389380656 555470377 191077606 749430319 667673582 151411149 603759800 502054361 124193854 322630847 845958485 413722949 283416591 116334169 175682739 143538515 868484425 524535063 845615857 934242929 121774151 540936551 835924522 445556874 552325443 394670674 202108381 83854840 376576614 609419076 806580457 386813550 286309093 212451714 557883932 119635989 51977603 425263893 534959979 75043417 94314375 798021428 112749354 156329738 539404616 543182501 358429024 69282759 898837840 287392993 240437172 298161411 893421748 521777193 229284854 451422725 356933320 488434434 498643876 1612794 788137134 836663215 424133041 938303393 495742019 686666177 576627418 874148264 717519780 442095996 180608904 670533674 551454272 663878403 838673330 192654391 23457592 227703807 667951873 120585559 917524777 946109489 213098704 141458577 600524562 842725441 576046330 11324399 889396842 301735925 823365109 489973862 128488355 47772299 789774513 896794666 528738171 509264671 572122675 846697113 581360118 473192231 467749217 359205674 88864817 364906712 346624845 773420569 829750201 613708794 617931331 593043790 944583417 833174565 954488655 36515326 921215688 899544049 143309339 603887913 435878379 133136726 259887809 144534239 21503602 144930661 413347 938403069 917863539 387205643 590037735 144031241 531360641 151851313 785182122 807734849 315808088 356365888 485745243 572643078 869533871 724814647 413958817 489819870 201522052 474851786 995518009 748397308 41390228 721521308 353142510 270855350 267821582 284270010 124677374 706388119 13369902 260215859 485236720 838750504 321484023 612362143 86330894 468569279 566373039 398953887 129622059 848110883 901333677 61952666 476024033 77290266 950118844 335513732 305150358 865688482 584619364 395604995 77985618 19045728 781064180 615047106 324894041 871804971 852541116 679595103 330050331 513396016 852218097 795154367 643163939 275205154 912106314 176534747 578791248 851998764 483193765 115335806 741594469 141577094 565701519 594017822 460424996 117253424 694512570 952803480 783548020 972301667 143365071 165597068 65753951 131145938 432401667 757175898 311708692 154825702 585890337 733156190 143939139 755944626 792176154 731131406 579775447 426344726 732935883 511973769 613410164 894806106 465385018 522056171 142636773 926919053 896874172 614184057 940130178 362588850 225729282 398219691 231598616 615540426 851981898 797371478 820694403 784701317 508067209 35624988 935638977 557163711 215198742 352754719 322529487 38822837 241468827 913759743 442306027 590995455 156832097 445596737 755428696 712498798 206276995 90584329 647039791 206900940 135430005 425758533 719361347 57084565 382142216 776807323 53176603 454567573 595642829 709653379 849773856 462184762 622820990 514582715 974159761 299837004 514657254 67867591 380505209 997569207 172292780 215692757 581313797 74043747 521711664 518186318 126417995 657012262 446121547 479690371 230291829 681877127 82919934 823806459 629614985 196755635 496993909 711830393 656510416 230489294 528574810 734338321 583945134 875085907 484994526 609190435 864966419 111192493 440660349 548902939 870275608 587644577 728272485 255904415 844792201 801672555 578348473 749858842 138627759 933590928 96444884 963120928 565134738 873093907 952600629 71841039 973698982 913144036 942298735 405292172 813616169 248929996 948922912 861020710 378975382 22173622 915716190 695792963 240668937 549884501 873732454 70307526 976411379 758170777 988665232 327591414 299946028 698495876 850891518 369104708 764249454 825079772 629675734 566006762 224754541 858085403 185308642 255126524 95624457 572590467 928907839 171044907 170093082 296586869 963782341 562746992 625169323 169323364 983976226 141557968 339591461 427368141 972198850 93044808 860410799 460910125 208924776 474481629 35580505 970599233 652930535 877821546 411585156 22453677 994439786 225914892 540775000 458478806 594546977 723317161 815625687 858362627 632659130 228513068 696596901 898663025 726286497 825151501 387495029 790191053 138522819 709564518 765508323 570990630 886843144 920976450 55834879 250349366 963792729 537522354 187463767 94266064 249574732 930000127 84565780 529244824 266588253 642513513 680122160 861274764 692395049 662138838 244236260 529613877 705886255 440155617 324990008 985515198 855931590 170745104 964161937 816838334 615823143 175978523 498280522 148907215 687661432 704111464 715985839 256310178 432950011 82376583 722462590 639068744 '''.split())))[int(input())])