Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a trie of all correct bracket sequences of length $2n$.

The definition of correct bracket sequence is as follows:  The empty sequence is a correct bracket sequence,  If $s$ is a correct bracket sequence, then $(\,s\,)$ is a correct bracket sequence,  If $s$ and $t$ are a correct bracket sequence, then $st$ is also a correct bracket sequence. 

For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.

Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie? Since the answer can be quite large, print it modulo $10^9 + 7$.


-----Input-----

The only line contains a single integer $n$ ($1 \le n \le 1000$).


-----Output-----

Print exactly one integer — the size of the maximum matching in the trie. Since the answer can be quite large, print it modulo $10^9 + 7$.


-----Examples-----
Input
1

Output
1

Input
2

Output
3

Input
3

Output
9



-----Note-----

The pictures below illustrate tries in the first two examples (for clarity, the round brackets are replaced with angle brackets). The maximum matching is highlighted with blue. [Image] [Image]

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n=int(input())
mod=10**9+7

ANS=[[0]*(n+1) for i in range(n+1)]

def bra(x,y):
    if ANS[x][y]!=0:
        return ANS[x][y]
    
    if x==y==0:
        ANS[x][y]=0
        return 0

    if (x+y)%2==1:
        A=1
    else:
        A=0

    if x==y:
        ANS[x][y]=A+bra(x-1,y)
        return ANS[x][y]

    elif x==0:
        ANS[x][y]=A+bra(x,y-1)
        return ANS[x][y]
    
    elif y==0:
        ANS[x][y]=A+bra(x-1,y)
        return ANS[x][y]

    elif x<y and x!=0 and y!=0:
        ANS[x][y]=A+bra(x-1,y)+bra(x,y-1)
        return ANS[x][y]

print(bra(n,n)%mod)
    
        
    


import sys

sys.setrecursionlimit(10 ** 9)


def fun(plus, cnt):
    if check[plus][cnt]:
        return check[plus][cnt]
    val = 0
    if plus < n and 2 * n - cnt > plus:
        val += fun(plus + 1, cnt + 1)
    if plus > 0:
        val += fun(plus - 1, cnt + 1)
    check[plus][cnt] = val
    if cnt % 2:
        check[plus][cnt] += 1
    check[plus][cnt] %= (10 ** 9 + 7)
    return check[plus][cnt]


n = int(input())
check = [[0 for _ in range(2 * n + 1)] for _ in range(2 * n + 1)]
print(fun(1, 1) % (10 ** 9 + 7))


