Chef loves arrays. But he really loves a specific kind of them - Rainbow Arrays. 
The array is a Rainbow Array if it has such a structure:
- The first a1 elements equal to 1. 
- The next a2 elements equal to  2. 
- The next a3 elements equal to  3. 
- The next a4 elements equal to  4. 
- The next a5 elements equal to  5. 
- The next a6 elements equal to  6. 
- The next a7 elements equal to  7. 
- The next a6 elements equal to  6. 
- The next a5 elements equal to  5. 
- The next a4 elements equal to  4. 
- The next a3 elements equal to  3. 
- The next a2 elements equal to  2. 
- The next a1 elements equal to  1. 
- ai is a positive integer, the variables with the same index (a1 in the first statement and a1 in the last one, for example) are equal. 
- There are no any other elements in array. 

For example, {1,1,2,2,2,3,4,5,5,6,7,7,7,6,5,5,4,3,2,2,2,1,1} is a Rainbow Array.

The array {1,2,3,4,5,6,7,6,6,5,4,3,2,1} is not a Rainbow Array, because the sizes of the blocks with the element 6 are different. 
Please help Chef to count the number of different Rainbow Arrays that contain exactly N elements. 

-----Input-----
The first line contains a single integer N. 

-----Output-----
Output the number of different Rainbow Arrays with N elements, modulo 10^9+7. 

-----Constraints-----
- 1 ≤ N ≤ 106

-----Example-----
Input #1:
10 

Output #1:
0

Input #2:
13

Output #2:
1

Input #3:
14

Output #3:
1

Input #4:
15

Output #4:
7

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
def modulo(p, q, r):
	x = 1
	y = p
	while q > 0:
		if q % 2 == 1:
			x = y * x % r
		y = y * y % r
		q /= 2
		q = int(q)
	return x % r
mod = 1000000007
n = input()
n = int(n)
n = (n - 1) / 2
n = int(n)
ans = modulo(n, 6, mod) - 15 * modulo(n, 5, mod) + 85 * modulo(n, 4, mod) - 225 * modulo(n, 3, mod) + 274 * modulo(n, 2, mod) - 120 * n
ans = ans % mod
ans = ans * modulo(720, mod - 2, mod)
ans %= mod
ans = int(ans)
ans = ans % 1000000007
print(ans)


import operator as op
import functools

def ncr(n, r):
	r = min(r, n - r)
	if r == 0:
		return 1
	numer = functools.reduce(op.mul, range(n, n - r, -1))
	denom = functools.reduce(op.mul, range(1, r + 1))
	return numer // denom
n = int(input())
diff = int(n - 13)
if diff < 0:
	print('0')
else:
	sum1 = ncr(7 + int(diff / 2) - 1, int(diff / 2))
	print(sum1 % 1000000007)


n = int(input())
n = n - 13
if n <= 0:
	if n == 0:
		print(1)
	else:
		print(0)
else:
	n = n // 2
	f = 1
	for x in range(1, 7):
		f *= x
	ans = 1
	n = n + 6
	for x in range(6):
		ans *= n
		n -= 1
	ans = ans // f
	ans = ans % 1000000007
	print(ans)


M = 1000000007

def factr(n, prod):
	p = 1
	st2 = 0
	st3 = 0
	st4 = 0
	st5 = 0
	st6 = 0
	for i in range(0, 6):
		p = n - i
		if p % 6 == 0 and st6 == 0:
			p /= 6
			st6 = 1
		if p % 5 == 0 and st5 == 0:
			p /= 5
			st5 = 1
		if p % 4 == 0 and st4 == 0:
			p /= 4
			st4 = 1
		if p % 3 == 0 and st3 == 0:
			p /= 3
			st3 = 1
		if p % 2 == 0 and st2 == 0:
			p /= 2
			st2 = 1
		p = p % M
		prod.append(int(p))
n = int(input())
if n < 13:
	print(0)
else:
	if n % 2 == 1:
		n += 1
	n = int(n / 2)
	k = n - 1
	prod = []
	m = 1
	factr(k, prod)
	for i in prod:
		m = m * i % M
	print(m)


from math import factorial

def nbCombinations(n):
	return n * (n - 1) * (n - 2) * (n - 3) * (n - 4) // factorial(5)
M = 10 ** 9 + 7

def solve(N):
	first = 1 if N % 2 == 1 else 2
	res = 0
	for a7 in range(first, N - 12 + 1, 2):
		half = (N - a7) // 2
		res = (res + nbCombinations(half - 1) % M) % M
	return res
N = int(input())
print(solve(N))


n = int(input())

def comb(n, r):
	r = min(r, n - r)
	num = 1
	den = 1
	for i in range(1, r + 1):
		den = den * i
	for i in range(n, n - r, -1):
		num = num * i
	return num // den
