In Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation.

We will consider an extremely simplified subset of Python with only two types of statements.

Simple statements are written in a single line, one per line. An example of a simple statement is assignment.

For statements are compound statements: they contain one or several other statements. For statement consists of a header written in a separate line which starts with "for" prefix, and loop body. Loop body is a block of statements indented one level further than the header of the loop. Loop body can contain both types of statements. Loop body can't be empty.

You are given a sequence of statements without indentation. Find the number of ways in which the statements can be indented to form a valid Python program.


-----Input-----

The first line contains a single integer N (1 ≤ N ≤ 5000) — the number of commands in the program. N lines of the program follow, each line describing a single command. Each command is either "f" (denoting "for statement") or "s" ("simple statement"). It is guaranteed that the last line is a simple statement.


-----Output-----

Output one line containing an integer - the number of ways the given sequence of statements can be indented modulo 10^9 + 7. 


-----Examples-----
Input
4
s
f
f
s

Output
1

Input
4
f
s
f
s

Output
2



-----Note-----

In the first test case, there is only one way to indent the program: the second for statement must be part of the body of the first one.

simple statement

for statement

    for statement

        simple statement



In the second test case, there are two ways to indent the program: the second for statement can either be part of the first one's body or a separate statement following the first one.

for statement

    simple statement

    for statement

        simple statement



or

for statement

    simple statement

for statement

    simple statement

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(N^2)

Starter code:

Solutions:
n = int(input())
a = [1]
flag = False
for i in range(n):
	if flag:
		a.append(0)
		flag = False
	else:
		s = 0
		for i in range(len(a)):
			t = a[i]
			a[i] += s
			s += t
			a[i] %= 10 ** 9 + 7
			s %= 10 ** 9 + 7
	if input() == 'f':
		flag = True
print(sum(a) % (10 ** 9 + 7))


def add(a, b):
	a = a % (1000000000 + 7)
	b = b % (1000000000 + 7)
	return (a + b) % (1000000000 + 7)
n = int(input())
i = 1
statements = []
dp = [[0 for i in range(n)] for i in range(n)]
prefix = [[0 for i in range(n)] for i in range(n)]
while i <= n:
	s = input()
	statements.append(s)
	i += 1
dp[0][0] = 1
prefix[0][0] = 1
j = 1
while j < n:
	dp[0][j] = 0
	prefix[0][j] = dp[0][j] + prefix[0][j - 1]
	j += 1
i = 1
while i < n:
	if statements[i - 1] == 'f':
		j = 1
		while j < n:
			dp[i][0] = 0
			prefix[i][0] = 0
			dp[i][j] = dp[i - 1][j - 1]
			prefix[i][j] = add(prefix[i][j - 1], dp[i][j])
			j += 1
	else:
		j = 0
		while j < n:
			if j == 0:
				dp[i][j] = prefix[i - 1][n - 1]
			else:
				dp[i][j] = prefix[i - 1][n - 1] - prefix[i - 1][j - 1]
			prefix[i][j] = add(prefix[i][j - 1], dp[i][j])
			j += 1
	i += 1
ans = 0
j = 0
while j < n:
	ans = add(ans, dp[n - 1][j])
	j += 1
print(ans % (1000000000 + 7))


import sys
import time
import re
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
gosa = 1.0 / 10 ** 10
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()
N = int(input())

def solve():
	A = []
	for n in range(N):
		A.append(input())
	dp = [[0] * (N + 1) for n in range(N + 1)]
	dp[0][0] = 1
	pre_a = A[0]
	for (i, a) in enumerate(A):
		if i == 0:
			continue
		if pre_a == 'f':
			for j in reversed(list(range(i + 1))):
				dp[i][j] = dp[i - 1][j - 1]
		else:
			s = 0
			for j in reversed(list(range(i))):
				s += dp[i - 1][j]
				s %= mod
				dp[i][j] = s
		pre_a = a
	res = 0
	for v in dp[N - 1]:
		res += v
		res = res % mod
	print(res)

def __starting_point():
	solve()
__starting_point()


from sys import stdin, stdout
n = int(stdin.readline())
dp = [[0 for i in range(n + 10)] for j in range(n + 10)]
MOD = 10 ** 9 + 7
dp[-1][0] = 1
previous = []
for i in range(n):
	s = stdin.readline().strip()
	if not previous or previous[-1] != 'f':
		cnt = 0
		for j in range(n, -1, -1):
			cnt = (cnt + dp[i - 1][j]) % MOD
			dp[i][j] = cnt
	else:
		cnt = 0
		for j in range(n + 1, -1, -1):
			cnt = dp[i - 1][j - 1]
			dp[i][j] = cnt
	previous.append(s)
ans = 0
for i in range(n + 1):
	ans = (ans + dp[n - 1][i]) % MOD
stdout.write(str(ans))


n = int(input())
s = [input() for i in range(n)]
MOD = 10 ** 9 + 7
dps = [[0] * (n + 3) for i in range(n + 1)]
dpf = [[0] * (n + 3) for i in range(n + 1)]
for k in range(n + 1):
	dps[0][k] = 1