l=[1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, 325878, 1174281, 4260282, 15548694, 57048048, 210295326, 778483932, 892818230, 786724318, 347919346, 355845955, 274146173, 336110626, 508416482, 521006399, 214448866, 997593411, 238896999, 849258736, 819525514, 53182350, 202970081, 945166442, 598349475, 683882441, 92894058, 452668785, 75136294, 196675923, 119906583, 942355177, 971081806, 117114980, 360237618, 942712231, 137580544, 313883953, 475793244, 854651725, 734277125, 39095249, 461071198, 801159097, 64968190, 936719156, 886161553, 639551605, 781314451, 681340193, 107129321, 680026807, 103559391, 682186676, 827551267, 510628237, 427135789, 600593159, 542474853, 821284002, 34030966, 212108296, 552111064, 883592263, 580458832, 835540036, 126388564, 22628138, 362655432, 628650076, 577876876, 73283345, 404323915, 228609761, 734246007, 503315696, 474786457, 786621025, 519844441, 126622248, 232121937, 461707459, 964781967, 444174545, 772222316, 418006179, 579943979, 48479441, 255004523, 149519163, 323014184, 89331782, 201498807, 879409500, 313819128, 148656825, 429282108, 581422264, 553214377, 428884534, 304578144, 685949384, 644505805, 93833863, 403784647, 832234244, 508584425, 948278881, 809571136, 445611926, 332423140, 173000195, 714064794, 116628822, 278519688, 676662450, 515315037, 125220758, 184190736, 383890856, 480000081, 126650091, 86979910, 808451709, 451630930, 921270058, 473876008, 646769937, 227033671, 276168190, 12697185, 757160642, 202483804, 116943455, 244139682, 934215874, 158452923, 97994528, 209136188, 812513077, 118261019, 434088376, 117384160, 727697141, 837642470, 132655896, 798015392, 775952773, 792922839, 764879931, 726311620, 830066915, 359922043, 952091491, 152210295, 182338426, 39938439, 35128174, 902646636, 209047086, 22725556, 251866406, 43672812, 503078357, 991343096, 653063739, 48339910, 79488094, 410126004, 546619281, 536643008, 15729744, 32641153, 773429140, 351222791, 178118753, 290822158, 209487213, 421501965, 393411119, 48310849, 206064336, 933840113, 383521934, 260247320, 300575894, 258016806, 861961462, 503317518, 289465950, 205742458, 965192988, 860838962, 612930989, 988868236, 692804611, 949808891, 158619989, 178478976, 656318591, 935888274, 594861602, 212504527, 197101944, 488966659, 561894038, 429319218, 452488972, 166318639, 625132009, 902887424, 864420332, 916156275, 98705298, 854694297, 349260433, 494421728, 633282503, 279864836, 243596071, 739349517, 770783447, 238812351, 18320172, 943321855, 747027778, 587801022, 352326238, 384356475, 659969891, 248924879, 943334805, 73371413, 178956400, 233438997, 94556124, 804781642, 113398542, 551897469, 72519241, 82549791, 509896387, 83827011, 356028512, 303296016, 390306785, 657022030, 464371224, 944104658, 343575359, 762229649, 822363169, 245293123, 766640045, 294291853, 133952039, 220290975, 943649890, 321501293, 833289741, 784922366, 405744219, 530715909, 620437844, 11611272, 828525996, 937378965, 458914582, 414889108, 186018763, 749887062, 87989481, 55886074, 736617689, 341197582, 17228846, 617689322, 804101956, 903076775, 98319282, 528089640, 461743124, 782942141, 82422628, 319537334, 88043058, 306801051, 542873338, 87819422, 465447307, 799568629, 975457975, 981268163, 513413366, 277319289, 45482685, 608310648, 333645167, 42492538, 90835075, 316094777, 746062140, 949995418, 171734290, 391028054, 835144212, 738966944, 547487595, 185412017, 176355329, 219911742, 70400092, 387509540, 906481553, 987149700, 500784758, 125325184, 869740064, 999893398, 164984755, 930117545, 657010659, 123257692, 424856034, 552743218, 184931575, 731307947, 64903761, 431470115, 333568319, 713240357, 662663489, 97641445, 370615844, 848298226, 278661556, 826018292, 31838269, 401165432, 281668873, 886207297, 122232045, 417432333, 486737668, 375497685, 766171974, 542002482, 863934476, 77832072, 837135351, 182727912, 883577248, 721401797, 871352722, 96373726, 522425701, 536349386, 630762417, 787392490, 23805397, 507956382, 461503163, 71726115, 618689038, 943008913, 113268710, 312778511, 836482002, 624222414, 878017876, 986936158, 63031877, 316979977, 131631035, 63038786, 355616568, 724661479, 333664142, 181914780, 436447148, 898609769, 663457398, 659379714, 392454251, 12669528, 903992102, 476374148, 316368147, 90392579, 557340517, 448808914, 182133812, 225359668, 808448727, 688086493, 442960289, 683937353, 485963477, 308485073, 890681010, 72684064, 57234135, 774455177, 267805522, 771768761, 6098266, 220366179, 366000794, 793333460, 864455402, 956074672, 664016903, 630673596, 979578951, 419921513, 881083493, 597187057, 856446379, 54047225, 693970948, 873422393, 282886954, 644264998, 860347601, 119895585, 283479471, 519986253, 816523644, 66832216, 543768713, 614816297, 166601192, 320952360, 379348377, 26136448, 197730425, 655766372, 460581382, 207978233, 99021052, 269775043, 74158462, 418326072, 988044944, 307537543, 240660439, 265956167, 465824590, 976630677, 548433887, 549409535, 269926647, 646212242, 471795581, 896022900, 33108198, 309018900, 573413525, 548833238, 728732265, 951572105, 62448659, 703336805, 113031230, 607758383, 137765647, 881099721, 391255515, 901883059, 531248881, 821743512, 596607866, 422243650, 933777784, 242341144, 805390173, 350461238, 830213159, 245094858, 857768048, 218783758, 858028212, 495606600, 608849415, 714459946, 687960612, 948463089, 32682, 795552363, 673396205, 228454570, 133703002, 3112053, 844662262, 721758359, 182280845, 950342575, 796155000, 63689540, 309812047, 438719405, 366111352, 95696826, 296478421, 904956013, 369725313, 357451142, 47733681, 308344913, 320281313, 599344160, 13921921, 663831108, 132574468, 885056263, 840671481, 676169302, 139295812, 258208619, 592157991, 761901575, 142454833, 299702654, 495761523, 888809591, 104549631, 175465462, 292920150, 584499101, 573679842, 128635314, 236383179, 862035230, 110986048, 731804942, 993647432, 746189529, 467216224, 554057120, 517244686, 157592431, 655562353, 620632991, 316630647, 85089599, 3726444, 576285033, 928970336, 380253777, 359525609, 576932584, 341967422, 533436792, 935722398, 122828500, 362006261, 248987300, 817257641, 906273861, 829394369, 526605667, 582661484, 370655577, 882805119, 753297511, 81791288, 316611255, 185264993, 666225844, 813053846, 315572368, 7438708, 101639442, 847352407, 7361464, 455867504, 1163613, 277884625, 695446595, 702659456, 229118130, 888237935, 695612236, 795282452, 158199573, 846044262, 987819716, 345349078, 841539968, 901727083, 709050100, 503739619, 14825889, 878511475, 796673314, 406538115, 902388885, 927775097, 867418048, 50029940, 846478507, 29788443, 361089455, 243429091, 564385190, 101176236, 471093640, 78389731, 61344214, 896237857, 943210382, 748603085, 487617534, 960782037, 280990439, 338839050, 364966819, 897591613, 239205605, 231883826, 888568706, 352895224, 234659531, 202465711, 747150346, 944580974, 623637770, 977244794, 409076311, 644222090, 921930604, 879387216, 132503849, 88740389, 910328654, 202013463, 114078731, 262855538, 504650505, 853619015, 557249827, 859593512, 782879502, 161588334, 290651237, 976886584, 539505231, 778151014, 425402192, 569549764, 171990975, 480916433, 550645889, 71155583, 156065139, 499692059, 80534761, 418595649, 488668178, 483262353, 761079127, 870633587, 582698686, 397416556, 822038326, 114261506, 24622713, 443392919, 951731173, 817492184, 18330423, 870833154, 834533088, 117896956, 94498840, 536131881, 64007453, 449923986, 821574370, 757613711, 74723964, 425578023, 919147061, 692033356, 467140194, 373099004, 252086810, 47599235, 287686980, 488329506, 304736267, 299921437, 487263176, 570386721, 155626518, 135120313, 780256499, 943269485, 439311458, 670666024, 820144824, 655910522, 349408761, 973209540, 677034872, 799353311, 291824074, 435161693, 231559494, 329403708, 2378980, 212710521, 920578026, 48047965, 550520588, 30545354, 69630519, 773962707, 829864195, 905590682, 611119572, 260204078, 634457375, 968471787, 369265835, 425686971, 38771751, 183683590, 747131861, 960719728, 915994433, 866159020, 473015288, 53506151, 124948573, 343917587, 589872578, 742294532, 14495852, 377992279, 338934871, 28241227, 447328270, 892278625, 134942590, 464657765, 668660637, 250672558, 737001081, 455948587, 309079478, 40504754, 181925242, 361072832, 758358698, 665940970, 43517628, 382558658, 948135945, 911525107, 499528803, 734538281, 204256642, 716926919, 415293736, 592211534, 424766655, 211715017, 811989654, 973185261, 71283395, 669909261, 482493386, 155893078, 159427226, 93862352, 216394917, 81081646, 180373727, 943312894, 438886068, 519120891, 113649471, 447020879, 739772797, 242921087, 74228901, 220425653, 391801216, 971741486, 261900778, 41122455, 852161905, 415634960, 431598449, 106918318, 819689988, 83691209, 268351949, 75997009, 544684771, 842793534, 394127480, 536977905, 273669961, 13154017, 674697744, 120570063, 173038062, 155289228, 729866854, 305834431, 254366798, 948146714, 392601387, 39480327, 1894544, 754109866, 572739979, 929037081, 90035951, 874246352, 59675925, 1639774, 365008783, 737618194, 547055796, 90532616, 469020494, 633699042, 164043064, 186471361, 193622327, 424472933, 626586210, 89128552, 996907354, 177728313, 771495880, 74281199, 969142217, 325059319, 798380593, 121126553, 471553701, 763095828, 455627020, 105743124, 341748301, 709962931, 111837265, 318531149, 930733897, 988695586, 830870739, 30656108, 122689687, 217360479, 391706796, 741471890, 523325838, 141398412, 107925116, 851092099, 271148809, 117970195, 863018934, 735447523, 857990960, 509742870, 500498218, 573794852, 447759458, 684941990, 844729133, 629225108, 222106593, 392879106, 533068281, 850626054, 45899995, 593638907, 934676342, 132318000, 499023155, 436171271, 552883679, 792295609, 645824803, 886827414, 706444268, 616896524, 78301802, 260254975, 901788810, 642418894, 305553206, 618273364, 788645719, 325110782, 587778720, 111711831, 542577686, 12630481, 256730080, 990724443, 869772036, 424356626, 206165254, 769304584, 613851764, 109177953, 544965142, 144527275, 685309657, 63128159, 657300159, 183652896, 321430751, 502528496, 818667858, 499495550, 376529503, 107701542, 391726460, 621975044, 124468824, 238513581, 896376532, 184309119, 932750151, 687110877, 429731291, 281410514, 593103008, 412518197, 620794804, 197857848, 88614112, 15607459, 45223178, 833816631, 377769395, 213918106, 940598221, 989987019, 484564200, 910451483, 875358514, 505257001, 732867688, 292446139, 82609509, 52728457, 38430250, 314974394, 335096325, 728604989, 447007395, 890184550, 517695501, 24770755, 921881760, 351326827, 217344338, 960947743, 75924321, 424019996, 694255122, 188892581, 834256730, 557264777, 697776343, 266829437, 874344960, 637341357, 423320860, 482111820, 814393690, 840475831, 679228153, 655235288, 877941507, 207328718, 248957988, 285894421, 395481136, 249742236, 430609643, 401495572, 954688273, 245064797, 922491926, 270272637, 115775092, 143669332, 849150685, 583597813, 588026197, 272442482, 187450294, 678335714, 259782599, 242688362, 534917942, 253525093, 210730219, 722032462, 965259266, 617034309, 393073110, 313721419, 56306249, 343735952, 636787318, 261702273, 321718608, 531249357, 37579442, 73077892, 579187843, 325446335, 501118772, 558299622, 192686246, 661106091, 878219067, 47659047, 403148139, 250519042, 920205385, 215748488, 432798303, 106669575, 886085854, 25864307, 514447542, 29281400, 401866153, 903783456, 915095654, 535826789, 833110881, 756854001, 137783625, 180168764, 811262396, 311635063, 273281805, 633829322, 440767894, 345547294, 949734795, 792150353, 189238431, 71998606, 947591062, 679349515, 606781339, 966875176, 224259878, 692359925, 820312559, 804141891, 368969629, 142139205, 939356275, 969189655, 414138837, 15044142, 176100512, 562397884, 787042742, 956416385, 176740934, 146380347, 557357153, 425360915, 337919072, 428764947, 894643220, 160943702, 738297521, 759110632, 102698674, 268473967, 60052640, 621526957, 895441155, 644577760, 559548335, 226477730, 804947440, 854802118, 212773938, 369618916, 630074277, 683336252, 733742391, 689759642, 536324741, 12232850, 588395062, 311834902, 822700906, 918264540, 383029467, 838692046, 779820735, 231894781, 127968797, 146143427, 514318905, 780214430, 532924900, 362245605, 616904934, 159952118, 974181243, 464233843, 638310707, 136785681, 650317857, 735148405, 813970111, 346354503, 450347746, 226170708, 949341109, 686265960, 457248555, 802620126, 406473234, 620525961, 499658652, 996948192, 432517005, 531544188, 736310230, 364121646, 51128023, 702339436, 491727676, 778790268, 991720904, 233882858, 447952019, 967158671, 131392770, 249020049, 17082876, 698852882, 940026909, 688883348, 292899252, 464708546, 689894359, 844446056, 660596379, 835026416, 434755394, 40833306, 988981175, 833869084, 148016296, 289878633, 691707616, 661734006, 227811471, 658581356, 651921475, 899658740, 598341579, 491077042, 523084223, 76743680, 345023872, 817961350, 668829460, 244890498, 889263641, 690084579, 789381194, 684971088, 529646577, 281941575, 866121528, 672773016]
n=int(input())
print(sum(l[:n])%1000000007)