ans = 0
modulo = int(1000000000.0) + 7
for i in range(1, n + 1):
	noOfa7 = i
	rem = n - noOfa7
	if rem % 2 == 0:
		k = rem // 2
		if k >= 6:
			ans = (ans % modulo + comb(k - 1, 5) % modulo) % modulo
print(ans)


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

def solve(a):
	ab2 = a / 2
	return nC5(ab2 - 1)

def nC5(k):
	res = (k - 4) * k * (k - 1) * (k - 2) * (k - 3)
	res = res / 120
	return res
if n < 13:
	print(0)
elif n == 13:
	print(1)
else:
	a7Max = n - 12 + 1
	if n % 2 == 1:
		ans = 0
		for a7 in range(1, a7Max, 2):
			rest = n - a7
			ans += solve(rest)
			ans = ans % mod
		print(ans % mod)
	else:
		ans = 0
		for a7 in range(2, a7Max, 2):
			rest = n - a7
			ans += solve(rest)
			ans = ans % mod
		print(ans % mod)


n = int(input())
m = int(n / 2)
if n % 2 == 0:
	w = (m - 6) * (m - 5) * (m - 4) * (m - 3) * (m - 2) * (m - 1)
else:
	w = (m - 5) * (m - 4) * (m - 3) * (m - 2) * (m - 1) * m
if n < 13:
	w = 0
w = w // 720
w = w % 1000000007
print(int(w))


MODULO = 1000000007

def main():
	n = int(input())
	tot_ans = 0
	for a7 in range(1, n - 11):
		k = n - a7
		if not k % 2 == 0:
			continue
		k = k / 2
		ans = (k - 1) * (k - 2) * (k - 3) * (k - 4) * (k - 5)
		ans = ans / 120
		ans = ans % MODULO
		tot_ans = (tot_ans + ans) % MODULO
	print(str(tot_ans))

def __starting_point():
	main()
__starting_point()


def ncr(n, r):
	k = 1
	for i in range(r):
		k = k * (n - i)
	for i in range(1, r + 1):
		k = k // i
	return k
n = int(input())
if n < 13:
	print('0')
elif n % 2 == 0:
	n = int(n / 2)
	ans = int(ncr(n - 1, 6))
	ans = ans % 1000000007
	print(str(ans))
else:
	n = int(n / 2)
	ans = int(ncr(n, 6))
	ans = ans % 1000000007
	print(str(ans))


__author__ = 'Tanay Jha'
n = int(input())
x = int((n - 13) / 2)
ans = int((x + 1) * (x + 2) * (x + 3) * (x + 4) * (x + 5) * (x + 6))
ans //= 720
print(ans % 1000000007)


import math
import sys
from collections import Counter, defaultdict
from bisect import bisect_left
mod = 1000000007

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

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())

def main():
	try:
		if n < 13:
			print(0)
		elif n == 14 or n == 13:
			print(1)
		else:
			objects = (n - 13) // 2
			reciver = 7
			ans = 1
			for i in range(1, 7):
				ans *= objects + i
			ans = ans // 720
			ans %= mod
			print(ans)
	except Exception as e:
		print(e)
for _ in range(1):
	n = int(input())
	main()


def combi(n, r):
	r = min(r, n - r)
	ans = 1
	for i in range(1, r + 1):
		ans *= n
		n -= 1
	for i in range(2, r + 1):
		ans = ans // i
	ans = ans % 1000000007
	return ans
n = int(input())
if n < 13:
	print('0')
else:
	n = (n - 13) // 2
	print(combi(n + 6, 6))


