One day John had to take care of his little nephew Jim. He was very busy, so he gave Jim a big bag full of building bricks. The bricks are of various heights: at most 15 different heights. For each height, the bag contains infinitely many bricks. 

Now, Jim’s task is to build every possible tower of height $N$ from the given bricks. Bricks are stacked vertically only and stand in an upright position. Two towers are different if their brick height sequences are different.

Jim is good at building towers and can build one tower in exactly 2 minutes, regardless of its height. John wants to know the time Jim requires to build all possible towers.  

Input Format 

There are $3$ lines of input. First line contains an integer, $N$, the height of tower to be built. Second line contains another integer, $\mbox{K}$, which represents different heights of bricks available in the bag. Third line contains $\mbox{K}$ distinct integers representing the available heights.  

Output Format 

In one line print the number of minutes Jim requires to build all possible towers. As this number can be very large, print the number modulo $(10^9+7)$.  

Constraints 

$1\leq N\leq10^{18}$ 

$1\leq K\leq15$ 

All heights will be unique. 

Height of each brick will lie in range [1, 15].  

Sample Input#00

10
1
1

Sample Output#00  

2

Explanation#00:  There is exactly one type of brick, so there is exactly one tower of height 10. Building any tower takes 2 minutes, so the answer is 2.

Sample Input#01  

5
2
2 3

Sample Output#01  

4

Explanation #01: There are two types of bricks. There are two different towers of height 5 which can be build from these types of bricks: $[2,3]$ and $[3,2]$. They are different, because the sequence of bricks in them is different. Building any tower takes 2 minutes, so the answer is $2\times2=4$.

Sample Input#03  

19
2
4 5

Sample Output#03

8

Explanation #03: There are two types of bricks. Jim can build 4 different towers of height $19$ from these bricks: $[5,5,5,4]$, $[5,5,4,5]$, $[5,4,5,5]$ and $[4,5,5,5]$. Building any tower takes 2 minutes, so the answer is $2\times4=8$.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Starter code:

Solutions:
MOD = 10 ** 9 + 7

def mul(A, B):
	return [[sum([A[i][k] * B[k][j] for k in range(len(A[0]))]) % MOD for j in range(len(B[0]))] for i in range(len(A))]

def pow(A, e):
	P = [[1 if i == j else 0 for j in range(len(A[0]))] for i in range(len(A))]
	while e > 0:
		if e & 1:
			P = mul(P, A)
		A = mul(A, A)
		e >>= 1
	return P
N = int(input())
K = int(input())
Ks = [int(_) for _ in input().split()]
A = [[1 if j == i + 1 else 0 for j in range(16)] for i in range(16)]
for k in Ks:
	A[k - 1][0] = 1
P = pow(A, N)
print(2 * P[0][0] % MOD)


MOD = 10 ** 9 + 7

def multiply(A, B):
	R = len(A)
	K = len(B)
	C = len(B[0])
	return [[sum((A[r][k] * B[k][c] for k in range(K))) % MOD for c in range(C)] for r in range(R)]

def identity(D):
	return [[1 if r == c else 0 for c in range(D)] for r in range(D)]

def exponentiate(A, n):
	B = A
	C = identity(len(A))
	while n:
		if n % 2:
			C = multiply(C, B)
		B = multiply(B, B)
		n //= 2
	return C
N = int(input())
int(input())
H = tuple(map(int, input().split()))
R = C = 16
M = [[0 for c in range(C)] for r in range(R)]
for c in range(C - 1):
	M[c + 1][c] = 1
for h in H:
	M[-h][-1] = 1
DP = [1 if i == 0 else 0 for i in range(R)]
for i in range(1, len(DP)):
	for h in H:
		if h <= i:
			DP[i] += DP[i - h]
print(2 * multiply([DP], exponentiate(M, N))[0][0] % MOD)


from copy import copy
m = 10 ** 9 + 7

def matPow(A, n):
	C = [[0] * len(A) for i in range(len(A))]
	for i in range(len(A)):
		C[i][i] = 1
	while n:
		if n & 1:
			C = matMult(C, A)
		A = matMult(A, A)
		n >>= 1
	return C

def matMult(A, B):
	C = [[0] * len(B[0]) for i in range(len(A))]
	for i in range(len(A)):
		for k in range(len(B[0])):
			for j in range(len(B)):
				C[i][k] += A[i][j] * B[j][k]
				C[i][k] %= m
	return C