ans = [ 1,3,9,27,84,270,892,3012,10350,36074,127218,453096,1627377,5887659,21436353,78484401,288779727,67263652,960081882,746806193,94725532,450571487,724717660,60828279,569244761,90251153,304700019,302293423,541190422,390449151,
209974658,263157008,466127089,411293524,9642992,693525433,786419491,239088269,314224563,510900486,630807069,573162239,544244038,661359018,21596629,964308860,101889397,415773350,891566594,746218312,480495430,519590679,980661877,781820967,846789157,783508306,669669852,309221450,90535894,771876087,
879005408,559032208,662591599,344778268,172329528,682957765,110093547,710686706,253161552,74445547,108476513,320584809,872695873,756288129,336746954,172286983,298675547,321303685,683959117,312609186,890486062,963769407,368093315,596703076,330949076,834264772,309051222,95672240,615516681,742138929,
974260866,435968318,400750278,844924823,617147132,35153304,615097283,663576724,918581247,68100403,391114587,480446369,681945176,561354669,875173797,23830615,453112723,34534980,587749357,16633884,321212028,7161405,651667210,745501073,149285713,981519957,490104375,438383249,247954378,693566304,
25989437,198989632,913054426,29683241,308202929,984865379,500180409,625401167,809591903,193482752,673482833,800132924,887112834,695564536,147195459,68465510,542341518,189111448,416145119,692313309,705010494,462171129,664654933,781598388,25738063,959953937,118406853,216401381,425537569,238050639,
356311658,790400034,907784194,635481328,473123791,605779687,403795072,179747838,972670677,737550601,463862214,293929122,653851165,605942649,758152944,940491370,980429809,15557976,918204612,127251691,149977247,401843653,445516465,948594822,939937911,593001643,641341553,720829647,130955644,677574925,
214217926,229947670,262588823,36017956,387240747,565359500,856181658,65668864,487170829,880581948,928892797,134957126,68797232,452319166,712566486,13142373,271159179,133120634,636438152,925904102,131646553,96839534,957678496,570609478,559477707,252282311,202091195,360711184,539190160,195508744,
131397011,726258613,938763140,135865077,624831736,186725767,616044985,68533950,234852589,859984598,762872015,627292340,543448608,642153906,496848196,846108629,340530350,973812853,253677682,497273753,236623263,7406703,246219054,264539226,207861074,954888852,542689867,895016105,279372573,939342464,
188267336,131602134,204973547,383929947,617368944,711925068,516706703,630105245,182002707,254521948,337071739,846968126,930795137,286823642,590119658,980426443,637448466,101819683,45924334,389499693,151729335,974092504,219385620,986025665,280317511,414269550,634560525,578210408,899711701,733001435,
517923794,923668013,454383915,74821752,86433024,914959020,852337978,311252553,726141661,912160424,662047479,750036960,805923034,542540716,883738298,900967144,518656459,322758408,225835176,324154458,852244098,313987215,96929349,179351977,498889311,586932369,893733420,436606751,524426173,989873480,
789442102,764900070,746168226,259581585,536900874,582383559,190694200,524339367,566831905,657666980,973761757,719823890,669819301,841553591,232581638,67725843,806692787,354180375,539592392,715947721,935859463,6259548,393769088,300250634,287400327,788185085,913510269,783250326,783143717,948128472,
878246010,535256662,658514354,83370381,636113599,821045174,552353114,617256875,48726983,382295302,95535652,758199141,855840586,226456423,74754642,353416198,179434483,211272752,612438184,894107057,780314347,902546392,319978718,806716386,182214064,948386038,490388513,354322982,432155054,269290398,
452018310,335595551,56997341,928350063,24723782,547149483,83498862,714261279,501653762,525459159,33415534,494918697,566644812,185333843,128342749,241611459,554389970,390871965,15094372,893112248,880048399,943080276,260060246,391691281,454730067,810346635,535008107,868672249,50587022,487034170,
385643932,49101323,708481037,100935281,113604809,17596904,493971052,810339199,900731778,458072288,906881202,89015007,314374675,122823395,810909888,253870170,937807523,423770993,732256066,622937069,695621133,752855268,527310438,795115960,566884714,572982980,793349159,159349946,952683406,817138801,
773213466,437230362,67903951,47482895,467404408,348487894,945674951,802121323,856168548,550139489,423561875,706448829,350713820,211061414,330956999,614436470,134422716,950946360,17778569,561547282,176363572,342964764,663917124,43265494,69401942,267132367,922898739,383480114,591458347,690479399,
960254442,34412897,452738969,440783906,748321449,988981888,254938048,720762638,697393308,245827188,795236723,65163363,711375605,183171179,79194072,112302270,421321170,994734695,543567926,272300184,223872282,286320941,989657746,102688969,710447352,848212999,729312713,120568221,22451273,553700154,
375443659,972051525,394295168,328072945,570414089,375804255,726265493,556478645,801573503,659341544,878125302,736153507,231760100,840609515,555069454,243030059,191493141,191525823,987078186,660474384,888928954,22631949,25744002,870406264,592164616,774445461,724788029,520943022,584632562,894444609,
333164007,699275359,794972185,91450599,996406612,366131918,723583060,771316741,79661647,399942960,999287120,13209034,677040142,809614610,694670866,535342340,211511635,350807447,609016066,201174050,963075625,105530451,405233105,900994628,789804212,894353843,69819298,362739448,947238549,520918384,
649553698,885936877,747972100,858958148,590763083,584410508,330600030,797816254,351873367,869118053,26710477,682272830,302905814,619536461,704626060,708352504,284637530,213607859,593861636,953387245,530319822,872287244,405724029,341446420,464274920,826281181,75268474,892526115,798799969,628194331,
154799991,737461475,108117045,990922164,744219668,826010956,142622204,327887197,994113041,807166880,122739241,130177949,231817391,79169791,86531255,542398759,543562372,821446997,516893585,219553034,448671164,336909092,32521321,827803773,986003346,832047601,819867310,165216381,6756342,908483425,
617533518,121273130,136099019,14610487,811283801,217821909,120210787,47985877,915403925,965433865,811912365,841700808,202790256,446219347,10604530,111780766,582874406,661264137,722608351,618846201,562056576,310659654,798277188,759059218,40049650,378888700,743855519,641447125,880652730,112536549,
1105248,354000472,588660003,791125714,538276053,482857020,106494783,83739570,492815881,137037964,58968561,938355777,70859619,159600008,69928655,271942118,386020849,648876387,153526885,7145893,564395720,423989225,206868720,368457054,659108291,635994868,175500092,953651106,379053291,948603055,
120594023,601510456,152156338,223311921,379377060,879069119,959603880,378199522,8066867700,350130046,111209166,981842753,564541432,961957988,783996307,898257813,922880526,366273438,318004604,135496781,153827204,24660351,859193439,977090395,71589228,607721109,671728562,121652541,943226911,700840615,
775564579,201142595,120289649,812323005,279463192,652562196,904649006,952248241,239935214,728264720,33000980,332922417,820185593,390572307,546198825,681319138,461575630,404845108,844156566,514822583,334967400,990877922,340286676,313496209,990531081,789884385,81708452,516870145,748429639,77833340,
80212320,292922841,213500860,261548825,812069413,842614767,912245286,686207986,516072174,421662849,32782414,292986492,927443867,895915647,265181475,690868446,729640197,913323787,660455641,621175362,537169788,403328801,876344089,929850240,54798806,398716393,988588971,730883496,745379348,123371620,
462306491,490547718,937875988,830154606,965097196,429754954,98415584,349088142,86089216,542037803,851117281,891622035,73547270,434620102,192978793,858919763,902437391,284996042,233131980,144657080,644185883,378724157,582980799,299907711,715201447,307412974,732179629,943894646,755884293,729069547,
800352942,470262196,952755582,108648653,268075879,361938231,578333148,659414794,839788521,783101408,221987469,741108360,854757831,301778703,41551493,284472580,358701481,579127134,970928350,942669829,204570600,245693055,97854953,513489913,945088362,52006673,871696661,955387870,223739812,299736821,
844421592,687215119,81342592,618320497,891990458,905144475,579842212,700412275,873450337,28739558,758606412,64440836,318807634,266954341,659555728,699036055,700930599,455040458,27780430,956817511,46853455,921099807,980775732,982415506,347424282,85042469,632098265,722630881,191651368,825350410,
989393474,175864828,369487155,793960088,420546291,509674843,506582190,684310503,455806376,530087575,499229785,824289104,622669690,743796243,215349937,978445765,434072778,539815902,881564203,591527127,703364392,21895534,952629431,941325010,772195742,802851850,925541537,142902009,534608805,276080688,
799406526,940804938,48730047,899822146,170970948,288941143,151960070,887407593,745398546,255141409,755639627,329434472,777193930,462135913,306865039,936090147,158196733,551075839,84144113,934770167,980670162,574309062,508985397,641303397,140326545,576497816,129381488,921677097,567501893,454329300,
160773561,777670085,855971887,116226855,18015658,660434552,965987758,584261115,372906827,698017609,285796322,397508153,940085839,952716320,209446393,200170829,69942858,494299484,700464738,469769315,83621072,192799025,737764167,882291442,567601092,630729251,288029403,471682299,793113050,295641539,
114309390,613804940,990334443,98035978,489762438,111737475,236206299,474719880,371096405,555405524,488155668,175266538,604997829,886408343,479511344,892029541,512824338,710682186,799296298,814903757,860126935,693943559,71712947,285631053,226229267,216216279,700780479,611231955,486590462,991847463,
724715144,17161276,99770785,152499242,190929492,505903886,841000211,569605193,16612581,906797131,424492625,449263380,371145133,722471960,939816298,900764034,976688355,400708344,94963459,283856040,118112763,675377540,373153876,639983313,514328266,151669616,574990476,57102289,871495979,711971803,
391199949,46435230,924376737,131705448,380663436,666557857,62038986,311781222,742390865,143886430]