def cal_coeff(n):
	coeff = [1]
	for k in range(7):
		coeff.append(coeff[k] * (n - k) // (k + 1))
	return coeff
arr = [1, 6, 15, 20, 15, 6, 1]
mod = 10 ** 9 + 7
n = int(input())
if n % 2 == 0:
	n -= 1
if n < 13:
	ans = 0
else:
	ch = (n - 1) // 2 - 6
	ans = 0
	coeff = cal_coeff(ch)
	r = ch + 1 if ch < 7 else 7
	for i in range(r):
		ans += coeff[i] * arr[i] % mod
print(ans % mod)


x = int(input(''))
ans = 0
if x < 13:
	ans = 0
if x >= 13:
	if x % 2 == 0:
		x = int(x - 2)
	if x % 2 == 1:
		x = int(x - 1)
	x = x // 2
	ans = x * (x - 1) * (x - 2) * (x - 3) * (x - 4) * (x - 5) // 720
	ans = int(ans % 1000000007)
print('', ans)


import sys

def modInverse(n, MOD):
	return pow(n, MOD - 2, MOD)

def choose(n, k, m):
	N = 1
	D = 1
	for i in range(k):
		N = N * (n - i) % m
	for i in range(1, k + 1):
		D = D * i % m
	return N * modInverse(D, m) % m
n = int(sys.stdin.readline())
n = n + 1 >> 1
print(choose(n - 1, 6, 10 ** 9 + 7))


n = int(input()) - 12
val = 0
for a7 in range(1 if n % 2 == 1 else 2, n + 1, 2):
	m = (n - a7) // 2
	val += (m + 5) * (m + 4) * (m + 3) * (m + 2) * (m + 1) // 120
print(val % 1000000007)


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def alg(N):
	res = 0
	B = 6
	while True:
		C = N - 2 * B
		if C >= 1:
			v = B - 6
			res += pow(6, v, 1000000007)
		else:
			break
		B += 1
	return res

def alg2(N):
	res = 0
	B = 6
	while True:
		C = N - 2 * B
		if C >= 1:
			res += math.factorial(B - 6 + 6 - 1) // (math.factorial(B - 6) * math.factorial(6 - 1))
			res %= 1000000007
		else:
			break
		B += 1
	return res

def alg3(N):
	res = 0
	B = 6
	nominator = math.factorial(5)
	denom1 = nominator
	nd = 1
	while True:
		C = N - 2 * B
		if C >= 1:
			res += nd
			res %= 1000000007
		else:
			break
		B += 1
		nd *= B - 1
		nd //= B - 6
	return res

def alg4(N):
	MOD = 1000000007
	res = 0
	B = 6
	nd = 1
	C = N - 2 * B
	while True:
		if C >= 1:
			res += nd
		else:
			break
		nd *= B
		nd //= B - 5
		B += 1
		C -= 2
	return res % MOD

def main():
	data = sys.stdin
	nb = int(data.readline())
	print(alg3(nb))
main()


i = int(input())
if i < 13:
	print(0)
if i >= 13:
	i = int((i - 1) / 2)
	d = 1
	for k in range(0, 6):
		d = d * (i - k) % 1000000007
	d = d * 301388891 % 1000000007
	print(int(d))


n = int(input())
if n < 13:
	print('0')
elif n == 13 or n == 14:
	print('1')
else:
	diff = (n - 13) // 2
	big = diff + 6
	if diff > 6:
		val = 6
		diff = 6
	else:
		val = diff
	(ans, ans1) = (1, 1)
	for x in range(val):
		ans = ans * big
		big = big - 1
		ans1 = ans1 * diff
		diff = diff - 1
	print(ans // ans1 % 1000000007)


a = int(input())
a = a - 13
a = a // 2
if a < 0:
	print(0)
elif a == 0:
	print(1)
else:
	n = a + 6
	t = 1
	for i in range(a + 1, n + 1):
		t = t * i
	t = t // 720
	print(t % 1000000007)


MOD = 10 ** 9 + 7
n = int(input())
n = (n - 1) // 2
wyn = (n ** 6 - 15 * n ** 5 + 85 * n ** 4 - 225 * n ** 3 + 274 * n ** 2 - 120 * n) // 720
print(wyn % MOD)


n = int(input())
if n < 13:
	print(0)
else:
	n = (n - 13) // 2 + 6
	r = 7 - 1
	mod = 10 ** 9 + 7
	ans = n * (n - 1) * (n - 2) * (n - 3) * (n - 4) * (n - 5) // 720
	print(ans % mod)


def ncr(n, r):
	if r < 0 or r > n:
		return 0
	numerator = (n - 4) * (n - 3) * (n - 2) * (n - 1) * n
	denominator = 120
	return numerator // denominator
modulo = 1000000000 + 7
N = int(input())
ans = 0
if N % 2 == 0:
	a7 = 2
else:
	a7 = 1
while N - a7 > 11:
	n = (N - a7) // 2
	n -= 6
	ans += ncr(6 + n - 1, n)
	a7 += 2
print(ans % modulo)


import sys
n = int(sys.stdin.readline())
sum = 0
for a7 in range(1, n - 11):
	if (n - a7) % 2 == 1:
		continue
	k = (n - a7) / 2 - 6
	res = (k + 5) * (k + 4) * (k + 3) * (k + 2) * (k + 1)
	res /= 120
	res %= 1000000007
	sum += res
	sum %= 1000000007
print(str(sum))


n = int(input())
ans = 0
if n % 2 == 1:
	for i in range(1, n - 11, 2):
		t = (n - i) // 2
		t -= 1
		if t < 5:
			break
		ans += t * (t - 1) * (t - 2) * (t - 3) * (t - 4) // 120
else:
	for i in range(2, n - 11, 2):
		t = (n - i) // 2
		t -= 1
		if t < 5:
			break
		ans += t * (t - 1) * (t - 2) * (t - 3) * (t - 4) // 120
ans %= 1000000007
print(int(ans))


def C(n, k):
	ans = 1
	for i in range(n, n - k, -1):
		ans *= i
	for i in range(1, k + 1):
		ans //= i
	return ans % (10 ** 9 + 7)
n = int(input().split()[0])
if n % 2:
	print(C(n // 2, 6))
else:
	print(C(n // 2 - 1, 6))