// 念の為（？）埋め込み解チェック #include using namespace std; using ll = long long; #define TYPE_OF( VAR ) remove_const::type >::type #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define QUIT return 0 #define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT #define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; cin >> VARIABLE_FOR_CHECK_REDUNDANT_INPUT; assert( VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin ); int main() { constexpr const int bound_N = 3000; CIN_ASSERT( N , 3 , bound_N ); CHECK_REDUNDANT_INPUT; constexpr const ll answer[bound_N + 1] = { 0 , 0 , 0 , 1 , 101 , 6376 , 322027 , 14232227 , 575129152 , 827039040 , 701907442 , 277845895 , 576446680 , 98704771 , 581398102 , 562145665 , 170298373 , 244198299 , 981746362 , 75584221 , 195415695 , 814025243 , 474295314 , 8941106 , 49934313 , 160598438 , 815795654 , 449512192 , 648524733 , 189771026 , 813114736 , 765233312 , 549305412 , 535783047 , 720427119 , 481010691 , 316063442 , 32778069 , 235322726 , 100657435 , 494730726 , 777877236 , 228339370 , 664126646 , 235399238 , 821639977 , 193572569 , 740240062 , 837446059 , 984065258 , 2236013 , 103445890 , 881459499 , 762365986 , 729469583 , 764254482 , 913288619 , 176062298 , 302439046 , 908745084 , 379776527 , 730375363 , 131169827 , 518619205 , 751390461 , 997398477 , 261251134 , 152648201 , 48307836 , 126650735 , 137061342 , 537724526 , 997565245 , 845232978 , 886233616 , 378301408 , 275992813 , 72165864 , 443884010 , 859853137 , 613001374 , 209391279 , 835530 , 648384886 , 125484676 , 875428169 , 532728632 , 397043582 , 505319151 , 42384407 , 564084411 , 326173063 , 809849412 , 443193314 , 350803219 , 505498251 , 111171517 , 858743509 , 505273258 , 14000708 , 291304103 , 27640647 , 61476128 , 127248709 , 825527500 , 8511348 , 631909785 , 925426414 , 340002670 , 749112657 , 723209948 , 495286762 , 791076844 , 721359243 , 849135481 , 766623858 , 19449058 , 177283782 , 287132408 , 350678023 , 577128191 , 812946358 , 633987998 , 68659831 , 244837819 , 606488479 , 916302093 , 309278064 , 566408094 , 776307274 , 48740289 , 305867367 , 905333170 , 111994546 , 652378334 , 979752057 , 804517856 , 905331918 , 546679726 , 245067293 , 67185856 , 196966406 , 216634829 , 891091540 , 275182861 , 570597849 , 779121760 , 961212915 , 461901067 , 660133188 , 602859276 , 628813186 , 742001027 , 599771290 , 192412692 , 362065655 , 749039373 , 756161215 , 579039793 , 852613062 , 855858942 , 981257090 , 500793964 , 990381460 , 316844353 , 652347767 , 467544732 , 853197813 , 566856094 , 361963989 , 366777195 , 836893140 , 995307637 , 215306650 , 776014186 , 547421712 , 85640292 , 874540197 , 705646477 , 816801141 , 423942730 , 145487415 , 719790860 , 762752377 , 822706657 , 330887601 , 331649002 , 399126393 , 456997965 , 558437808 , 754797401 , 366192922 , 246460873 , 180122584 , 952338726 , 191946463 , 41707762 , 128863051 , 857066999 , 255524362 , 419167070 , 850070504 , 287013122 , 561650059 , 425015953 , 517456909 , 560169400 , 613124231 , 541110363 , 248376414 , 4511471 , 773081729 , 737488127 , 470666686 , 79469546 , 663406913 , 857484355 , 806799054 , 225313216 , 527101921 , 819079602 , 857936040 , 360073350 , 367706621 , 483564528 , 977253699 , 656844459 , 473778707 , 231372137 , 402692820 , 331816509 , 124017725 , 194073776 , 855359665 , 533531299 , 103049496 , 367880512 , 96180518 , 507263531 , 942777399 , 413240290 , 812921862 , 350037642 , 589367204 , 193398852 , 426324733 , 906723654 , 448752138 , 932408588 , 613774820 , 98237551 , 552421201 , 864244771 , 436880637 , 111608034 , 556969256 , 353447283 , 837608279 , 532685151 , 734195360 , 186854981 , 479624226 , 422675839 , 547297053 , 179717144 , 605847379 , 366267217 , 714826078 , 336877225 , 205915990 , 298985168 , 739435876 , 704265010 , 400742549 , 504541128 , 612138870 , 54368855 , 990897615 , 825098060 , 112853771 , 472190359 , 333027737 , 143633263 , 232463299 , 848941736 , 817926083 , 840062880 , 154691553 , 924783629 , 659156465 , 471954935 , 620242380 , 656565689 , 395103494 , 950930616 , 915848880 , 852654924 , 378801002 , 806906777 , 406719496 , 403981484 , 802033734 , 804606504 , 699497705 , 631009376 , 868401868 , 838330308 , 699800171 , 268571525 , 658880309 , 639617550 , 988236238 , 755776523 , 205486849 , 158667401 , 330209991 , 236986843 , 836750293 , 445666123 , 648394813 , 903222087 , 127767748 , 609142161 , 597815548 , 223617620 , 796952666 , 358033445 , 177705773 , 694141654 , 419266355 , 542589655 , 469838372 , 560124732 , 126470002 , 208513433 , 735465029 , 933706279 , 143968907 , 431283769 , 672240860 , 281125893 , 770719642 , 659167361 , 429453828 , 233349562 , 650982723 , 823089 , 583582488 , 197222301 , 101240488 , 330849325 , 712703310 , 695052652 , 732829351 , 31833251 , 122982253 , 211411192 , 449178323 , 573640945 , 41177280 , 935373421 , 191199686 , 306318149 , 106861182 , 276620110 , 281107380 , 316409515 , 411992037 , 917941007 , 194544559 , 751240321 , 8662263 , 56796515 , 662998379 , 376099716 , 926297891 , 213442226 , 588409487 , 885319613 , 201134633 , 150843079 , 50409897 , 425716649 , 775990419 , 472023344 , 158343285 , 726606994 , 451508611 , 924430738 , 573654266 , 145812825 , 752900511 , 419746533 , 60177625 , 261724565 , 642647139 , 107670976 , 134696786 , 454755185 , 205848381 , 751072537 , 726388607 , 535351161 , 581855658 , 374256937 , 447091044 , 747877788 , 331460128 , 395072367 , 141177197 , 899501674 , 830666735 , 94384262 , 40364058 , 813271978 , 890626760 , 420093867 , 351070190 , 664789696 , 922377170 , 47649282 , 49169108 , 667266156 , 199644559 , 487674462 , 470170023 , 848045155 , 539602668 , 127448338 , 307359130 , 955720186 , 846877284 , 708597804 , 85290056 , 863553690 , 447092952 , 25828122 , 133705655 , 62025000 , 987409557 , 13196396 , 857922291 , 920662566 , 510091385 , 812055968 , 192217741 , 319111779 , 252812176 , 710471802 , 644644987 , 76923046 , 289305908 , 877746215 , 567220171 , 266558076 , 938838144 , 798021246 , 253336966 , 158890606 , 889008278 , 533553505 , 530384731 , 708842909 , 925614849 , 431204510 , 87383269 , 409964491 , 213109408 , 814484600 , 956100305 , 445806646 , 554710544 , 556670220 , 773268868 , 993948282 , 897641236 , 279656564 , 619586906 , 762987207 , 458302067 , 912311851 , 661683430 , 191032321 , 614763226 , 379058058 , 381014265 , 357656796 , 589511449 , 473582870 , 877031849 , 299269143 , 144294609 , 237323539 , 89250527 , 409582503 , 725993827 , 308966077 , 985288864 , 389976449 , 465714501 , 79058297 , 545559775 , 111150345 , 823819485 , 200145396 , 933281162 , 861363201 , 561231444 , 567625430 , 988370840 , 725037055 , 27694663 , 745872163 , 846374124 , 445423867 , 240410824 , 679413977 , 335363327 , 212033731 , 380187766 , 274339277 , 172127116 , 512933087 , 457445920 , 717682278 , 353204342 , 194265569 , 883434411 , 990108654 , 308804855 , 166767112 , 510707750 , 402208540 , 829188501 , 250519624 , 19274390 , 678461466 , 735943330 , 656031722 , 397706533 , 522271420 , 944665598 , 461502755 , 76128232 , 573768685 , 348155143 , 897564116 , 203049694 , 154547307 , 967251933 , 100607986 , 265713006 , 413482225 , 446693306 , 969460304 , 947865674 , 746530118 , 361870177 , 66999121 , 979901070 , 456822385 , 491127877 , 319954804 , 165880719 , 870866191 , 741266415 , 20338179 , 326162793 , 468225370 , 786647649 , 17177237 , 837809503 , 948672877 , 328159835 , 854097618 , 634574936 , 428265485 , 954909744 , 217802930 , 598731759 , 403551322 , 369668674 , 117456101 , 965897566 , 743634908 , 185143269 , 784831794 , 259922566 , 414779634 , 645904013 , 122914828 , 299611571 , 798907922 , 664389141 , 568543153 , 641205375 , 350508042 , 353792900 , 897717219 , 663706889 , 717469405 , 170865928 , 671124852 , 812648041 , 409610711 , 101239759 , 304368130 , 288689721 , 145116267 , 341718989 , 954652170 , 666207838 , 681982655 , 654651349 , 892813049 , 134588050 , 72859819 , 582869826 , 813890551 , 559280182 , 543303170 , 626612092 , 403672939 , 294760212 , 536843540 , 240024316 , 39220159 , 265957667 , 370572623 , 69804636 , 298173241 , 382690243 , 298340872 , 953055831 , 974890249 , 251475323 , 846068845 , 230649367 , 776928535 , 66948455 , 183948966 , 489389530 , 568131973 , 612113318 , 865678670 , 617949229 , 853513164 , 161020178 , 902258493 , 215798402 , 913290213 , 781437402 , 590918356 , 180787 , 598706714 , 123092853 , 854872216 , 385621040 , 576369855 , 137861754 , 957287159 , 137629167 , 384389589 , 806723033 , 533194735 , 21818868 , 166732164 , 940553599 , 163621833 , 962972802 , 632151486 , 544672783 , 703812004 , 315723823 , 980584555 , 67378323 , 445371847 , 412394573 , 726519743 , 666545066 , 492806919 , 845941618 , 602760256 , 770177668 , 676096830 , 604164024 , 947857726 , 847620360 , 884990104 , 259137969 , 433830669 , 807330291 , 374941462 , 167791072 , 428915007 , 364504291 , 483977728 , 302966094 , 432794724 , 456053354 , 484576167 , 817425926 , 111740002 , 693405133 , 248218800 , 587229434 , 340723446 , 482880642 , 563395006 , 904306622 , 99133262 , 29195826 , 697044160 , 447910179 , 950823113 , 341482425 , 260088986 , 486148825 , 527445893 , 397569005 , 798905696 , 60943197 , 407430055 , 688592433 , 633489611 , 138832153 , 301225937 , 160762987 , 952029084 , 776824387 , 56875981 , 773891743 , 342626076 , 41373064 , 25701173 , 146364712 , 875204561 , 723502507 , 468451952 , 339842410 , 546354765 , 525685123 , 367562046 , 256306419 , 341802056 , 407779458 , 294005808 , 508634335 , 91011451 , 87067102 , 928124720 , 186821826 , 671000594 , 592347302 , 860196614 , 908647170 , 23128763 , 317066683 , 526244467 , 92027453 , 81380167 , 566232429 , 725443431 , 590922329 , 17214591 , 531552561 , 331583843 , 146899459 , 557807703 , 282588840 , 171448992 , 437621476 , 810644924 , 801199926 , 643568856 , 196800309 , 879870320 , 407241454 , 846824580 , 529142703 , 530205771 , 754175443 , 115899709 , 417925828 , 645188390 , 916596371 , 179460459 , 849949983 , 371163645 , 995955987 , 473889930 , 173717029 , 95027161 , 113556924 , 531505430 , 697605777 , 40943969 , 883947830 , 923086371 , 845831882 , 861267826 , 865530744 , 54570539 , 965145078 , 103881137 , 730357303 , 611452571 , 639345259 , 301319521 , 282180322 , 445635588 , 243988786 , 528178922 , 512855652 , 233254721 , 197998550 , 105216097 , 987950393 , 108103323 , 149938339 , 142999437 , 987069070 , 311605789 , 784674896 , 300468906 , 189034627 , 277209559 , 469800819 , 37763776 , 396561648 , 843903298 , 738151242 , 528487179 , 905055379 , 697558924 , 810312322 , 167457164 , 108200290 , 828304113 , 949351621 , 489046934 , 17055881 , 844239725 , 198804295 , 665862151 , 385401096 , 749975311 , 593057883 , 927100908 , 91789477 , 877649692 , 157575999 , 169019140 , 807590643 , 911791875 , 757547771 , 609362602 , 937751478 , 971617758 , 646014853 , 439594743 , 23465482 , 732010960 , 342922167 , 201870335 , 27602849 , 533158240 , 561540483 , 668484745 , 825338094 , 6926252 , 629524396 , 601587985 , 579379523 , 117497746 , 334748854 , 768257174 , 421326962 , 99284122 , 326862292 , 292511580 , 818397881 , 375090152 , 58950207 , 118881842 , 229382328 , 197716375 , 494317040 , 321457148 , 574463624 , 813259509 , 261236780 , 936743153 , 5244246 , 222302460 , 336495635 , 845395181 , 927836529 , 895794017 , 755228729 , 593056469 , 548089490 , 451630806 , 372203836 , 627791030 , 419711811 , 613737051 , 191901652 , 624473596 , 557776572 , 41200486 , 579832622 , 531496700 , 218394327 , 291763933 , 112960840 , 423912828 , 260205211 , 605857370 , 79122699 , 448431043 , 406112616 , 171816454 , 50141064 , 415987425 , 280887775 , 356771190 , 577330164 , 652212708 , 48556069 , 885902591 , 357885122 , 618079499 , 523777741 , 447726792 , 933783546 , 424548426 , 919832607 , 719166769 , 949427969 , 507145284 , 703984787 , 787526954 , 411786732 , 176111350 , 819142959 , 858330246 , 93974903 , 858102127 , 353833976 , 870350758 , 704907363 , 409803042 , 612883666 , 164840618 , 530448207 , 476183401 , 239715854 , 269054086 , 993203843 , 500241343 , 930805151 , 862724583 , 310526340 , 101201346 , 937828647 , 974422146 , 201544777 , 519714769 , 662501472 , 502469427 , 497189066 , 191535129 , 320888101 , 591252807 , 972996480 , 764143808 , 70780524 , 659724296 , 220933802 , 754815991 , 913207762 , 453090305 , 208439401 , 65893050 , 510973313 , 843705498 , 980854518 , 812933356 , 492297950 , 264121993 , 307752880 , 824996369 , 661912109 , 401910675 , 261631499 , 942494346 , 802293480 , 364391250 , 879606489 , 753300838 , 262249046 , 437752127 , 693759670 , 772797449 , 306193954 , 878734053 , 144258360 , 490405599 , 691975032 , 580621268 , 373777219 , 529476736 , 883991336 , 871066591 , 670438917 , 37546404 , 160991710 , 648042110 , 736775701 , 622498231 , 487321729 , 149997127 , 582685639 , 318448432 , 394945644 , 283730659 , 335708215 , 27625669 , 882591512 , 313210322 , 332359573 , 742294120 , 891500226 , 903989037 , 247110125 , 637447018 , 33908430 , 866664275 , 737902911 , 664481583 , 879906891 , 543110687 , 787236189 , 394597757 , 460694226 , 960067620 , 508440145 , 984366337 , 215824005 , 489856980 , 275996678 , 468488173 , 24665297 , 34480153 , 379535419 , 675912440 , 166596274 , 789820233 , 304408540 , 123952625 , 914027728 , 238919588 , 82892476 , 302419934 , 83567434 , 324900151 , 37821922 , 46841649 , 218675138 , 460856859 , 341616353 , 766359724 , 146370825 , 521331637 , 213587221 , 198138786 , 369505623 , 204787882 , 713148385 , 981309872 , 17407767 , 303382990 , 261426768 , 755118032 , 819697618 , 731529924 , 909052995 , 722407859 , 472675672 , 120316459 , 565914687 , 563974355 , 222081823 , 210791559 , 716242398 , 432207429 , 866812044 , 345558540 , 420517750 , 162195348 , 606328829 , 665317182 , 137199184 , 269606528 , 261670295 , 490409908 , 913664395 , 932914907 , 297024854 , 690913139 , 982070428 , 339532918 , 472747005 , 683100667 , 523533902 , 915856884 , 698409091 , 138909227 , 495771853 , 675124474 , 903879745 , 758389098 , 112127988 , 634987256 , 26206768 , 417175329 , 594170829 , 866324315 , 356767682 , 781653716 , 726165728 , 263542820 , 365155001 , 320899670 , 388084879 , 792999491 , 139696491 , 739114253 , 549651094 , 161254252 , 953364707 , 643427487 , 436243596 , 491512558 , 890024705 , 821450629 , 29089697 , 409778061 , 79117491 , 190470911 , 150894541 , 867443163 , 828489182 , 232592124 , 72261265 , 547946350 , 984761847 , 334792272 , 516083146 , 929162320 , 265041316 , 34600417 , 932698390 , 828559632 , 33680842 , 542188255 , 551534170 , 410798253 , 747850486 , 121113289 , 567874790 , 677291883 , 20139706 , 679341299 , 925387920 , 986671632 , 515207449 , 538982906 , 959601788 , 169054607 , 205707797 , 73388666 , 566013569 , 372961145 , 576918024 , 566405441 , 524223009 , 67251600 , 994994795 , 62847779 , 12270439 , 99872716 , 630405739 , 956331770 , 975967316 , 467619241 , 594385114 , 743517868 , 648038386 , 437643691 , 945810445 , 520539873 , 391852510 , 818158423 , 620978859 , 331894517 , 295612422 , 889412520 , 384452994 , 799191926 , 803092015 , 567947152 , 768449159 , 760983639 , 129594852 , 802745797 , 356911453 , 542733004 , 896386216 , 91857618 , 432000499 , 788361978 , 579034824 , 990189047 , 217633545 , 528179477 , 355658658 , 594908584 , 494090114 , 565862544 , 517622883 , 465454438 , 738674698 , 640301049 , 564667280 , 677713603 , 824368940 , 82168556 , 541134884 , 792420709 , 326342290 , 220652737 , 688807926 , 44934871 , 721938165 , 975447353 , 932487925 , 859622219 , 775480441 , 205488772 , 969949428 , 783924614 , 347136117 , 633832773 , 451722900 , 670878294 , 267005907 , 711513190 , 369629561 , 961312535 , 996747030 , 351213876 , 835139828 , 80632679 , 35507352 , 423597246 , 738735386 , 737673812 , 303162076 , 508223284 , 487049301 , 333883187 , 369647396 , 415133788 , 26661775 , 992969673 , 968039512 , 31000278 , 622166092 , 22816927 , 604842141 , 953128243 , 581416376 , 223393187 , 245721251 , 796709987 , 563887506 , 736144952 , 800199580 , 499192061 , 897126077 , 222498946 , 822376518 , 169448577 , 984694895 , 803078105 , 321092006 , 549743220 , 665538621 , 658594331 , 576967859 , 602738418 , 516993341 , 328833342 , 966366648 , 442506389 , 728230157 , 291297490 , 908036412 , 783577804 , 700737506 , 681289415 , 994068448 , 330074062 , 688852048 , 300029157 , 634719621 , 102863779 , 718959928 , 143811011 , 420305515 , 61930688 , 146284441 , 952659289 , 361862355 , 846320616 , 941588195 , 307999066 , 257491796 , 693848831 , 701929243 , 121437303 , 731265225 , 636890557 , 270935997 , 911893831 , 661976414 , 872080271 , 657541335 , 142226669 , 514271278 , 972078671 , 793439347 , 583148201 , 811725335 , 133090969 , 625809087 , 87016401 , 281072973 , 190697958 , 545253982 , 789141649 , 502004477 , 755651895 , 831024972 , 326668708 , 122912519 , 715347194 , 723687211 , 665870626 , 349983945 , 464309845 , 568484971 , 559944205 , 202190037 , 344926690 , 525466543 , 587581991 , 627263344 , 41764996 , 519514095 , 946515064 , 279527317 , 594384223 , 765362219 , 747613813 , 385646517 , 228046369 , 235975149 , 363233584 , 609181059 , 962213217 , 137863458 , 990473246 , 414876675 , 789726216 , 932060014 , 128272488 , 527083447 , 553934121 , 996089366 , 768634186 , 831662815 , 33261795 , 338418782 , 240314522 , 720696823 , 226075118 , 814847558 , 626182273 , 705777784 , 499627069 , 967144333 , 221140800 , 225444559 , 355603317 , 747193392 , 555451554 , 936126499 , 112265224 , 378470229 , 666570407 , 521633396 , 28418606 , 922943866 , 374900472 , 302480780 , 913100649 , 984184065 , 630970470 , 50628526 , 359506843 , 576075386 , 739599029 , 451664833 , 527060438 , 606321348 , 504333875 , 175187473 , 836859877 , 450675294 , 570133936 , 617140543 , 494279644 , 210963565 , 198389486 , 68757536 , 522121430 , 176360807 , 693180233 , 904040909 , 283219906 , 91398487 , 127601442 , 236605816 , 401629989 , 624624577 , 207002126 , 30957453 , 904125848 , 972086982 , 505683288 , 371832109 , 451840839 , 878745917 , 430395554 , 147209310 , 430921068 , 139123648 , 401791787 , 535878343 , 841915183 , 74848259 , 506298598 , 469129630 , 863700610 , 79397490 , 635505843 , 130591989 , 438942754 , 267490768 , 69691648 , 471690321 , 410635580 , 308126149 , 830660661 , 461972237 , 896727579 , 808935514 , 35976364 , 954171964 , 674465926 , 106752667 , 197710163 , 782100549 , 708853678 , 772417668 , 906149358 , 889444901 , 751350342 , 97671943 , 311309373 , 588824019 , 35439701 , 913836043 , 498266377 , 520222570 , 364584081 , 728646506 , 784840994 , 515589311 , 444843105 , 963775228 , 94134335 , 217363487 , 475572809 , 496260552 , 762623630 , 63808862 , 115817078 , 875770434 , 215649929 , 455175950 , 40164148 , 773496910 , 823931576 , 386326553 , 789903764 , 408176771 , 150369135 , 220225716 , 755890368 , 740253267 , 900346430 , 644456944 , 455191729 , 240165678 , 182137293 , 263797558 , 163217383 , 447920255 , 858633761 , 219315337 , 237599314 , 2229724 , 473175469 , 658809115 , 698246562 , 509765398 , 236562092 , 955549104 , 870797088 , 714964996 , 765342821 , 471293570 , 463962405 , 451371066 , 962822196 , 437633278 , 268480259 , 175136775 , 88058776 , 314752390 , 937752299 , 665731661 , 194013201 , 399048534 , 177793852 , 220644580 , 858244099 , 196791273 , 135981026 , 943957027 , 158440897 , 170106922 , 171026547 , 657177864 , 281993448 , 865672277 , 766122576 , 862274195 , 536081222 , 466441563 , 830980422 , 825302509 , 881487628 , 831099453 , 419386581 , 29026258 , 797760778 , 798779111 , 529163236 , 393563603 , 768191632 , 484015010 , 652723489 , 845418721 , 508101421 , 97060452 , 28585816 , 631666856 , 262426399 , 966951225 , 832594061 , 390212644 , 78288289 , 81123627 , 836645268 , 704200536 , 459225422 , 211568180 , 419740294 , 933980151 , 634796072 , 946607770 , 735175410 , 664913717 , 288456995 , 905204867 , 633036556 , 329963957 , 451134177 , 535688281 , 808970440 , 322835045 , 689466886 , 556451599 , 521374559 , 954346824 , 427971656 , 11145049 , 829149306 , 622558523 , 238352069 , 902751757 , 434255614 , 552351345 , 657058377 , 407623705 , 357679118 , 699911940 , 83192055 , 4582461 , 454465220 , 879582280 , 746651184 , 313989824 , 338433341 , 410705545 , 765202871 , 126467224 , 660839922 , 342112470 , 903601517 , 630088437 , 370948936 , 225591056 , 99652342 , 857363335 , 391329565 , 488570275 , 97426319 , 567326769 , 177761782 , 614397702 , 898695657 , 817454036 , 816656442 , 500449466 , 778387039 , 652843855 , 641622699 , 775952326 , 221821442 , 684483611 , 491400588 , 804993651 , 121919862 , 510621672 , 525235004 , 301374538 , 298644367 , 240801312 , 774040124 , 388849054 , 91243053 , 657194819 , 444829676 , 125460616 , 150403917 , 136577152 , 901145309 , 996138220 , 626741929 , 32981986 , 400932945 , 461187290 , 347207670 , 481936504 , 52326122 , 934946352 , 570386447 , 127593297 , 69278677 , 570071461 , 729107402 , 873599126 , 345898274 , 483671011 , 465343172 , 922555136 , 516896776 , 414490831 , 924571150 , 394185911 , 274740726 , 412913651 , 84093283 , 217223006 , 360210148 , 269328755 , 394672513 , 901020293 , 566471615 , 718502872 , 251564137 , 928711921 , 145698427 , 479032127 , 874976095 , 26977960 , 586964353 , 1559708 , 870494824 , 197070777 , 90568169 , 786732592 , 356088321 , 213445545 , 545854372 , 504526427 , 841962504 , 386480582 , 885844439 , 764780337 , 128458182 , 47044441 , 330959333 , 36160941 , 108148636 , 50556046 , 394361429 , 443409440 , 625737641 , 514785689 , 189937756 , 586949099 , 428197867 , 331169894 , 789648414 , 362135606 , 332849973 , 869895785 , 38647341 , 179027658 , 140713539 , 240322452 , 390895016 , 643331282 , 416449482 , 616624768 , 30161542 , 75536091 , 724890179 , 560130724 , 891343551 , 44455542 , 66776123 , 563195075 , 631237469 , 212305143 , 511339785 , 189607911 , 588500131 , 736983942 , 808297535 , 150064232 , 545139450 , 141869885 , 609122258 , 917759007 , 349427944 , 870208137 , 702951930 , 830821814 , 718854797 , 597970400 , 316466389 , 532499711 , 811586206 , 100228149 , 31133045 , 323600885 , 181195071 , 220344960 , 916520400 , 62092293 , 621528430 , 337018189 , 728701834 , 274600792 , 450098737 , 544827938 , 512041529 , 768057909 , 310930715 , 816242049 , 584302676 , 882595137 , 366108342 , 615609220 , 672870843 , 409624240 , 715905613 , 656415317 , 544302753 , 872887894 , 601933722 , 75110969 , 944943037 , 929034136 , 754506028 , 719016691 , 504287232 , 354659064 , 607690717 , 631854863 , 980656472 , 743247653 , 51345576 , 97248015 , 658603593 , 485915836 , 858415528 , 765069802 , 100580183 , 41293703 , 544068582 , 991695145 , 430798036 , 94243843 , 718779338 , 901210833 , 6279663 , 607574126 , 409236164 , 41661092 , 351508494 , 334816412 , 437878636 , 216727366 , 516074959 , 117182204 , 516835815 , 566795249 , 339580406 , 842932217 , 6938534 , 790219724 , 396744039 , 264237449 , 255789035 , 162134539 , 689062059 , 956233967 , 665157772 , 123899508 , 880400852 , 662031489 , 792900015 , 935926005 , 600871287 , 536730587 , 269457934 , 355712720 , 911770019 , 121510405 , 447536943 , 314033271 , 279642369 , 726634586 , 467491559 , 383938693 , 845868175 , 203890161 , 760517448 , 661005450 , 162533613 , 463630584 , 449350427 , 663563984 , 881344323 , 575962848 , 557341329 , 406814927 , 180704352 , 560448963 , 827290213 , 873535831 , 387569994 , 940149534 , 419879420 , 359672969 , 718705202 , 285397093 , 74366368 , 205272664 , 639947878 , 113830818 , 876324274 , 204441254 , 981202694 , 316126947 , 857302577 , 768314904 , 360267640 , 577436966 , 972156435 , 267019155 , 917888714 , 956266080 , 46271477 , 190217281 , 782828758 , 114958526 , 954452342 , 462610825 , 297638496 , 370977121 , 409608048 , 208595611 , 573460344 , 866288104 , 874931037 , 714366183 , 94764989 , 894558350 , 664744450 , 600288526 , 532720710 , 828887975 , 66239171 , 625111511 , 490224973 , 496994566 , 114711703 , 18694494 , 216776299 , 884771286 , 906182646 , 734405960 , 369341820 , 800627276 , 298793733 , 738514641 , 30129693 , 515052918 , 675003233 , 326396278 , 456302906 , 276923884 , 705800430 , 737053670 , 780326747 , 882126448 , 176183132 , 555394626 , 156722503 , 535906441 , 802285065 , 283419910 , 151725583 , 253959530 , 427066528 , 549665861 , 986121848 , 665956796 , 319002632 , 937614499 , 313301866 , 136475258 , 297625656 , 545722115 , 84365042 , 984554017 , 719471437 , 153810303 , 91360030 , 872074786 , 211205785 , 216379371 , 364979145 , 136330388 , 674087069 , 685712639 , 244761027 , 472166209 , 932359055 , 18011095 , 486104513 , 101171614 , 828919338 , 361339214 , 909399008 , 928753471 , 561274350 , 851153773 , 268482522 , 51528897 , 358212146 , 499377072 , 168292979 , 598553907 , 193396365 , 414338861 , 504600993 , 627686739 , 913588343 , 640512312 , 385528058 , 777297048 , 739562637 , 393735005 , 46110289 , 258730867 , 168051372 , 813069125 , 237828932 , 92578502 , 946313122 , 975338506 , 859159232 , 118094908 , 223509158 , 78363315 , 677199600 , 671360871 , 559648123 , 98971669 , 308103899 , 692815461 , 644833982 , 410264590 , 440164190 , 20641372 , 816259787 , 535979692 , 32563454 , 679819830 , 914397066 , 962658484 , 711509317 , 862412590 , 94096110 , 782140980 , 344218357 , 302044541 , 45373421 , 637521435 , 648008419 , 582936917 , 695028940 , 35990066 , 335798714 , 139589808 , 207402100 , 893970719 , 880755473 , 130180059 , 140085191 , 972787992 , 727120812 , 43429650 , 257849559 , 629064974 , 96352902 , 403373480 , 194577429 , 304507265 , 762764069 , 344882151 , 454570588 , 982738971 , 67621870 , 386317431 , 122607639 , 566497857 , 366336731 , 732961729 , 313294463 , 693927998 , 300045345 , 46877128 , 46400169 , 638655285 , 279287986 , 866842295 , 500730254 , 568974366 , 323008531 , 622728274 , 565537186 , 482594674 , 689453705 , 126786276 , 902081967 , 328425455 , 913829073 , 769793743 , 423614205 , 294026871 , 192523176 , 632203277 , 860164053 , 115638466 , 970997027 , 708144528 , 860417304 , 717530056 , 804395564 , 529600657 , 616140323 , 956448919 , 44697388 , 626019686 , 437610005 , 384642313 , 222404010 , 699839624 , 769524322 , 145610965 , 909136286 , 963923766 , 189620689 , 897088559 , 22184613 , 489468181 , 234112597 , 296693560 , 456269746 , 138882168 , 675425005 , 189425064 , 57345041 , 879874364 , 584796494 , 658135623 , 330388084 , 166147017 , 868988663 , 793578168 , 433741201 , 247992978 , 192369023 , 53241795 , 592002176 , 822229131 , 949602488 , 372476707 , 702620635 , 512318413 , 95341929 , 545026393 , 887836192 , 219698210 , 346637529 , 529735219 , 618248806 , 44716559 , 581556042 , 662654199 , 7432524 , 520586859 , 441440981 , 249596751 , 45874893 , 516087764 , 435986629 , 525348048 , 22040837 , 842464691 , 639036449 , 275878300 , 777116565 , 345640652 , 663595205 , 524755411 , 389221685 , 923975288 , 195971721 , 525078168 , 121162284 , 172075775 , 395434579 , 479314844 , 427947331 , 750193013 , 635232754 , 122680958 , 224279429 , 822431707 , 715874433 , 712498092 , 428088784 , 480171739 , 592478217 , 192709643 , 102093487 , 25655925 , 71354708 , 840822494 , 108507187 , 66922248 , 297081887 , 379562863 , 431640962 , 148780868 , 320276757 , 14788421 , 260194517 , 653287893 , 189506463 , 945392806 , 836108001 , 244818018 , 340575928 , 414379548 , 15088579 , 596942825 , 417148328 , 381500072 , 668082433 , 282993340 , 943709524 , 326509076 , 791826369 , 502022017 , 205219068 , 314335536 , 632650622 , 770785923 , 876211935 , 768749190 , 943658959 , 491042512 , 911813070 , 901486038 , 78442904 , 148769344 , 325283809 , 307155700 , 177960206 , 652411236 , 914086990 , 675387719 , 174942266 , 359591686 , 527991652 , 47101881 , 586273838 , 194383595 , 185953230 , 311964351 , 785819295 , 839714141 , 48875979 , 724949157 , 565764177 , 703119265 , 630086582 , 835798506 , 193867935 , 970439366 , 58578167 , 780166490 , 942308769 , 980476376 , 101311819 , 714489570 , 500324768 , 809781733 , 746685885 , 748129317 , 345983955 , 70747338 , 631807546 , 526354965 , 587041677 , 824736731 , 592544236 , 158776765 , 819856686 , 236608610 , 966775931 , 474061551 , 338456016 , 930032839 , 436247059 , 706988820 , 649343509 , 383148354 , 393460830 , 589288567 , 266427785 , 193016521 , 577173410 , 662139508 , 321178537 , 923206021 , 486003317 , 740782529 , 929807292 , 463966530 , 912889721 , 641677254 , 54563572 , 349430474 , 74555972 , 815151500 , 437825180 , 22029886 , 511378917 , 388993968 , 878826622 , 869936148 , 134373634 , 219025224 , 665914848 , 6238570 , 994619158 , 864158445 , 605654946 , 234016900 , 296627419 , 232971784 , 713856667 , 150164413 , 506136191 , 569222992 , 297768856 , 852885215 , 432576458 , 256349517 , 218986058 , 206083741 , 14046348 , 178107233 , 126066504 , 3487225 , 565333527 , 808680993 , 630417318 , 788631886 , 18684362 , 681008435 , 684227460 , 19297414 , 523174333 , 300936163 , 163848454 , 711313279 , 284472837 , 513033055 , 154246033 , 464567025 , 325027629 , 401298932 , 75387265 , 356714801 , 514911025 , 63807742 , 812250038 , 351063020 , 198529440 , 133595725 , 510947415 , 476864271 , 318147338 , 380206104 , 259025797 , 191788518 , 129248370 , 282536562 , 586002868 , 701821155 , 304724368 , 805152423 , 122814207 , 173203288 , 652049943 , 84688278 , 615589924 , 874166919 , 1521790 , 171477965 , 590154597 , 133321349 , 303348101 , 541725244 , 918330165 , 326364410 , 862314036 , 58645636 , 85565215 , 677103593 , 8495861 , 198437272 , 173717138 , 358290416 , 942607525 , 291109102 , 277596339 , 851818386 , 571752224 , 235730885 , 73983346 , 66207727 , 573062782 , 180944888 , 649573101 , 843326135 , 206882364 , 142599216 , 54134739 , 6189068 , 145321075 , 563799638 , 15136116 , 954117169 , 234917248 , 852075805 , 88467965 , 5204263 , 149822964 , 661407760 , 832235842 , 748624089 , 984568296 , 636559261 , 882886712 , 332110586 , 855794403 , 113477948 , 330584578 , 280546504 , 559421287 , 313996919 , 650709465 , 557529671 , 317284529 , 772182105 , 441666784 , 30250053 , 336151501 , 42036790 , 813990073 , 945465060 , 113531018 , 730995857 , 990734747 , 462056405 , 826564589 , 473787016 , 761159125 , 512727020 , 515193742 , 224582535 , 448838768 , 273202563 , 990137448 , 637819846 , 87830318 , 270000097 , 713042257 , 47609409 , 620448874 , 404731181 , 404589287 , 799961277 , 642468792 , 658071166 , 685746569 , 478209600 , 570498859 , 879276380 , 968939164 , 134778219 , 140001214 , 700195245 , 74222694 , 661494842 , 403546374 , 889154841 , 35818204 , 877254517 , 860541553 , 952463495 , 796080576 , 336192161 , 15486778 , 361032685 , 699522915 , 101027155 , 584056535 , 786523502 , 591596146 , 367213294 , 126199525 , 662165722 , 701978075 , 959605874 , 840061280 , 885417912 , 502606268 , 563728178 , 110177608 , 74365443 , 750677904 , 240435517 , 459150171 , 772610425 , 531514073 , 601554008 , 517670600 , 186004761 , 799385750 , 547303792 , 614997878 , 691170900 , 190014244 , 119003428 , 715561026 , 267983660 , 718159169 , 524664643 , 787795834 , 48062595 , 475038608 , 696379347 , 313048411 , 185863363 , 34529876 , 761853938 , 217252471 , 938861457 , 572434474 , 558792798 , 867735267 , 781805547 , 875818854 , 140312086 , 289505768 , 73507645 , 764828089 , 32963816 , 66784132 , 699086618 , 852044084 , 393529856 , 57388758 , 930060555 , 760720643 , 260088817 , 638994765 , 503048028 , 269182970 , 280263756 , 276177825 , 663071936 , 919376416 , 106922166 , 250424811 , 508371568 , 705773316 , 857435568 , 380911562 , 435906365 , 847406059 , 994446495 , 448594687 , 731579487 , 961917801 , 324848789 , 260934308 , 73244590 , 388788933 , 750853152 , 928544276 , 722748357 , 716159842 , 57559659 , 443271379 , 147700143 , 151350186 , 355373454 , 834590299 , 642380507 , 735221242 , 407052534 , 285397452 , 221745842 , 286385431 , 836674748 , 456851864 , 627742648 , 324561251 , 818296957 , 413343155 , 717079755 , 709610338 , 206519238 , 25743681 , 824516955 , 355157036 , 424624924 , 118613667 , 160335569 , 904922835 , 174795954 , 543512236 , 928830791 , 813888671 , 701992779 , 665060993 , 152545431 , 85782985 , 17333297 , 65381899 , 729184567 , 199351520 , 73401833 , 295816927 , 482866381 , 809956952 , 887673269 , 266175130 , 56266040 , 328263324 , 426908436 , 173149597 , 421758578 , 137683935 , 457081673 , 313920963 , 729940099 , 775561729 , 142959500 , 131340902 , 168862476 , 887277364 , 645997879 , 860125203 , 134084398 , 214254571 , 685187512 , 544213561 , 639310834 , 32656974 , 716610196 , 262511836 , 271632647 , 162721287 , 260034849 , 351419270 , 26623892 , 571524107 , 841751645 , 878936531 , 38095141 , 16455959 , 675620114 , 182430520 , 535280080 , 927633129 , 619978977 , 590581472 , 575186915 , 308873396 , 855410730 , 317666643 , 814913368 , 461640564 , 187977754 , 948567959 , 508597453 , 5255850 , 965436151 , 416029891 , 402138477 , 716573127 , 685912381 , 56471381 , 173913790 , 688734881 , 244624926 , 952084784 , 702086521 , 1645671 , 138953557 , 272607559 , 709974560 , 508896367 , 526083145 , 285740326 , 508811799 , 289744226 , 997818772 , 5102940 , 939970152 , 947229248 , 420570856 , 122061806 , 959170271 , 289825815 , 358874419 , 918594025 , 254106139 , 76967389 , 43752475 , 543902753 , 157253582 , 387338709 , 657435622 , 231374821 , 747100577 , 347608261 , 592011741 , 529678652 , 288310344 , 689886912 , 463767408 , 177238234 , 590186979 , 142329142 , 974883194 , 683747877 , 875044932 , 442775276 , 3511830 , 813221895 , 53575925 , 505546724 , 624979859 , 574048968 , 747157637 , 729147166 , 952741368 , 620768453 , 210807913 , 268425256 , 556830656 , 760317141 , 14783988 , 204794360 , 526327257 , 66695189 , 90918196 , 708837005 , 254839595 , 646064618 , 391646633 , 538814099 , 732818422 , 359185015 , 609894494 , 60614711 , 584875983 , 636364843 , 11731777 , 392510691 , 444803544 , 117427394 , 500590073 , 596645590 , 212439913 , 136794389 , 616584583 , 203871029 , 772277876 , 995234490 , 932143354 , 863104046 , 719455449 , 796039332 , 171787016 , 121612427 , 462794901 , 777216776 , 334188291 , 904160150 , 921874788 , 450718498 , 342226352 , 959755721 , 960493260 , 407112336 , 854215617 , 453569713 , 463651969 , 787456035 , 772726971 , 839845966 , 558055195 , 810169582 , 106339091 , 597454740 , 10778396 , 182773266 , 578839159 , 894765683 , 775480512 , 859136982 , 179549398 , 160098077 , 62128987 , 217102995 , 598785675 , 951048332 , 733614217 , 424819039 , 237404454 , 770556425 , 501450677 , 873647662 , 189177819 , 554175621 , 370626248 , 651726864 , 573081446 , 909008397 , 63038911 , 218298116 , 59230778 , 53315061 , 73370891 , 614035897 , 868817194 , 991627998 , 697204780 , 440045073 , 967209064 , 712507201 , 427336905 , 483068167 , 538946759 , 482325054 , 318273749 , 150047783 , 181651416 , 930991663 , 218683827 , 350455207 , 41471086 , 304234648 , 211508168 , 142446578 , 485859105 , 716082409 , 218605449 , 550937368 , 645719626 , 224887177 , 704262100 , 211773258 , 909683215 , 942570603 , 793534722 , 663803200 , 740101551 , 492727631 , 18139551 , 790735012 , 794477254 , 826026322 , 613122958 , 481677870 , 487702216 , 614816428 , 254992227 , 193592624 , 373813108 , 810953537 , 914243147 , 697934953 , 849336804 , 53984079 , 11498219 , 460939778 , 930826420 , 484656516 , 343546316 , 830939137 , 277447928 , 559397059 , 12938375 , 889973871 , 868038464 , 766912779 , 432013588 , 293846612 , 542707108 , 947863406 , 894449310 , 512796064 , 913734040 , 461042330 , 884160388 , 720631929 , 207706561 , 700113830 , 45711462 , 441247066 , 680607908 , 319983632 , 18371608 , 263674548 , 802144502 , 291791953 , 19416844 , 525493623 , 984586909 , 683813057 , 719279590 , 901409573 , 140374923 , 586512686 , 680123483 , 962935909 , 859710923 , 797639714 , 692390522 , 6176686 , 530017476 , 870607037 , 146310274 , 434989004 , 64631542 , 393989816 , 417288305 , 190155901 , 973278981 , 320699930 , 723546452 , 722184628 , 993054754 , 371337710 , 24517899 , 635822831 , 780820303 , 908495616 , 194604448 , 202414613 , 511425473 , 920939652 , 926795115 , 579467130 , 756689403 , 774452811 , 475897673 , 332014073 , 516931492 , 422367604 , 474607993 , 546099270 , 618286293 , 536087526 , 691178280 , 358717235 , 86852624 , 281597428 , 74785830 , 101759639 , 538905638 , 2936575 , 631696729 , 56156755 , 77440857 , 128994831 , 236472803 , 484819576 , 34083393 , 23930777 , 267145265 , 366694484 , 132190138 , 690449938 , 588431527 , 575231640 , 933480728 , 219282449 , 522014522 , 198630191 , 415316758 , 352448584 , 816255684 , 945198654 , 109909679 , 831614524 , 784897492 , 979132763 }; RETURN( answer[N] ); }