def f(n, B):
	mat = [[0] * 20 for i in range(20)]
	for i in range(1, 20):
		mat[i][i - 1] = 1
	for b in B:
		mat[0][b - 1] = 1
	a = [[0] for i in range(20)]
	a[0][0] = 1
	return matMult(matPow(mat, n), a)[0][0]
n = int(input())
k = int(input())
B = [int(i) for i in input().split()]
print(2 * f(n, B) % m)


import sys
MOD = 1000000007
MAX = 15

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
DIM = max(A)
M = [[int(i + 1 in A) for i in range(DIM)]]
for i in range(1, DIM):
	x = [0] * DIM
	x[i - 1] = 1
	M.append(x)
X = [[int(i == j) for j in range(DIM)] for i in range(DIM)]
while N > 0:
	if N % 2 == 1:
		X = matrix_mult(X, M)
	M = matrix_mult(M, M)
	N //= 2
print(2 * X[0][0] % MOD)


import sys
MOD = 1000000007
MAX = 15

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
DIM = max(A)
M = [[int(i + 1 in A) for i in range(DIM)]]
for i in range(1, DIM):
	x = [0] * DIM
	x[i - 1] = 1
	M.append(x)
X = [[int(i == j) for j in range(DIM)] for i in range(DIM)]
while N > 0:
	if N % 2 == 1:
		X = matrix_mult(X, M)
	M = matrix_mult(M, M)
	N //= 2
print(2 * X[0][0] % MOD)


import sys
MOD = 1000000007
MAX = 15

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
DIM = max(A)
M = [[int(i + 1 in A) for i in range(DIM)]]
for i in range(1, DIM):
	x = [0] * DIM
	x[i - 1] = 1
	M.append(x)
X = [[int(i == j) for j in range(DIM)] for i in range(DIM)]
while N > 0:
	if N % 2 == 1:
		X = matrix_mult(X, M)
	M = matrix_mult(M, M)
	N //= 2
print(2 * X[0][0] % MOD)


import sys
MOD = 1000000007
MAX = 15

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
n = max(A)
M = [[int(i + 1 in A) for i in range(n)]]
for i in range(1, n):
	x = [0] * n
	x[i - 1] = 1
	M.append(x)
exp = {1: [x[:] for x in M]}
k = 1
while k < N:
	i = max((j for j in exp if j <= N - k))
	M = matrix_mult(M, exp[i])
	k += i
	exp[k] = [x[:] for x in M]
print(2 * M[0][0] % MOD)


import sys
MOD = 1000000007
MAX = 15

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
DIM = max(A)
M = [[int(i + 1 in A) for i in range(DIM)]]
for i in range(1, DIM):
	x = [0] * DIM
	x[i - 1] = 1
	M.append(x)
X = [[int(i == j) for j in range(DIM)] for i in range(DIM)]
while N > 0:
	if N % 2 == 1:
		X = matrix_mult(X, M)
	M = matrix_mult(M, M)
	N //= 2
print(2 * X[0][0] % MOD)


MOD = 1000000007
MAX = 15

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]
N = int(input())
K = int(input())
A = list(map(int, input().split()))
n = max(A)
M = [[int(i + 1 in A) for i in range(n)]]
for i in range(1, n):
	x = [0] * n
	x[i - 1] = 1
	M.append(x)
exp = {1: [x[:] for x in M]}
k = 1
while k < N:
	i = max((j for j in exp if j <= N - k))
	M = matrix_mult(M, exp[i])
	k += i
	exp[k] = [x[:] for x in M]
print(2 * M[0][0] % MOD)


mod = 10 ** 9 + 7
N = int(input())
K = int(input())
A = [int(x) for x in input().split()]
s = max(A)

def mul(a, b):
	return [[sum((a[i][k] * b[k][j] for k in range(s))) % mod for j in range(s)] for i in range(s)]
m = [[0] * s for i in range(s)]
for i in range(s - 1):
	m[i + 1][i] = 1
for x in A:
	m[0][x - 1] = 1
b = [[0] * s for i in range(s)]
for i in range(s):
	b[i][i] = 1
while N:
	if N & 1:
		b = mul(b, m)
	m = mul(m, m)
	N >>= 1
print(2 * b[0][0] % mod)


def fastMult(m, B):
	r = 1
	M = tuple([tuple(b) for b in B])
	old = [M]
	while True:
		if m == 0:
			return old[-1]
		if m < 2 * r:
			break
		r *= 2
		M = matM(M, M)
		old.append(M)
	i = 1
	C = [[0 for m in range(len(B))] for n in range(len(B))]
	for j in range(len(B)):
		C[j][j] = 1
	m -= r
	while m > 0:
		if m >= r:
			m -= r
			M = matM(M, old[-i])
		r //= 2
		i += 1
	return M

