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: HARD
Tags: Tree algorithms

Dynamic programming

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
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])


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 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
		return out % MOD
sol = Solution()
sol2 = Solution2()
for test_case in range(1):
	N = input()
	out = sol.solve(int(N))
	print(str(out))


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
	s = 0
	for i in range(len(arr)):
		s += arr[i] * (d // 2)
		d -= 1
	res += s
	res = res % 1000000007
print(res)


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)


n = int(input())
dp = [[0 for i in range(2005)] for j in range(2005)]
(ans, mod) = (0, 10 ** 9 + 7)
dp[1][1] = 1
for i in range(1, 2 * n):
	for j in range(2 * n):
		dp[i + 1][j + 1] += dp[i][j]
		if dp[i + 1][j + 1] >= mod:
			dp[i + 1][j + 1] -= mod
		if j > 0:
			dp[i + 1][j - 1] += dp[i][j]
			if dp[i + 1][j - 1] >= mod:
				dp[i + 1][j - 1] -= mod
for i in range(1, 2 * n, 2):
	for j in range(2 * n):
		valid = i + j <= 2 * n
		if valid:
			ans += dp[i][j]
			if ans >= mod:
				ans -= mod
print(ans % 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)


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)


u = 1000000007
import sys

def P(n):
	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])))


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[1][i][j] = max(tmp1, tmp2) % mod
print(max(dp[0][-1][-1], dp[1][-1][-1]) % mod)


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])


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


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))


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)


n = int(input())
mod = 10 ** 9 + 7
dp = [[0] * (n + 1) for i in range(2 * n + 1)]
dp[0][0] = 1
for d in range(1, 2 * n + 1):
	for v in range(n + 1):
		if v + 1 <= n:
			dp[d][v + 1] += dp[d - 1][v]
			dp[d][v + 1] %= mod
		if v - 1 >= 0:
			dp[d][v - 1] += dp[d - 1][v]
			dp[d][v - 1] %= mod
ans = 0
for d in range(2 * n + 1):
	if d % 2 == 1:
		for v in range(n + 1):
			if v <= 2 * n - d:
				ans += dp[d][v]
				ans %= mod
print(ans)


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)