print(ans[int(input())-1])


n = int(input())

board = [[0 for i in range(n + 1)] for j in range(2 * n + 1)]

board[0][0] = 1
for i in range(1, n):
    for j in range(len(board[0])):
        if j > 0:
            board[i][j-1] += board[i-1][j]
        if j + 1 < len(board[0]) and j < 2 * n - i:
            board[i][j+1] += board[i-1][j]
for i in range(n, 2 * n + 1):
    for j in range(len(board[0])):
        if j > 0:
            board[i][j-1] += board[i-1][j]
            #board[i][j-1] %= 1000000007
        if j + 1 < len(board[0]) and j < 2 * n - i:
            board[i][j+1] += board[i-1][j]       
            #board[i][j+1] %= 1000000007     
ans = 0
for i in range(1, len(board), 2):
    
    ans += sum(board[i])
    ans %= 1000000007
        
print(ans)

n = int(input())
dp = [[[0] * (n+1) for i in range(n + 1)] for j in range(2)]

dp[0][0][0] = 0
dp[1][0][0] = 0
mod = 10 ** 9 + 7
for i in range(n + 1):
    for j in range(i, n + 1):
        if i == 0 and j == 0:
            continue
        dp[0][i][j] = (dp[1][i - 1][j] + dp[1][i][j - 1]) % mod
        tmp1 = 1
        if i - 1 <= j and i > 0:
            if i <= j - 1:
                tmp1 += dp[1][i][j - 1]
                tmp1 %= mod
            tmp1 += dp[0][i - 1][j]
        tmp1 %= mod
        tmp2 = 1
        if i <= j - 1 and j > 0:
            if i - 1 <= j:
                tmp2 += dp[1][i - 1][j]
                tmp2 %= mod
            tmp2 += dp[0][i][j - 1]
        tmp2 %= mod


        #
        # dp[i][j][1] = max(
        #     (((dp[i - 1][j][0]) + (dp[i][j - 1][1] if i <= j - 1 else 0)) if i - 1 <= j and i > 0 else 0) + 1,
        #     (((dp[i - 1][j][1] if i - 1 <= j else 0) + (dp[i][j - 1][0])) if i <= j - 1 and j > 0 else 0) + 1
        # ) % mod

        dp[1][i][j] = max(tmp1, tmp2) % mod

