#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4244) // 最悪をします
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <stack>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#include <numeric>
#include <sstream>
#define BIT(nr) (1UL << (nr))
//#define int long long
//#define ll long long
#define double long double
#define mod 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807	//ない環境用
#define LL_HALFMAX 9223372036854775807 / 2	//ない環境用
#define MIN -(9223372036854775807 / 2)
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define mp make_pair
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }


using namespace std;


signed ans[] = { 0, 0, 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961, 8407925, 12322413, 18059374, 26467299, 38789712, 56849086, 83316385, 122106097, 178955183, 262271568, 384377665, 563332848, 825604416, 209982074, 773314922, 598919331, 808901405, 582216320, 181135644, 990037049, 572253362, 753389006, 743426048, 315679403, 69068402, 812494450, 128173846, 197242248, 9736691, 137910537, 335152785, 344889476, 482800013, 817952798, 162842267, 645642280, 463595071, 626437338, 272079611, 735674682, 362112013, 634191624, 369866299, 731978312, 366169929, 736036228, 468014533, 834184462, 570220683, 38235209, 872419671, 442640347, 480875556, 353295220, 795935567, 276811116, 630106336, 426041896, 702853012, 332959341, 759001237, 461854242, 794813583, 553814813, 15669048, 810482631, 364297437, 379966485, 190449109, 554746546, 934713031, 125162133, 679908679, 614621703, 739783836, 419692508, 34314204, 774098040, 193790541, 228104745, 2202778, 195993319, 424098064, 426300842, 622294161, 46392218, 472693060, 94987214, 141379432, 614072492, 709059706, 850439138, 464511623, 173571322, 24010453, 488522076, 662093398, 686103851, 174625920, 836719318, 522823162, 697449082, 534168393, 56991548, 754440630, 288609016, 345600564, 100041187, 388650203, 734250767, 834291954, 222942150, 957192917, 791484864, 14427007, 971619924, 763104781, 777531788, 749151705, 512256479, 289788260, 38939958, 551196437, 840984697, 879924655, 431121085, 272105775, 152030423, 583151508, 855257283, 7287699, 590439207, 445696483, 452984182, 43423382, 489119865, 942104047, 985527429, 474647287, 416751327, 402278749, 876926036, 293677356, 695956105, 572882134, 866559490, 562515588, 135397715, 1957198, 564472786, 699870501, 701827699, 266300478, 966170979, 667998671, 934299149, 900470121, 568468785, 502767927, 403238041, 971706826, 474474746, 877712787, 849419606, 323894345, 201607125, 51026724, 374921069, 576528194, 627554918, 2475980, 579004174, 206559085, 209035065, 788039239, 994598324, 203633382, 991672621, 986270938, 189904313, 181576927, 167847858, 357752171, 539329098, 707176956, 64929120, 604258218, 311435167, 376364287, 980622505, 292057665, 668421952, 649044450, 941102115, 609524060, 258568503, 199670611, 809194671, 67763167, 267433778, 76628442, 144391609, 411825387, 488453829, 632845438, 44670818, 533124647, 165970078, 210640896, 743765543, 909735621, 120376510, 864142053, 773877667, 894254177, 758396223, 532273883, 426528053, 184924269, 717198152, 143726198, 328650467, 45848612, 189574810, 518225277, 564073889, 753648699, 271873969, 835947858, 589596550, 861470519, 697418370, 287014913, 148485425, 845903795, 132918701, 281404126, 127307914, 260226615, 541630741, 668938655, 929165270, 470796004, 139734652, 68899915, 539695919, 679430571, 748330486, 288026398, 967456969, 715787448, 3813839, 971270808, 687058249, 690872088, 662142889, 349201131, 40073212, 702216101, 51417225, 91490437, 793706538, 845123763, 936614200, 730320731, 575444487, 512058680, 242379404, 817823891, 329882564, 572261968, 390085852, 719968416, 292230377, 682316229, 402284638, 694515015, 376831237, 779115875, 473630883, 850462120, 629577988, 103208864, 953670984, 583248965, 686457829, 640128806, 223377764, 909835593, 549964392, 773342156, 683177742, 233142127, 6484276, 689662018, 922804145, 929288421, 618950432, 541754570, 471042984, 89993409, 631747979, 102790956, 192784365, 824532344, 927323300, 120107658, 944640002, 871963295, 992070953, 936710948, 808674236, 800745182, 737456123, 546130352, 346875527, 84331643, 630461995, 977337522, 61669158, 692131153, 669468668, 731137826, 423268972, 92737633, 823875459, 247144424, 339882057, 163757509, 410901933, 750783990, 914541499, 325443425, 76227408, 990768907, 316212325, 392439733, 383208633, 699420958, 91860684, 475069317, 174490268, 266350952, 741420269, 915910537, 182261482, 923681751, 839592281, 21853756, 945535507, 785127781, 806981537, 752517037, 537644811, 344626341, 97143371, 634788182, 979414523, 76557887, 711346069, 690760585, 767318472, 478664534, 169425112, 936743584, 415408111, 584833223, 521576800, 936984911, 521818127, 43394920, 980379831, 502197951, 545592871, 525972695, 28170639, 573763510, 99736198, 127906837, 701670347, 801406545, 929313382, 630983722, 432390260, 361703635, 992687357, 425077610, 786781245, 779468595, 204546198, 991327443, 770796031, 975342229, 966669665, 737465689, 712807911, 679477569, 416943251, 129751155, 809228724, 226171968, 355923123, 165151840, 391323808, 747246931, 912398771, 303722572, 50969496, 963368267, 267090832, 318060328, 281428588, 548519420, 866579748, 148008329, 696527749, 563107490, 711115819, 407643561, 970751051, 681866863, 89510417, 60261461, 742128324, 831638741, 891900202, 634028519, 465667253, 357567448, 991595967, 457263213, 814830661, 806426621, 263689827, 78520481, 884947102, 148636922, 227157403, 112104498, 260741420, 487898823, 600003321, 860744741, 348643557, 948646878, 809391612, 158035162, 106682033, 916073645, 74108800, 180790833, 96864471, 170973271, 351764104, 448628575, 619601846, 971365950, 419994518, 39596357, 10962300, 430956818, 470553175, 481515475, 912472293, 383025461, 864540936, 777013222, 160038676, 24579605, 801592827, 961631503, 986211108, 787803928, 749435424, 735646525, 523450446, 272885863, 8532381, 531982827, 804868690, 813401071, 345383891, 150252574, 963653645, 309037529, 459290103, 422943741, 731981270, 191271366, 614215107, 346196370, 537467736, 151682836, 497879206, 35346935, 187029771, 684908977, 720255912, 907285683, 592194653, 312450558, 219736234, 811930887, 124381438, 344117672, 156048552, 280429990, 624547662, 780596214, 61026197, 685573859, 466170066, 527196263, 212770115, 678940181, 206136437, 418906552, 97846726, 303983163, 722889715, 820736441, 124719597, 847609312, 668345746, 793065343, 640674648, 309020387, 102085723, 742760371, 51780751, 153866474, 896626845, 948407596, 102274063, 998900908, 947308497, 49582553, 48483454, 995791951, 45374497, 93857951, 89649895, 135024392, 228882343, 318532238, 453556630, 682438973, 971204, 454527834, 136966800, 137938004, 592465838, 729432638, 867370642, 459836473, 189269104, 56639739, 516476212, 705745316, 762385055, 278861260, 984606576, 746991624, 25852877, 10459446, 757451070, 783303947, 793763393, 551214456, 334518396, 128281782, 679496238, 14014627, 142296409, 821792647, 835807274, 978103683, 799896323, 635703590, 613807266, 413703582, 49407165, 663214431, 76918006, 126325171, 789539602, 866457608, 992782779, 782322374, 648779975, 641562747, 423885114, 72665082, 714227829, 138112936, 210778018, 925005847, 63118776, 273896794, 198902634, 262021410, 535918204, 734820838, 996842248, 532760445, 267581276, 264423517, 797183962, 64765231, 329188748, 126372703, 191137934, 520326682, 646699385, 837837319, 358163994, 4863372, 842700691, 200864678, 205728050, 48428734, 249293412, 455021462, 503450196, 752743608, 207765063, 711215259, 463958860, 671723923, 382939175, 846898035, 518621951, 901561126, 748459154, 267081098, 168642217, 917101371, 184182462, 352824679, 269926043, 454108505, 806933184, 76859220, 530967725, 337900902, 414760122, 945727847, 283628742, 698388864, 644116704, 927745446, 626134303, 270251000, 197996439, 824130742, 94381735, 292378174, 116508909, 210890644, 503268818, 619777727, 830668371, 333937182, 953714909, 784383273, 118320448, 72035350, 856418623, 974739071, 46774414, 903193037, 877932101, 924706515, 827899545, 705831639, 630538147, 458437685, 164269317, 794807464, 253245142, 417514459, 212321916, 465567058, 883081517, 95403426, 560970484, 444051994, 539455420, 100425897, 544477891, 83933304, 184359201, 728837092, 812770396, 997129597, 725966682, 538737071, 535866661, 261833336, 800570407, 336437061, 598270397, 398840797, 735277858, 333548248, 732389045, 467666896, 801215144, 533604182, 1271071, 802486215, 336090390, 337361461, 139847669, 475938059, 813299520, 953147189, 429085241, 242384754, 195531936, 624617177, 867001931, 62533860, 687151037, 554152961, 616686821, 303837851, 857990812, 474677626, 778515477, 636506282, 111183901, 889699378, 526205653, 637389554, 527088925, 53294571, 690684125, 217773043, 271067614, 961751739, 179524775, 450592389, 412344121, 591868896, 42461278, 454805399, 46674288, 89135566, 543940965, 590615253, 679750819, 223691777, 814307030, 494057842, 717749619, 532056642, 26114477, 743864096, 275920731, 302035208, 45899297, 321820028, 623855236, 669754533, 991574561, 615429790, 285184316, 276758870, 892188660, 177372969, 454131839, 346320492, 523693461, 977825300, 324145785, 847839246, 825664539, 149810317, 997649563, 823314095, 973124412, 970773968, 794088056, 767212461, 737986422, 532074471, 299286925, 37273340, 569347811, 868634736, 905908076, 475255880, 343890609, 249798678, 725054558, 68945160, 318743838, 43798389, 112743549, 431487387, 475285776, 588029325, 19516705, 494802481, 82831799, 102348504, 597150985, 679982784, 782331288, 379482266, 59465043, 841796331, 221278590, 280743633, 122539957, 343818547, 624562180, 747102137, 90920677, 715482857, 462584987, 553505664, 268988514, 731573501, 285079158, 554067672, 285641166, 570720324, 124787989, 410429155, 981149479, 105937461, 516366616, 497516088, 603453549, 119820158, 617336246, 220789788, 340609946, 957946192, 178735973, 519345919, 477292104, 656028077, 175373989, 652666093, 308694163, 484068152, 136734238, 445428401, 929496553, 66230784, 511659185, 441155731, 507386515, 19045693, 460201424, 967587939, 986633632, 446835049, 414422981, 401056606, 847891655, 262314629, 663371235, 511262883, 773577512, 436948740, 948211623, 721789128, 158737861, 106949477, 828738605, 987476466, 94425936, 923164541, 910641000, 5066929, 928231470, 838872463, 843939392, 772170855, 611043311, 454982696, 227153544, 838196855, 293179544, 520333088, 358529936, 651709480, 172042561, 530572497, 182281970, 354324531, 884897028, 67178991, 421503522, 306400543, 373579534, 795083056, 101483592, 475063126, 270146175, 371629767, 846692893, 116839061, 488468828, 335161714, 452000775, 940469603, 275631310, 727632085, 668101681, 943732991, 671365069, 339466743, 283199727, 954564796, 294031532, 577231259, 531796048, 825827580, 403058832, 934854880, 760682453, 163741278, 98596151, 859278604, 23019875, 121616026, 980894630, 3914498, 125530524, 106425147, 110339645, 235870169, 342295316, 452634961, 688505130, 30800439, 483435400, 171940523, 202740962, 686176362, 858116885, 60857840, 747034202, 605151080, 666008920, 413043115, 18194188, 684203108, 97246216, 115440404, 799643512, 896889728, 12330125, 811973637, 708863358, 721193483, 533167113, 242030464, 963223947, 496391053, 738421517, 701645457, 198036503, 936458020, 638103470, 836139973, 772597986, 410701449, 246841415, 19439394, 430140843, 676982258, 696421652, 126562488, 803544746, 499966391, 626528879, 430073618, 930040009, 556568881, 986642499, 916682501, 473251375, 459893867, 376576361, 849827736, 309721596, 686297957, 536125686, 845847282, 532145232, 68270911, 914118193, 446263418, 514534329, 428652515, 874915933, 389450255, 818102770, 693018696, 82468944, 900571714, 593590403, 676059347, 576631054, 170221450, 846280797, 422911844, 593133294, 439414084, 862325928, 455459215, 894873299, 757199220, 212658428, 107531720, 864730940, 77389361, 184921081, 49652014, 127041375, 311962456, 361614470, 488655845, 800618301, 162232764, 650888609, 451506903, 613739667, 264628269, 716135172, 329874832, 594503101, 310638266, 640513098, 235016192, 545654458, 186167549, 421183741, 966838199, 153005741, 574189482, 541027674, 694033415, 268222890, 809250564, 503283972, 771506862, 580757419, 84041384, 855548246, 436305658, 520347042, 375895281, 812200939, 332547974, 708443255, 520644187, 853192161, 561635409, 82279589, 935471750, 497107152, 579386741, 514858484, 11965629, 591352370, 106210847, 118176476, 709528846, 815739693, 933916169, 643445008, 459184694, 393100856, 36545857, 495730551, 888831407, 925377264, 421107808, 309939208, 235316465, 656424273, 966363481, 201679939, 858104212, 824467686, 26147618, 884251830, 708719509, 734867127, 619118950, 327838452, 62705572, 681824522, 9662967, 72368539, 754193061, 763856028, 836224567, 590417621, 354273642, 190498202, 780915823, 135189458, 325687660, 106603476, 241792934, 567480594, 674084070, 915877004, 483357591, 157441654, 73318651, 556676242, 714117896, 787436547, 344112782, 58230671, 845667218, 189779993, 248010664, 93677875, 283457868, 531468532, 625146407, 908604275, 440072800, 65219200, 973823475, 413896268, 479115468, 452938936, 866835204, 345950665, 798889601, 665724798, 11675456, 810565057, 476289848, 487965304, 298530354, 774820202, 262785499, 561315853, 336136048, 598921547, 160237393, 496373441, 95294981, 255532374, 751905815, 847200796, 102733163, 854638978, 701839767, 804572930, 659211901, 361051661, 165624584, 824836485, 185888139, 351512723, 176349201, 362237340, 713750063, 890099264, 252336597, 966086660, 856185917, 108522507, 74609160, 930795077, 39317577, 113926737, 44721807, 84039384, 197966121, 242687928, 326727312, 524693433, 767381361, 94108666, 618802099, 386183453, 480292119, 99094211, 485277664, 965569783, 64663987, 549941651, 515511427, 580175414, 130117058, 645628485, 225803892, 355920950, 1549428, 227353320, 583274270, 584823698, 812177018, 395451281, 980274979, 792451990, 187903264, 168178236, 960630226, 148533483, 316711719, 277341938, 425875421, 742587140, 19929071, 445804492, 188391625, 208320696, 654125188, 842516813, 50837502, 704962690, 547479496, 598316998, 303279681, 850759177, 449076168, 752355849, 603115019, 52191180, 804547029, 407662041, 459853221, 264400243, 672062284, 131915498, 396315741, 68378018, 200293516, 596609257, 664987275, 865280791, 461890041, 126877309, 992158100, 454048134, 580925443, 573083536, 27131663, 608057106, 181140635, 208272298, 816329404, 997470039, 205742330, 22071727, 19541759, 225284089, 247355816, 266897575, 492181664, 739537480, 6435048, 498616712, 238154185, 244589233, 743205945, 981360130, 225949356, 969155301, 950515424, 176464773, 145620067, 96135484, 272600257, 418220324, 514355808, 786956065, 205176382, 719532190, 506488248, 711664630, 431196813, 937685061, 649349684, 80546490, 18231544, 667581228, 748127718, 766359262, 433940483, 182068194, 948427456, 382367932, 564436126, 512863575, 895231507, 459667626, 972531201, 867762701, 327430320, 299961514, 167724208, 495154528, 795116042, 962840250, 457994771, 253110806, 215951049, 673945820, 927056626, 143007668, 816953488, 744010107, 887017775, 703971256, 447981356, 334999124, 38970373, 486951729, 821950853, 860921226, 347872948, 169823794, 30745013, 378617961, 548441755, 579186768, 957804729, 506246477, 85433238, 43237960, 549484437, 634917675, 678155635, 227640065, 862557740, 540713368, 768353433, 630911166, 171624527, 939977960, 570889119, 742513646, 682491599, 253380711, 995894357, 678385949, 931766660, 927661010, 606046952, 537813605, 465474608, 71521553, 609335158, 74809759, 146331312, 755666470, 830476229, 976807541, 732474004, 562950226, 539757760, 272231757, 835181983, 374939736, 647171493, 482353469, 857293205, 504464691, 986818160, 844111358, 348576042, 335394195, 179505546, 528081588, 863475783, 42981322, 571062910, 434538686, 477520008, 48582911, 483121597, 960641605, 9224509, 492346106, 452987704, 462212213, 954558319, 407546016, 869758229, 824316541, 231862550, 101620772, 925937313, 157799856, 259420628, 185357934, 343157790, 602578418, 787936352, 131094135, 733672553, 521608898, 652703033, 386375579, 907984477, 560687503, 947063082, 855047552, 415735048, 362798123, 217845668, 633580716, 996378839, 214224500, 847805216, 844184048, 58408541, 906213757, 750397798, 808806339, 715020089, 465417880, 274224212, 989244301, 454662174, 728886386, 718130680, 172792847, 901679233, 619809906, 792602753, 694281979, 314091878, 106694624, 800976603, 115068474, 221763098, 22739694, 137808168, 359571266, 382310960, 520119128, 879690394, 262001347, 782120475, 661810862, 923812209, 705932677, 367743532, 291555734, 997488411, 365231936, 656787670, 654276074, 19508003, 676295673, 330571740, 350079743, 26375409, 356947149, 707026892, 733402301, 90349443, 797376335, 530778629, 621128072, 418504400, 949283029, 570411094, 988915494, 938198516, 508609603, 497525090, 435723599, 944333202, 441858285, 877581884, 821915079, 263773357, 141355234, 963270313, 227043663, 368398897, 331669203, 558712866, 927111763, 258780959, 817493825, 744605581, 3386533, 820880358, 565485932, 568872465, 389752816, 955238748, 524111206, 913864022, 869102763, 393213962, 307077977, 176180733, 569394695, 876472672, 52653398, 622048093, 498520758, 551174156, 173222242, 671743000, 222917149, 396139391, 67882384, 290799533, 686938924, 754821308, 45620834, 732559758, 487381059, 533001893, 265561644, 752942703, 285944589, 551506233, 304448929, 590393518, 141899744, 446348673, 36742184, 178641928, 624990601, 661732785, 840374713, 465365307, 127098085, 967472798, 432838098, 559936183, 527408974, 960247072, 520183248, 47592215, 7839280, 528022528, 575614743, 583454023, 111476544, 687091287, 270545303, 382021847, 69113127, 339658430, 721680277, 790793404, 130451827, 852132104, 642925501, 773377328, 625509425, 268434919, 41812240, 667321665, 935756584, 977568824, 644890482, 580647059, 558215876, 203106351, 783753410, 341969279, 545075630, 328829033, 670798312, 215873935, 544702968, 215501273, 431375208, 976078176, 191579442, 622954650, 599032819, 790612261, 413566904, 12599716, 803211977, 216778874, 229378590, 32590560, 249369434, 478748024, 511338584, 760708018, 239456035, 750794619, 511502630, 750958665, 501753277, 13255900, 764214565, 265967835, 279223735, 43438293, 309406128, 588629863, 632068156, 941474284, 530104140, 162172289, 103646566, 633750706, 795922995, 899569561, 533320260, 329243248, 228812802, 762133062, 91376303, 320189105, 82322160, 173698463, 493887568, 576209728, 749908191, 243795752, 820005480, 569913664, 813709416, 633714889, 203628546, 17337955, 651052844, 854681390, 872019345, 523072182, 377753565, 249772903, 772845085, 150598643, 400371546, 173216624, 323815267, 724186813, 897403437, 221218697, 945405510, 842808940, 64027630, 9433133, 852242073, 916269703, 925702836, 777944902, 694214598, 619917427, 397862322, 92076913, 711994340, 109856655, 201933568, 913927908, 23784556, 225718124, 139646025, 163430581, 389148705, 528794730, 692225311, 81374009, 610168739, 302394043, 383768052, 993936791, 296330827, 680098879, 674035663, 970366490, 650465362, 324501018, 294867501, 945332863, 269833874, 564701375, 510034231, 779868105, 344569473, 854603704, 634471802, 979041275, 833644972, 468116767, 447158035, 280803000, 748919767, 196077795, 476880795, 225800555, 421878350, 898759145, 124559693, 546438043, 445197181, 569756874, 116194910, 561392091, 131148958, 247343868, 808735959, 939884917, 187228778, 995964737, 935849647, 123078418, 119043148, 54892788, 177971206, 297014354, 351907142, 529878348, 826892702, 178799837, 708678185, 535570880, 714370717, 423048895, 958619775, 672990485, 96039373, 54659141, 727649626, 823688999, 878348140, 605997759, 429686751, 308034884, 914032643, 343719387, 651754271, 565786907, 909506294, 561260558, 127047458, 36553745, 597814303, 724861761, 761415506, 359229802, 84091556, 845507062, 204736857, 288828413, 134335468, 339072325, 627900738, 762236206, 101308524, 729209262, 491445461, 592753985, 321963240, 813408701, 406162679, 728125919, 541534613, 947697292, 675823204, 217357810, 165055095, 840878299, 58236102, 223291197, 64169489, 122405591, 345696788, 409866277, 532271868, 877968656, 287834926, 820106794, 698075443, 985910369, 806017156, 504092592, 490002954, 296020103, 800112695, 290115642, 586135745, 386248433, 676364075, 262499813, 648748246, 325112314, 587612127, 236360366, 561472680, 149084800, 385445166, 946917846, 96002639, 481447805, 428365644, 524368283, 5816081, 434181725, 958550008, 964366089, 398547807, 357097808, 321463890, 720011697, 77109498, 398573388, 118585078, 195694576, 594267964, 712853042, 908547618, 502815575, 215668610, 124216221, 627031796, 842700406, 966916627, 593948416, 436648815, 403565435, 997513851, 434162659, 837728094, 835241938, 269404590, 107132677, 942374615, 211779198, 318911875, 261286483, 473065681, 791977556, 53264032, 526329713, 318307262, 371571294, 897901007, 216208262, 587779556, 485680556, 701888818, 289668367, 775348923, 477237734, 766906101, 542255017, 19492744, 786398845, 328653855, 348146599, 134545437, 463199292, 811345891, 945891328, 409090613, 220436497, 166327818, 575418431, 795854928, 962182746, 537601170, 333456091, 295638830, 833240000, 166696084, 462334914, 295574907, 462270991, 924605905, 220180805, 682451796, 607057694, 827238499, 509690288, 116747975, 943986474, 453676755, 570424730, 514411197, 968087952, 538512675, 52923865, 21011810, 559524485, 612448350, 633460160, 192984638, 805432988, 438893141, 631877779, 437310760, 876203901, 508081673, 945392433, 821596327, 329677993, 275070419, 96666739, 426344732, 701415151, 798081890, 224426615, 925841766, 723923649, 948350264, 874192023, 598115665, 546465922, 420657938, 18773596, 565239518, 985897456, 4671045, 569910563, 555808012, 560479057, 130389613, 686197625, 246676675, 377066288, 63263906, 309940581, 687006869, 750270775, 60211349, 747218218, 497488986, 557700335, 304918546, 802407532, 360107860, 665026406, 467433931, 827541791, 492568190, 960002121, 787543905, 280112088, 240114202, 27658100, 307770188, 547884390, 575542490, 883312678};

signed main() {
	int S;
	scanf("%d", &S);

	printf("%d\n", ans[S - 1]);

	return 0;
}


Measured memory_bytes: 3820