for (pos, char) in enumerate(s):
	if char == 's':
		for depth in range(pos + 2):
			dps[pos + 1][depth] = dpf[pos][depth] - dpf[pos][depth - 1] + dps[pos][pos] - dps[pos][depth - 1]
			dps[pos + 1][depth] += dps[pos + 1][depth - 1]
			dps[pos + 1][depth] %= MOD
		for p in range(pos + 2, n + 1):
			dpf[pos + 1][p] += dpf[pos + 1][p - 1]
			dpf[pos + 1][p] %= MOD
		continue
	else:
		for depth in range(1, pos + 2):
			dpf[pos + 1][depth] = dpf[pos][depth - 1] - dpf[pos][depth - 2] + dps[pos][pos] - dps[pos][depth - 2]
			dpf[pos + 1][depth] += dpf[pos + 1][depth - 1]
			dpf[pos + 1][depth] %= MOD
		for p in range(pos + 2, n + 1):
			dpf[pos + 1][p] += dpf[pos + 1][p - 1]
			dpf[pos + 1][p] %= MOD
ans = dps[n][n] % MOD
print(ans)


MOD = int(1000000000.0 + 7)
n = int(input())
a = []
for i in range(n):
	a.append(input())
a = ''.join(a)
(dp, s) = ([], [])
for i in range(n + 1):
	dp.append([0] * (n + 1))
	s.append([0] * (n + 1))
dp[0][0] = 1
s[0][0] = 1
for i in range(1, n):
	for j in range(0, n):
		if a[i - 1] == 'f':
			dp[i][j + 1] = dp[i - 1][j] % MOD
		elif a[i - 1] == 's':
			dp[i][j] = s[i - 1][j] % MOD
	for j in reversed(range(n)):
		s[i][j] += (dp[i][j] + s[i][j + 1]) % MOD
print(s[n - 1][0] % MOD)


n = int(input())
L = [0] * 5000
L[0] = 1
f = 1
for i in range(n):
	C = input()
	if C == 'f':
		f = f + 1
	else:
		for j in range(1, f):
			L[j] = (L[j] + L[j - 1]) % 1000000007
print(L[f - 1])


def solve():
	rd = lambda : list(map(int, input().split()))
	n = int(input())
	p = []
	for i in range(n):
		p.append(input())
	dp = [0 for i in range(n)]
	dp[0] = 1
	indent = 0
	L = int(1000000000.0 + 7)
	for (i, val) in enumerate(p):
		if val == 'f':
			indent += 1
		else:
			for j in range(1, indent + 1):
				dp[j] = (dp[j - 1] + dp[j]) % L
	print(dp[indent])
solve()


import sys
import math
from collections import defaultdict, deque
import heapq
n = int(sys.stdin.readline())
arr = []
mod = 10 ** 9 + 7
for i in range(n):
	s = sys.stdin.readline()[:-1]
	arr.append(s)
dp = [[0 for _ in range(n)] for x in range(n)]
dp[0][0] = 1
for i in range(1, n):
	if arr[i] == 's' and arr[i - 1] == 'f':
		for j in range(n - 1, 0, -1):
			dp[i][j] = dp[i - 1][j - 1]
			dp[i][j] %= mod
	if arr[i] == 'f' and arr[i - 1] == 's':
		pre = 0
		for j in range(n - 1, -1, -1):
			pre += dp[i - 1][j]
			dp[i][j] = pre
			pre %= mod
			dp[i][j] %= mod
	if arr[i] == 's' and arr[i - 1] == 's':
		pre = 0
		for j in range(n - 1, -1, -1):
			pre += dp[i - 1][j]
			dp[i][j] = pre
			pre %= mod
			dp[i][j] %= mod
	if arr[i] == 'f' and arr[i - 1] == 'f':
		for j in range(n - 1, 0, -1):
			dp[i][j] = dp[i - 1][j - 1]
ans = sum(dp[n - 1])
ans %= mod
print(ans)


n = int(input())
s = [0 for _ in range(n)]
for i in range(n):
	s[i] = input()
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	if s[i] == 's':
		sums = 0
		for j in reversed(range(n)):
			sums = (sums + dp[i][j]) % 1000000007
			dp[i + 1][j] = sums
	else:
		for j in range(n):
			dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % 1000000007
print(dp[n][0])


import sys
import math
input = sys.stdin.readline
from functools import cmp_to_key

def pi():
	return int(input())

def pl():
	return int(input(), 16)

def ti():
	return list(map(int, input().split()))

def ts():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
mod = 1000000007
f = []

def fact(n, m):
	global f
	f = [1 for i in range(n + 1)]
	f[0] = 1
	for i in range(1, n + 1):
		f[i] = f[i - 1] * i % m

def fast_mod_exp(a, b, m):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b = b >> 1
	return res

def inverseMod(n, m):
	return fast_mod_exp(n, m - 2, m)