# for i in range(n + 1):
#     for j in range(n + 1):
#         print(i, j, dp[i][j][0], dp[i][j][1])

print(max(dp[0][-1][-1], dp[1][-1][-1]) % mod)

# print(dp)


n = int(input())
f = [[0]*(n+1) for i in range(n+1)]
g = [[0]*(n+1) for i in range(n+1)]
mod = 10**9+7
for i in range(1, n + 1):
    f[0][i] = g[0][i - 1]
    g[0][i] = f[0][i - 1] + 1
t = [0, 0]
for i in range(1, n + 1):
    for j in range(i, n + 1):
        if i > 0:
            f[i][j] += g[i - 1][j]
            t[0] = g[i - 1][j]
            t[1] = f[i - 1][j] + 1
        if j > i:
            f[i][j] += g[i][j-1]
            t[0] += f[i][j - 1] + 1
            t[1] += g[i][j - 1]
        for k in t: g[i][j] = max(g[i][j], k)
print(g[n][n]%mod)



n = int(input())
f = [[0]*(n+1) for i in range(n+1)]
g = [[0]*(n+1) for i in range(n+1)]
mod = 10**9+7
for i in range(1, n + 1):
    f[0][i] = g[0][i - 1]
    g[0][i] = f[0][i - 1] + 1