def matM(A, B):
	L = len(A)
	R = []
	MOD = 10 ** 9 + 7
	for i in range(L):
		X = []
		for j in range(L):
			s = 0
			for k in range(L):
				s += A[i][k] * B[k][j] % MOD
			X.append(s)
		R.append(X)
	return R

def solveC(m, A):
	MOD = 10 ** 9 + 7
	M = max(A)
	B = [[0 for i in range(M)] for j in range(M)]
	for i in range(M - 1):
		B[i + 1][i] = 1
	for a in A:
		B[-a][-1] = 1
	C = [[0 for i in range(M)] for j in range(M)]
	C[0][-1] = 1
	M = fastMult(m, B)
	C = matM(C, M)
	print(C[0][-1] * 2 % MOD)
m = int(input())
input()
A = [int(a) for a in input().split()]
solveC(m, A)


import math
import os
import random
import re
import sys
MOD = 1000000007
MAX = 15

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
DIM = max(A)
M = [[int(i + 1 in A) for i in range(DIM)]]
for i in range(1, DIM):
	x = [0] * DIM
	x[i - 1] = 1
	M.append(x)
X = [[int(i == j) for j in range(DIM)] for i in range(DIM)]
while N > 0:
	if N % 2 == 1:
		X = matrix_mult(X, M)
	M = matrix_mult(M, M)
	N //= 2
print(2 * X[0][0] % MOD)


import itertools

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % 1000000007 for B_col in zip(*B)] for A_row in A]

def solve(n, heights):
	m = max(heights)
	M = [[int(i + 1 in heights) for i in range(m)]]
	for i in range(1, m):
		temp = [0] * m
		temp[i - 1] = 1
		M.append(temp)
	X = [[int(i == j) for j in range(m)] for i in range(m)]
	while n > 0:
		if n % 2 == 1:
			X = matrix_mult(X, M)
		M = matrix_mult(M, M)
		n //= 2
	return 2 * X[0][0] % 1000000007
n = int(input().strip())
heights_count = int(input().strip())
heights = list(map(int, input().rstrip().split()))
result = solve(n, heights)
print(str(result))


MOD = 10 ** 9 + 7

def mul(A, B):
	return [[sum([A[i][k] * B[k][j] for k in range(len(A[0]))]) % MOD for j in range(len(B[0]))] for i in range(len(A))]

def pow(A, e):
	P = [[1 if i == j else 0 for j in range(len(A[0]))] for i in range(len(A))]
	while e > 0:
		if e & 1:
			P = mul(P, A)
		A = mul(A, A)
		e >>= 1
	return P
N = int(input())
K = int(input())
Ks = [int(_) for _ in input().split()]
A = [[1 if j == i + 1 else 0 for j in range(16)] for i in range(16)]
for k in Ks:
	A[k - 1][0] = 1
P = pow(A, N)
print(2 * P[0][0] % MOD)


import sys
MOD = 1000000007
MAX = 15

def matrix_mult(A, B):
	return [[sum((a * b for (a, b) in zip(A_row, B_col))) % MOD for B_col in zip(*B)] for A_row in A]
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
DIM = max(A)
M = [[int(i + 1 in A) for i in range(DIM)]]
for i in range(1, DIM):
	x = [0] * DIM
	x[i - 1] = 1
	M.append(x)
X = [[int(i == j) for j in range(DIM)] for i in range(DIM)]
while N > 0:
	if N % 2 == 1:
		X = matrix_mult(X, M)
	M = matrix_mult(M, M)
	N //= 2
print(2 * X[0][0] % MOD)


MOD = 10 ** 9 + 7

def mul(A, B):
	return [[sum([A[i][k] * B[k][j] for k in range(len(A[0]))]) % MOD for j in range(len(B[0]))] for i in range(len(A))]

def pow(A, e):
	P = [[1 if i == j else 0 for j in range(len(A[0]))] for i in range(len(A))]
	while e > 0:
		if e & 1:
			P = mul(P, A)
		A = mul(A, A)
		e >>= 1
	return P
N = int(input())
K = int(input())
Ks = [int(_) for _ in input().split()]
A = [[1 if j == i + 1 else 0 for j in range(16)] for i in range(16)]
for k in Ks:
	A[k - 1][0] = 1
P = pow(A, N)
print(2 * P[0][0] % MOD)