def ncr(n, r, m):
	if n < 0 or r < 0 or r > n:
		return 0
	if r == 0:
		return 1
	return f[n] * inverseMod(f[n - r], m) % m * inverseMod(f[r], m) % m

def main():
	C()

def D():
	[n, m, k] = ti()
	w = [[] for i in range(n)]
	for i in range(n):
		w[i] = ts()
	mn = [[0 for j in range(k + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(k + 1):
			c = 0
			(st, en) = (-1, -1)
			for x in range(m):
				if w[i - 1][x] == '1':
					if c == j and st == -1:
						st = x
					if c < j:
						c += 1
					if c == j:
						en = x
			mn[i][j] = en - st + 1 if st != -1 and en != -1 else 0
			(st, en) = (-1, -1)
			c = 0
			for x in range(m - 1, -1, -1):
				if w[i - 1][x] == '1':
					if c == j and st == -1:
						st = x
					if c < j:
						c += 1
					if c == j:
						en = x
			if st != -1 and en != -1 >= 0:
				mn[i][j] = min(mn[i][j], st - en + 1)
	dp = [[9999999999999999 for j in range(k + 1)] for i in range(n + 1)]
	for i in range(k + 1):
		dp[0][i] = 0
	for i in range(1, n + 1):
		for j in range(k + 1):
			for x in range(k + 1):
				if j - x >= 0:
					dp[i][j] = min(dp[i][j], dp[i - 1][j - x] + mn[i][x])
	print(dp[n][k])

def C():
	n = pi()
	s = []
	mxI = 0
	for i in range(n):
		c = input()
		s.append(c[:len(c) - 1])
		if s[len(s) - 1] == 'f':
			mxI += 1
	dp = [[0 for j in range(mxI + 1)] for i in range(n)]
	dp[0][0] = 1
	preSum = [1 for i in range(mxI + 1)]
	pre = 1
	for i in range(1, n):
		sm = 0
		pre = 0
		for j in range(mxI + 1):
			if s[i - 1] == 'f':
				dp[i][j] = dp[i - 1][j - 1] % mod
			else:
				dp[i][j] = (preSum[mxI] % mod - (pre if j != 0 else 0) % mod) % mod
			pre = preSum[j]
			preSum[j] = ((preSum[j - 1] if j != 0 else 0) % mod + dp[i][j] % mod) % mod
	print(preSum[mxI] % mod)
main()


mod = 10 ** 9 + 7
n = int(input())
dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 1
s = []
for i in range(n):
	s.append(input())
for i in range(1, n + 1):
	if s[i - 1] != 'f':
		c = 0
		for j in range(n - 1, -1, -1):
			dp[i][j] = c + dp[i - 1][j]
			c += dp[i - 1][j]
			c %= mod
			dp[i][j] %= mod
	else:
		for j in range(n + 1):
			dp[i][j] = dp[i - 1][j - 1]
		dp[i][0] = 0
print(sum(dp[n - 1]) % mod)


import sys
from random import *
from bisect import *
pl = 1
from math import gcd, sqrt
from copy import *
sys.setrecursionlimit(10 ** 5)
if pl:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('outpt.txt', 'w')

def li():
	return [int(xxx) for xxx in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())
t = 1
while t > 0:
	t -= 1
	n = fi()
	mod = 10 ** 9 + 7
	dp = [[0 for i in range(n + 5)] for j in range(n + 5)]
	prev = '-1'
	for i in range(n):
		p = input().rstrip()
		if i == 0:
			dp[i][0] = 1
		else:
			c = 0
			if prev == 'f':
				for j in range(n):
					dp[i][j + 1] = dp[i - 1][j]
			else:
				for j in range(n, -1, -1):
					c = (c + dp[i - 1][j]) % mod
					dp[i][j] = c
		prev = p
	print(sum(dp[n - 1]) % mod)


mod = int(1000000000.0 + 7)

def solve(n, a):
	dp = [0 for i in range(n)]
	dp[0] = 1
	indent = 0
	for i in a:
		if i == 'f':
			indent += 1
		else:
			for j in range(1, indent + 1):
				dp[j] = (dp[j - 1] + dp[j]) % mod
	return dp[indent]

def python_identation(n, a):
	return solve(n, a)
n = int(input())
a = []
for i in range(1, n + 1):
	a.append(input())
print(python_identation(n, a))


n = int(input())
MODULO = 10 ** 9 + 7
i = 0
dp = [[0 for i in range(n + 2)] for j in range(n + 2)]
dp[0][0] = 1
new_array = [0] * (n + 2)
old_array = [0] * (n + 2)
new_array[0] = 1
for i in range(n):
	c = input()[0]
	old_array = new_array
	new_array = [0] * (n + 2)
	if c == 'f':
		for j in range(n):
			new_array[j + 1] = old_array[j]
	else:
		j = i + 1
		tmp = 0
		while j >= 0:
			tmp = (tmp + old_array[j]) % MODULO
			new_array[j] = tmp % MODULO
			j -= 1
tmp = 0
for i in range(n):
	tmp = (tmp + old_array[i]) % MODULO
print(tmp)


n = int(input())
mod = 10 ** 9 + 7
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
	nx = [0] * (n + 1)
	s = str(input())
	if s == 'f':
		nx[0] = 0
		for j in range(1, n + 1):
			nx[j] = dp[j - 1]
			nx[j] %= mod
	else:
		nx[n] = dp[n]
		for j in reversed(range(n)):
			nx[j] = nx[j + 1]
			nx[j] += dp[j]
			nx[j] %= mod
	if i != n - 1:
		dp = nx
print(sum(dp) % mod)


n = int(input())
dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 1
mod = 1000000007
s = []
for _ in range(n):
	s.append(input())
for _ in range(1, n + 1):
	if s[_ - 1] == 'f':
		for __ in range(1, n + 1):
			dp[_][__] = dp[_ - 1][__ - 1]
		dp[_][0] = 0
	else:
		sum = 0
		for __ in reversed(range(n)):
			dp[_][__] = sum + dp[_ - 1][__]
			sum += dp[_ - 1][__]
			sum %= mod
			dp[_][__] %= mod
ans = 0
for __ in range(n):
	ans += dp[n - 1][__]
	ans %= mod
print(int(ans))


N = int(input())
instruction = [''] * N
for i in range(N):
	instruction[i] = input()
ans = [[0 for _ in range(N)] for _ in range(N)]
ans[0][0] = 1
for i in range(1, N):
	if instruction[i - 1] == 'f':
		for j in range(i):
			ans[i][j + 1] = ans[i - 1][j]
	else:
		temp = 0
		for j in range(i - 1, -1, -1):
			temp = (temp + ans[i - 1][j]) % (1000000000.0 + 7)
			ans[i][j] = temp
s = 0
for v in ans[N - 1]:
	s = (s + v) % (1000000000.0 + 7)
print(int(s))


from collections import *

def dp():
	mem = [1]
	for i in range(n):
		if a[i] == 'f':
			mem.append(0)
		else:
			for j in range(1, len(mem)):
				mem[j] = (mem[j] + mem[j - 1]) % mod
	return mem[-1]
(n, mod) = (int(input()), 1000000007)
a = [input() for i in range(n)]
print(dp())


n = int(input())
f = [input().strip() == 'f' for ii in range(n)]
mod = 10 ** 9 + 7

def summ(a, b):
	return (a + b) % mod
dp = [1]
for ii in range(1, n):
	pf = f[ii - 1]
	if pf:
		dp.insert(0, 0)
	else:
		for jj in reversed(range(1, len(dp))):
			dp[jj - 1] = summ(dp[jj - 1], dp[jj])
ans = 0
for vv in dp:
	ans = summ(ans, vv)
print(ans)


modulo = int(1000000000.0 + 7)
n = int(input())
arr = [input() for i in range(n)]
dp = [1]
for i in range(n):
	if arr[i] == 'f':
		dp.append(0)
		continue
	for j in range(1, len(dp)):
		dp[j] = (dp[j] + dp[j - 1]) % modulo
print(dp[-1])


n = int(input())
dp = [1]
for i in range(n):
	c = input()
	if c == 'f':
		dp.append(0)
	else:
		for j in range(1, len(dp)):
			dp[j] = (dp[j] + dp[j - 1]) % 1000000007
print(dp[-1])


n = int(input())
s = [input() for _ in range(n)]
ml = 1 + s.count('f')
dp = [[0] * ml for _ in range(n)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(1, n):
	if s[i - 1] == 'f':
		for j in range(ml):
			if dp[i - 1][j]:
				dp[i][j + 1] = dp[i - 1][j] % mod
	else:
		pre = 0
		for j in range(ml - 1, -1, -1):
			pre = (pre + dp[i - 1][j]) % mod
			dp[i][j] = pre
print(sum(dp[-1]) % mod)


import sys
input = sys.stdin.readline
n = int(input())
c = [' '] + [input().rstrip() for i in range(n)]
mod = 10 ** 9 + 7
dp = [[0] * (n + 1) for i in range(n + 1)]
dp[1][0] = 1
sdp = [0] * (n + 1)
sdp[0] = 1
for i in range(1, n + 1):
	if i >= 2 and c[i - 1] == 'f':
		for j in range(1, n + 1):
			dp[i][j] = dp[i - 1][j - 1]
			dp[i][j] %= mod
		dp[i][0] = 0
	else:
		for j in range(n + 1):
			dp[i][j] = sdp[j]
			dp[i][j] %= mod
	sdp = [dp[i][j] for j in range(n + 1)]
	for j in range(1, n + 1)[::-1]:
		sdp[j - 1] += sdp[j]
		sdp[j - 1] %= mod
print(sdp[0] % mod)


MOD = int(1000000000.0 + 7)
n = int(input())
a = [input() for i in range(n)]
dp = [1]
for i in range(n):
	if a[i] == 'f':
		dp.append(0)
		continue
	for j in range(1, len(dp)):
		dp[j] = (dp[j] + dp[j - 1]) % MOD
print(dp[-1])


from sys import stdout
m = int(1000000000.0 + 7)
n = int(input())
a = [0] * n
a[0] = 1
k = 0
for _ in range(n):
	s = input()
	if s == 'f':
		k += 1
	elif s == 's':
		for j in range(1, k + 1):
			a[j] = (a[j - 1] + a[j]) % m
print(a[k])


n = int(input())
dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 1
for i in range(0, n):
	a = input()
	if a == 'f':
		for j in range(1, n):
			dp[i + 1][j] = dp[i][j - 1]
	else:
		suf = 0
		for j in range(n - 1, -1, -1):
			suf = (suf + dp[i][j]) % 1000000007
			dp[i + 1][j] = (dp[i + 1][j] + suf) % 1000000007
print(sum([x for x in dp[n - 1]]) % 1000000007)


rd = lambda : list(map(int, input().split()))
value = int(input())
stmt = []
for i in range(value):
	ch = input()
	stmt.append(ch)
dp = [0 for i in range(value)]
dp[0] = 1
c = 0
for (i, val) in enumerate(stmt):
	if val == 'f':
		c += 1
	else:
		for j in range(1, c + 1):
			dp[j] = (dp[j - 1] + dp[j]) % 1000000007
print(dp[c])


n = int(input())
dp = [1]
for IND in range(n):
	c = input()
	if c == 'f':
		dp.insert(0, 0)
	else:
		for i in range(len(dp) - 2, -1, -1):
			dp[i] = (dp[i] + dp[i + 1]) % 1000000007
print(dp[0])


import sys
input = sys.stdin.readline
n = int(input())
s = ''
for _ in range(n):
	s += input().strip()
DP = [[0] * 5001 for _ in range(2)]
ind = 0
DP[0][0] = 1
for i in range(1, n + 1):
	now = i % 2
	last = 1 - now
	if s[i - 1] == 'f':
		ind += 1
		for k in range(ind, -1, -1):
			DP[now][k] = DP[last][k - 1]
		DP[now][0]
	else:
		pos = 1
		DP[now][ind] = 1
		for k in range(ind - 1, -1, -1):
			pos += DP[last][k]
			DP[now][k] = pos % (10 ** 9 + 7)
print(max(1, sum(DP[(n - 1) % 2])) % (10 ** 9 + 7))


MOD = 1000000007
n = int(input())
p = ''.join([input() for _ in range(n)])
dp = [[0] * 5005 for _ in range(n + 1)]
dp[0][0] = 1
i = 1
for c in p:
	if c == 'f':
		for j in range(n - 1, -1, -1):
			dp[i][j] = dp[i - 1][j - 1] if j - 1 >= 0 else 0
	else:
		for j in range(n - 1, -1, -1):
			dp[i][j] = (dp[i - 1][j] + dp[i][j + 1]) % MOD
	i += 1
print(dp[n][0] % MOD)


n = int(input())
levels = [1]
for i in range(n):
	line = input()
	if line == 'f':
		levels.append(0)
	else:
		for j in range(1, len(levels)):
			levels[j] = (levels[j] + levels[j - 1]) % (10 ** 9 + 7)
print(levels[-1])


M = 10 ** 9 + 7
n = int(input())
a = []
for i in range(n):
	a.append(input())
dp = [[0] * (n + 5) for i in range(n + 2)]
dp[0][0] = 1
for i in range(1, n):
	count = 0
	if a[i - 1] == 'f':
		for j in range(n - 2, -1, -1):
			if dp[i - 1][j] > 0:
				dp[i][j + 1] = (dp[i][j + 1] + dp[i - 1][j]) % M
	else:
		for j in range(n - 2, -1, -1):
			if dp[i - 1][j] > 0:
				count = (count + dp[i - 1][j]) % M
			dp[i][j] = (dp[i][j] + count) % M
print(sum(dp[n - 1]) % M)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(200001)]
pp = [0] * 200001

def SieveOfEratosthenes(n=200000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
MOD = int(1000000000.0 + 7)
n = int(input())
a = [input() for i in range(n)]
dp = [1]
for i in range(n):
	if a[i] == 'f':
		dp.append(0)
		continue
	for j in range(1, len(dp)):
		dp[j] = (dp[j] + dp[j - 1]) % MOD
print(dp[-1])


import sys
input = sys.stdin.readlines()
n = int(input[0].strip())
m = 10 ** 9 + 7
curr = [0] * (n + 20)
last = [0] * (n + 20)
curr[0] = 1
for s in range(1, n):
	(last, curr) = (curr, last)
	if input[s] == 'f\n':
		curr[0] = 0
		for i in range(len(last) - 1):
			curr[i + 1] = last[i]
	elif input[s] == 's\n':
		curr[-1] = 0
		for i in range(len(last) - 2, -1, -1):
			curr[i] = (curr[i + 1] + last[i]) % m
s = 0
for x in curr:
	s = (s + x) % m
print(s)


MOD = 1000000007
n = int(input())
a = []
for _ in range(n):
	a.append(input())
dp = []
dp.append([1])
for i in range(1, n):
	if a[i - 1] == 'f':
		dp.append([0] + dp[i - 1])
	else:
		m = len(dp[i - 1])
		dp.append([0] * m)
		dp[-1][-1] = dp[i - 1][-1]
		for j in range(m - 2, -1, -1):
			dp[-1][j] = (dp[i - 1][j] + dp[i][j + 1]) % MOD
print(sum(dp[-1]) % MOD)


import sys
sys.setrecursionlimit(1000000)
read = sys.stdin.readline
MOD = 1000000007
N = int(read())
sts = [read().strip() for _ in range(N)]
ind = [0 for _ in range(N)]
ind[0] = 1
indent = 0
last = 'f'
for st in sts:
	if last != 'f':
		for i in range(indent, -1, -1):
			ind[i] += ind[i + 1]
			ind[i] %= MOD
	if st == 'f':
		indent += 1
		for i in range(indent, 0, -1):
			ind[i] += ind[i - 1]
			ind[i - 1] = 0
	last = st
ans = 0
for i in range(indent + 1):
	ans += ind[i]
	ans %= MOD
print(ans)


n = int(input())
ar = []
dp = [0] * 5005
cum = [0] * 5005
mod = int(1000000000.0 + 7)
for i in range(n):
	s = input()
	ar.append(s)
for i in range(5000):
	dp[i] = 1
	cum[i] = dp[i] + (cum[i - 1] if i > 0 else 0)
	cum[i] = cum[i] - mod if cum[i] >= mod else cum[i]
for i in range(n - 2, -1, -1):
	for j in range(5000):
		dp[j] = dp[j + 1] if ar[i] == 'f' else cum[j]
		dp[j] = dp[j] - mod if dp[j] >= mod else dp[j]
		cum[j] = dp[j] + (cum[j - 1] if j > 0 else 0)
		cum[j] = cum[j] - mod if cum[j] >= mod else cum[j]
print(dp[0])


n = int(input())
dp = [0] * 5000
MOD = 10 ** 9 + 7
f = 1
dp[0] = 1
for i in range(n):
	a = input()
	if a == 'f':
		f += 1
	else:
		for j in range(1, f):
			dp[j] = dp[j] + dp[j - 1]
			dp[j] %= MOD
print(dp[f - 1])


import sys
n = int(input())
statements = [input() for _ in range(n)]
if statements[-1] == 'f':
	print(0)
	sys.exist(0)
if n == 1:
	print(1)
	sys.exit(0)
max_level = [1] * n
idx = 1
for i in range(n):
	max_level[i] = idx
	if statements[i] == 'f':
		idx += 1
ways = [1] * max_level[-1]
mod = 10 ** 9 + 7
for i in range(1, n):
	if statements[n - 1 - i] == 's':
		ways[0] = ways[0] % mod
		for j in range(1, max_level[n - 1 - i]):
			ways[j] += ways[j - 1]
			ways[j] = ways[j] % mod
	else:
		for j in range(max_level[n - 1 - i]):
			ways[j] = ways[j + 1] % mod
print(ways[0])


L = int(1000000000.0 + 7)
N = int(input())
dp = [0 for _ in range(N)]
dp[0] = 1
index = 0
for _ in range(N):
	s = input()
	if s == 'f':
		index += 1
	if s == 's':
		for i in range(1, index + 1):
			dp[i] = (dp[i - 1] + dp[i]) % L
print(dp[index])


n = int(input())
MOD = 10 ** 9 + 7
ans = [0] * 5005
ans[0] = 1
indent = 1
for _ in range(n):
	c = input()
	if c == 'f':
		indent += 1
	else:
		for i in range(1, indent):
			ans[i] += ans[i - 1]
			ans[i] %= MOD
print(ans[indent - 1])


from sys import stdin, stdout
from collections import deque
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
PI = float('inf')
M = 10 ** 9 + 7
for _ in range(1):
	n = nmbr()
	s = [input() for _ in range(n)]
	dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	dp[0][0] = 1
	for i in range(1, n):
		for j in range(n):
			if i >= 1 and s[i - 1] == 'f':
				if j >= 1:
					dp[i][j] = dp[i - 1][j - 1] - dp[i - 1][j]
			elif i >= 1:
				dp[i][j] = dp[i - 1][j]
			dp[i][j] %= M
		for k in range(n - 1, -1, -1):
			dp[i][k] = (dp[i][k] + dp[i][k + 1]) % M
	print(dp[n - 1][0] % M)


n = int(input())
a = [input() for _ in range(n)]
MOD = int(1000000000.0 + 7)
const = 5001
levels = [0] * const
levels[0] = 1
for i in range(n - 1):
	if a[i] == 'f':
		for j in range(const - 2, -1, -1):
			levels[j + 1] = levels[j]
		levels[0] = 0
	else:
		cumsum = 0
		for j in range(const - 1, -1, -1):
			cumsum += levels[j]
			cumsum %= MOD
			levels[j] = cumsum
print(sum(levels) % MOD)


n = int(input())
dp = [0] * (n + 1)
maxlev = 0
mod = 1000000007
lst = 's'
dp[0] = 1
for i in range(n):
	s = input()
	if lst == 'f':
		for j in reversed(range(1, maxlev + 2)):
			dp[j] = dp[j - 1]
		maxlev += 1
		dp[0] = 0
	else:
		sum = 0
		for j in reversed(range(0, maxlev + 1)):
			sum = (sum + dp[j]) % mod
			dp[j] = sum
	lst = s
res = 0
for i in range(0, maxlev + 1):
	res = (res + dp[i]) % mod
print(res)


from sys import stdin, stdout, setrecursionlimit
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial, log2, floor
from bisect import bisect_right as br, bisect_left as bl
from heapq import *
mod = 10 ** 9 + 7

def solve():
	n = it()
	v = [0] * (n + 1)
	for i in range(1, n + 1):
		v[i] = input()
	dp = [[0] * (n + 2) for _ in range(n + 1)]
	for l in range(n + 2):
		dp[n][l] = 1
	for i in range(n - 1, 0, -1):
		curr_sum = 0
		for l in range(n):
			curr_sum += dp[i + 1][l]
			curr_sum %= mod
			if v[i] == 'f':
				dp[i][l] = dp[i + 1][l + 1]
			else:
				dp[i][l] = curr_sum
	print(dp[1][0])
solve()


n = int(input())
A = []
for i in range(n):
	x = input()
	A.append(x)
dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
mod = 10 ** 9 + 7
for i in range(n + 1):
	dp[n - 1][i] = 1
for line in range(n - 2, -1, -1):
	sum = 0
	if A[line] == 's':
		for indent in range(n):
			sum = (sum + dp[line + 1][indent]) % mod
			dp[line][indent] = sum
	else:
		for indent in range(n):
			dp[line][indent] = dp[line + 1][indent + 1]
print(dp[0][0])


n = int(input())

def prefix_sums(A):
	n = len(A)
	P = [0] * n
	P[0] = A[0]
	for k in range(1, n):
		P[k] = int((P[k - 1] + A[k]) % (1000000000.0 + 7))
	return P
arr = [[0] * n for _ in range(n)]
s = ''
for i in range(n):
	inst = input()
	s += inst

def find_ans():
	idx = 0
	for i in range(len(arr) - 1):
		arr[0][0] = 1
		if s[i] == 'f':
			for j in range(0, len(arr)):
				arr[i + 1][0] = 0
				if j > 0:
					arr[i + 1][j] = arr[i][j - 1]
					idx = i + 1
		else:
			val = 0
			arr[i + 1] = prefix_sums(arr[i][::-1])[::-1]
	return arr
if n == 1 or 'f' not in s:
	if s[0] == 's':
		print(1)
	else:
		print(int(sum(find_ans()[-1]) % (1000000000.0 + 7)))
else:
	print(int(sum(find_ans()[-1]) % (1000000000.0 + 7)))


n = int(input())
b = []
for j in range(n):
	b.append(input())
ans = 1
j = 0
res = 1
p = 10 ** 9 + 7
dp = [0] * n
dp[0] = 1
while j < n:
	if b[j] == 'f':
		res += 1
	else:
		for i in range(1, res):
			dp[i] = (dp[i] + dp[i - 1]) % p
	j += 1
print(dp[res - 1] % p)


n = int(input().rstrip())
arr = []
mod = pow(10, 9) + 7
indent_num = 0
for i in range(n):
	arr.append(input().rstrip())
	if arr[i] == 'f':
		indent_num += 1
dp = [0 for i in range(indent_num + 1)]
max_indent = 0
cur_indent = 0
pref = [0 for i in range(indent_num + 1)]

def cal_pref(dp, pref):
	pref[0] = dp[0]
	for i in range(1, len(dp)):
		pref[i] = pref[i - 1] + dp[i]
for i in range(n):
	if arr[i] == 'f':
		cur_indent += 1
		max_indent += 1
		continue
	cur = [0 for i in range(indent_num + 1)]
	cal_pref(dp, pref)
	for j in range(cur_indent, indent_num + 1):
		res_idx = j - cur_indent
		res_result = pref[res_idx - 1] if res_idx > 0 else 0
		cur[j] = (pref[indent_num] - res_result) % mod
	cur[max_indent] = 1 if not cur[max_indent] else cur[max_indent]
	dp = cur
	cur_indent = 0
print(sum(dp) % mod)


def add(x, j):
	x = x % (1000000000 + 7)
	j = j % (1000000000 + 7)
	return (x + j) % (1000000000 + 7)
statements = []
n = int(input())
i = 1
j = 1
temp = [[0 for i in range(n)] for i in range(n)]
earlier = [[0 for i in range(n)] for i in range(n)]
temp[0][0] = 1
earlier[0][0] = 1
while i <= n:
	s = input()
	statements.append(s)
	i += 1
while j < n:
	temp[0][j] = 0
	earlier[0][j] = temp[0][j] + earlier[0][j - 1]
	j += 1
i = 1
while i < n:
	if statements[i - 1] == 'f':
		j = 1
		while j < n:
			temp[i][0] = 0
			earlier[i][0] = 0
			temp[i][j] = temp[i - 1][j - 1]
			earlier[i][j] = add(earlier[i][j - 1], temp[i][j])
			j += 1
	else:
		j = 0
		while j < n:
			if j == 0:
				temp[i][j] = earlier[i - 1][n - 1]
			else:
				temp[i][j] = earlier[i - 1][n - 1] - earlier[i - 1][j - 1]
			earlier[i][j] = add(earlier[i][j - 1], temp[i][j])
			j += 1
	i += 1
ans = 0
j = 0
while j < n:
	ans = add(ans, temp[n - 1][j])
	j += 1
print(ans % (1000000000 + 7))


n = int(input())
mod = 10 ** 9 + 7
dp = [0 for i in range(10000)]
dp[0] = 1
pos = 1
for i in range(n):
	x = input()
	if x == 's':
		for j in range(1, pos):
			dp[j] = dp[j - 1] + dp[j]
			dp[j] %= mod
	else:
		pos += 1
print(dp[pos - 1])


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	arr = [input().strip() for _ in range(n)]
	(mod, i, arr1) = (10 ** 9 + 7, 0, [])
	while i != n:
		if arr[i] == 'f':
			cnt = 0
			while i != n and arr[i] == 'f':
				cnt += 1
				i += 1
			arr1.append(cnt)
		else:
			arr1.append(0)
		i += 1
	(x, y) = (len(arr1), sum(arr1))
	dp = [[0] * (y + 1) for _ in range(x + 1)]
	dp[0][0] = 1
	for i in range(1, x + 1):
		j = 0
		for k in range(y, arr1[i - 1] - 1, -1):
			j = (j + dp[i - 1][k - arr1[i - 1]]) % mod
			dp[i][k] = j
	ans = 0
	for i in dp[-1]:
		ans = (ans + i) % mod
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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

def summ(a, mod):
	ans = 0
	for i in range(len(a)):
		ans += a[i]
		ans %= mod
	return ans
for i in range(1, n):
	sm = summ(dp[i - 1], 10 ** 9 + 7)
	for j in range(n):
		if s[i - 1] == 'f':
			if j == 0:
				dp[i][j] = 0
			else:
				dp[i][j] = dp[i - 1][j - 1] % (10 ** 9 + 7)
		else:
			dp[i][j] = sm
			sm = (sm - dp[i - 1][j] + 10 ** 9 + 7) % (10 ** 9 + 7)
print(summ(dp[n - 1], 10 ** 9 + 7))


import bisect

def list_output(s):
	print(' '.join(map(str, s)))

def list_input(s='int'):
	if s == 'int':
		return list(map(int, input().split()))
	elif s == 'float':
		return list(map(float, input().split()))
	return list(map(str, input().split()))
n = int(input())
MOD = int(1000000000.0) + 7
seq = list()
for i in range(n):
	seq.append(list(map(str, input().split()))[0])
dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	ps = [0 for j in range(n + 1)]
	for j in range(n):
		ps[j + 1] = (ps[j] + dp[i][j]) % MOD
	for j in range(n):
		if i > 0 and seq[i - 1] == 'f':
			dp[i + 1][j + 1] += dp[i][j]
			dp[i + 1][j + 1] %= MOD
		else:
			dp[i + 1][j] += ps[n] - ps[j]
res = 0
for i in range(n + 1):
	res += dp[n][i]
	res %= MOD
print(res)


import os, sys, atexit
inputs = []
dp = [[0] * 5002 for _ in range(5002)]

def solve():
	n = int(input())
	for _ in range(n):
		inputs.append(input())
	for i in range(n - 1, -1, -1):
		for level in range(1, n + 1):
			ans = 0
			if inputs[i] == 'f':
				ans = dp[level + 1][i + 1] - dp[level][i + 1]
			else:
				ans = max(1, dp[level][i + 1])
			dp[level][i] = (ans + dp[level - 1][i]) % 1000000007
	print(dp[1][0])
try:
	solve()
except Exception as e:
	print(e)


n = int(input())
dp = [1] + [0] * n
p = input()
for _ in range(n - 1):
	if p == 'f':
		dp = [0] + dp[:n - 1]
	else:
		for i in range(n - 2, -1, -1):
			dp[i] = (dp[i] + dp[i + 1]) % (10 ** 9 + 7)
	p = input()
print(sum(dp) % (10 ** 9 + 7))