t = [0, 0]
for i in range(1, n + 1):
    for j in range(i, n + 1):
        if i > 0:
            f[i][j] = g[i - 1][j]
            t[0] = g[i - 1][j]
            t[1] = f[i - 1][j] + 1
        if j > i:
            f[i][j] = (f[i][j] + g[i][j-1]) % mod
            t[0] = (t[0] + f[i][j - 1] + 1) % mod
            t[1] = (t[1] + g[i][j - 1]) % mod;
        for k in t: g[i][j] = max(g[i][j], k)
print(g[n][n]%mod)



def fine():
    f, c, n = 1, 1, 1
    yield 0
    while True:
        yield f
        n += 1
        c = c * (4 * n - 6) // n
        f = (c - f) // 2

f = fine()
n = int(input())
print((sum(next(f) for _ in range(n + 3)) - 1) % (10**9 + 7))


N = int(input())
mod = 10**9+7
dp = [[0]*(N+1) for _ in range(N+1)]
dp[1][0] = 1
dp[1][1] = 1
for i in range(2, N+1):
    if i % 2:
        dp[i][i] = 1 + i//2
    else:
        dp[i][i] = i//2
    for j in range(i-1, -1, -1):
        dp[i][j] = (dp[i][j+1] + dp[i-1][j-1] + j%2)%mod
print(dp[-1][0])

mod = 1000000007
n = int(input())
cat = [0] * 1100
f, c, i = 1, 1, 1
while i < 1100:
    cat[i] = f
    i += 1
    c = c * (8*i - 12) // i
    f = c - f
cat = cat[1:-1]
sm = 0
for i in range(3, n + 3):
    sm += (cat[i - 1] + (-1) ** (i - 1)) // (1 << i)
print(sm % mod)

from itertools import accumulate
N = int(input())

arr = [1]

res = 1

for i in range(2,N+1):
    arr = list(accumulate(arr))
    arr = arr + [arr[-1]]
    d = i+1
    
    #print(arr)
    
    s = 0
    
    for i in range(len(arr)):
        s += arr[i]*(d//2)
        d -= 1
    
    res += s
    
    res = res % 1000000007
    #print(res)
    
print(res)

u = 1000000007
import sys
def P(n): 
    #take first edge or no? depth == < - >
    X = [[0 for i in range(2*n+1)] for j in range(2*n+1)]
    X[0][0] = 1
    r = 0
    for i in range(1,2*n+1):
        X[i][0]=X[i-1][1]
        for j in range(1,min([2*n+1-i,i+1])):
            X[i][j] = (X[i-1][j+1]+X[i-1][j-1])%u
        if i%2:r+=sum(X[i])
    return r%u

print(P(int(sys.stdin.read()[:-1])))


import collections
import random
import heapq
import bisect
import math
import time


class Solution2:
    def solve(self, A1, A2):
        pass
        

class Solution:
    def gcd(self, a, b):
        if not b: return a
        return self.gcd(b, a%b)

    def lcm(self, a, b):
        return b*a//self.gcd(b,a)

    def solve(self, n):
        out = 0
        MOD = 1000000007
        curr = {0 : [1,0]}
        for i in range(2*n):
            new_curr = {}

            for pos, (ways_clear, ways_taken) in list(curr.items()):
                ways_clear = ways_clear%MOD
                ways_taken = ways_taken%MOD
                if pos: 
                    if pos-1 not in new_curr: new_curr[pos-1] = [0,0]
                    new_curr[pos-1][0] += ways_taken
                    new_curr[pos-1][1] += ways_clear
                    out += ways_clear
                if pos < 2*n - i: 
                    if pos+1 not in new_curr: new_curr[pos+1] = [0,0]
                    new_curr[pos+1][0] += ways_taken
                    new_curr[pos+1][1] += ways_clear
                    out += ways_clear
            curr = new_curr
            #print(curr)
        return out%MOD



sol = Solution()
sol2 = Solution2()

#TT = int(input())
for test_case in range(1):
    N = input()
    #a = [int(c) for c in input().split()]
    #b = [int(c) for c in input().split()]

    out = sol.solve(int(N))
    print(str(out))
    #print(str(out))

    # out2 = sol2.solve(s)


# for _ in range(100000):
#     rand = [random.randrange(60) for _ in range(10)]
#     out1 = sol.solve(rand)
#     out2 = sol2.solve(rand)
#     if out1 != out2: 
#         print(rand, out1, out2)
#         break


N = int(input())

MOD = 10**9 + 7
dp = [[0] * (2020 + 1) for _ in range(2020 + 1)]
dp[1][1] = 1
ans = 0
for i in range(2, N + 2):
    for j in range(1, i + 1):
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD
        if (i + j) % 2 == 1:
            ans = (ans + dp[i][j]) % MOD
print(ans)


N = int(input())

MOD = 10**9 + 7
dp = [[0] * (2020 + 1) for _ in range(2020 + 1)]
dp[1][1] = 1
ans = 0
for i in range(2, N + 2):
    for j in range(1, i + 1):
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD
        if (i + j) % 2 == 1:
            ans = (ans + dp[i][j]) % MOD
print(ans)