Chef is given a sequence of prime numbers $A_1, A_2, \ldots, A_N$. This sequence has exactly $2^N$ subsequences. A subsequence of $A$ is good if it does not contain any two identical numbers; in particular, the empty sequence is good.
Chef has to find the number of good subsequences which contain at most $K$ numbers. Since he does not know much about subsequences, help him find the answer. This number could be very large, so compute it modulo $1,000,000,007$.

-----Input-----
- The first line of the input contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
Print a single line containing one integer ― the number of good subsequences with size at most $K$, modulo $1,000,000,007$.

-----Constraints-----
- $1 \le K \le N \le 10^5$
- $2 \le A_i \le 8,000$ for each valid $i$

-----Subtasks-----
Subtask #1 (40 points): $A_1, A_2, \ldots, A_N$ are pairwise distinct
Subtask #2 (60 points): original constraints

-----Example Input-----
5 3
2 2 3 3 5

-----Example Output-----
18

-----Explanation-----
There is $1$ good subsequence with length $0$, $5$ good subsequences with length $1$, $8$ good subsequences with length $2$ and $4$ good subsequences with length $3$.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Combinatorics

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
from collections import Counter
from itertools import accumulate
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ctr = Counter(a)
st = list(set(a))
l = len(st)
k = min(k, l)
m = list(accumulate([ctr[i] for i in st]))
ans = 0
for i in range(2, k + 1):
	temp = []
	for j in range(l):
		if j >= i - 1:
			ans += m[j - 1] * ctr[st[j]]
			temp.append(m[j - 1] * ctr[st[j]] + temp[-1])
		else:
			temp.append(0)
	m = temp
print((ans + sum(ctr.values()) + 1) % (10 ** 9 + 7))


import collections
import math

def CountFrequency(a):
	return collections.Counter(a)

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def sub(a, k, n):
	f = [0] * n
	f[0] = n
	for i in range(1, n, 1):
		for h in range(i, 0, -1):
			f[h] = f[h] + a[i] * f[h - 1]
	return f

def su(n, k, a, dp, hell, heave):
	if k == -1:
		return 1
	if n == -1:
		return 0
	if n <= hell and k <= heave:
		if dp[n][k] != -1:
			return dp[n][k]
	else:
		return 0
	ans1 = 0
	ans2 = 0
	ans1 = a[n] * su(n - 1, k - 1, a, dp, hell, heave)
	ans2 = su(n - 1, k, a, dp, hell, heave)
	if n <= hell and k <= heave:
		dp[n][k] = int(ans1 + ans2)
	sol = ans2 + ans1
	return int(sol)

def vi(roots, n, k):
	coeff = [0] * (n + 1)
	coeff[n] = 1
	for i in range(1, n + 1):
		for j in range(n - i - 1, n):
			coeff[j] += -1 * roots[i - 1] * coeff[j + 1]
	coeff = coeff[::-1]
	ans = 0
	for i in range(k + 1):
		ans += abs(coeff[i])
	return int(ans)
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
st = set(a)
hug = len(st)
if hug != n:
	freq = CountFrequency(a)
	an = [0] * hug
	star = 0
	for (key, value) in freq.items():
		an[star] = value
		star += 1
	siz = hug
	if k > hug:
		k = hug
	ans = vi(an, hug, k)
	print(int(ans) % 1000000007)
else:
	ans = int(math.pow(2, n))
	r = n
	while r > k:
		ans -= int(nCr(n, r))
		r -= 1
	print(int(ans) % 1000000007)


(N, K) = map(int, input().split())
a = list(map(int, input().split()))
dic = {}
for i in range(len(a)):
	if a[i] not in dic:
		dic[a[i]] = 1
	else:
		dic[a[i]] += 1
freq = list()
for x in dic:
	freq.append(dic[x])
(Na, Ka) = (len(freq), min(K, len(freq)))
dp = [[0 for _ in range(Ka + 1)] for _ in range(Na + 1)]
for n in range(Na + 1):
	for k in range(Ka + 1):
		if n == 0 or k == 0:
			dp[n][k] = 1
		else:
			dp[n][k] = freq[n - 1] * dp[n - 1][k - 1] % 1000000007 + dp[n - 1][k] % 1000000007
print(dp[Na][Ka] % 1000000007)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
ss = {}
for i in l:
	try:
		ss[i] += 1
	except:
		ss[i] = 1
dp = [0] * (n + 1)
dp[0] = 1
dp1 = dp[:]
j = 0
for a in ss:
	f = ss[a]
	for i in range(j + 1):
		dp1[i + 1] = dp1[i + 1] + dp[i] * f
	dp = dp1[:]
	j = j + 1
ans = sum(dp[:k + 1]) % (10 ** 9 + 7)
print(ans)


(nn, kk) = map(int, input().split())
it = list(map(int, input().split()))
ss = {}
for i in it:
	try:
		ss[i] += 1
	except:
		ss[i] = 1
j = 0
dp = [0] * (nn + 1)
dp[0] = 1
mod = 10 ** 9 + 7
for i in ss:
	f = ss[i]
	dp2 = dp[:]
	for k in range(j + 1):
		dp2[k + 1] += dp[k] * f
	dp = dp2[:]
	j += 1
	dp = [i % mod for i in dp]
print(sum(dp[:kk + 1]) % (10 ** 9 + 7))


from collections import Counter
mod = 1000000007
(n, k) = map(int, input().split())
arr = [int(i) for i in input().split()]
dic = Counter(arr)
arr1 = []
arr1.append(0)
for value in dic.values():
	arr1.append(value)
arr2 = [0 for i in range(len(arr1))]
arr2[0] = 1
for i in range(1, len(arr1)):
	for j in range(i, 0, -1):
		arr2[j] += arr1[i] * arr2[j - 1] % mod
if k > len(arr1) - 1:
	k = len(arr1) - 1
goodsub = 0
for i in range(k + 1):
	goodsub = (goodsub + arr2[i]) % mod
print(goodsub)


import sys
from functools import reduce
from collections import Counter
from numpy import convolve
(N, K) = map(int, sys.stdin.readline().split())
A = Counter(list(map(int, sys.stdin.readline().split()))[:N])
O = [[1, c] for c in A.values()]
ans = sum(reduce(lambda x, y: convolve(x, y) % 1000000007, O)[:K + 1])
print(ans % 1000000007, end='')


from sys import stdin, stdout
import math
from itertools import permutations, combinations
from collections import defaultdict
from bisect import bisect_left
from bisect import bisect_right

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

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

def I():
	return int(stdin.readline())
P = 1000000007

def main():
	(n, k) = In()
	arr = L()
	ans = 0
	dict1 = {}
	for i in range(n):
		if arr[i] in list(dict1.keys()):
			dict1[arr[i]] += 1
		else:
			dict1[arr[i]] = 1
	l1 = [-1] + list(dict1.keys())
	v = min(k, len(list(set(arr))))
	dp = [[0 for i in range(v + 1)] for i in range(len(l1))]
	dp[0][0] = 1
	for i in range(1, len(l1)):
		dp[i][0] = 1
		for j in range(1, v + 1):
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * dict1[l1[i]]
	for i in range(k + 1):
		ans += dp[len(l1) - 1][i]
		ans = ans % P
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
nums = {}
for i in range(n):
	if arr[i] in nums:
		nums[arr[i]] += 1
	else:
		nums[arr[i]] = 1
newArr = [0] * len(nums)
i = 0
res = 1
for z in nums:
	newArr[i] = nums[z]
	i += 1
temp = list(newArr)
for i in range(len(newArr)):
	res += newArr[i]
cnt = len(newArr)
sums = res - 1
if cnt < k:
	k = cnt
for K in range(1, k):
	nsum = 0
	temp[cnt - K] = 0
	for i in range(cnt - K):
		t = sums - temp[i]
		sums = t
		temp[i] = newArr[i] * t
		res += temp[i]
		nsum += temp[i]
	sums = nsum
print(res % 1000000007)


import collections
import numpy
mo = 10 ** 9 + 7

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
try:
	(x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	k = collections.Counter(l)
	o = list(k.values())
	m = min(y, len(o))
	p = [1] + [0] * m
	s = 0
	for _ in o:
		for i in range(m, 0, -1):
			p[i] += p[i - 1] * _
	print(sum(p) % mo)
except:
	pass


from collections import Counter

def solve(arr, n, k):
	ans = 0
	dict1 = {}
	mod = 1000000007
	for i in range(n):
		if arr[i] in dict1:
			dict1[arr[i]] += 1
		else:
			dict1[arr[i]] = 1
	l1 = [0] + list(dict1.keys())
	v = min(k, len(l1))
	dp = [[0 for _ in range(v + 1)] for _ in range(len(l1))]
	dp[0][0] = 1
	for i in range(1, len(l1)):
		dp[i][0] = 1
		for j in range(1, v + 1):
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * dict1[l1[i]]
	for i in range(v + 1):
		ans += dp[len(l1) - 1][i]
		ans = ans % mod
	return ans
(n, k) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
print(solve(arr, n, k))


from itertools import chain
(n, k) = map(int, input().split())
d = {}
count = 0
l = list(map(int, input().split()))
for i in l:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
l = []
for x in d.values():
	if x == 1:
		count += 1
	else:
		l.append(x)
d = {}
pr = [1]
for i in l:
	pr = [a + b * i for (a, b) in zip(chain([0], pr), chain(pr, [0]))]
a = min(count, k)
comb = [[0 for x in range(a + 1)] for y in range(count + 1)]
for i in range(count + 1):
	for j in range(min(i, a) + 1):
		if j == 0 or j == i:
			comb[i][j] = 1
		else:
			comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j]
pr.reverse()
sum = 0
for i in range(a + 1):
	for j in range(min(len(pr) - 1, k - i) + 1):
		sum = (sum + pr[j] * comb[count][i]) % 1000000007
print(sum)


from collections import Counter
modu = 10 ** 9 + 7
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
m = Counter(arr)
l = min(len(m), k)
dp = [[0 for i in range(len(m) + 1)] for j in range(len(m) + 1)]
un = list(m.values())
for i in range(1, len(m) + 1):
	for j in range(i, len(m) + 1):
		if i == 1:
			dp[i][j] = (dp[i][j - 1] % modu + un[j - 1] % modu) % modu
		else:
			dp[i][j] = (dp[i - 1][j - 1] % modu * (un[j - 1] % modu) % modu + dp[i][j - 1] % modu) % modu
ans = 1
for i in range(1, l + 1):
	ans = (ans % modu + dp[i][len(m)] % modu) % modu
print(ans % modu)


from collections import defaultdict
d = defaultdict(int)
(n, k) = map(int, input().split())
array = list(map(int, input().split()))
for v in array:
	d[v] += 1
prime = 10 ** 9 + 7
count = len(d)
dp = [[(0, 0) for i in range(count)] for j in range(count)]
j = 0
total = 0
for v in d:
	if j == 0:
		dp[0][j] = (d[v], d[v] % prime)
	else:
		dp[0][j] = (d[v], (d[v] + dp[0][j - 1][1]) % prime)
	j += 1
for i in range(1, count):
	for j in range(count):
		if j == 0:
			dp[i][j] = (0, 0)
		else:
			dp[i][j] = (dp[i - 1][j - 1][1] * dp[0][j][0], (dp[i - 1][j - 1][1] * dp[0][j][0] + dp[i][j - 1][1]) % prime)
if k == 0:
	print(1)
else:
	for i in range(count):
		if i < k:
			total = (total + dp[i][count - 1][1]) % prime
		else:
			break
	print(total + 1)


MOD = int(10 ** 9 + 7)

def solve(A, N, K):
	(frequency, ans) = ({}, 0)
	for i in A:
		if i not in frequency:
			frequency[i] = 0
		frequency[i] += 1
	A = list(set(A))
	N = len(A)
	K = min(N, K)
	dp = [[0 for i in range(K + 1)] for j in range(N + 1)]
	for i in range(0, N + 1):
		dp[i][0] = 1
	for i in range(1, N + 1):
		for j in range(1, K + 1):
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * frequency[A[i - 1]]
			dp[i][j] %= MOD
	for i in range(0, K + 1):
		ans += dp[N][i]
		ans %= MOD
	print(ans)
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
solve(A, N, K)


import sys
from functools import reduce
import numpy
input = sys.stdin.readline
from collections import Counter
PUKS = 1000000007
(n, k) = map(int, input().split())
s = list(map(int, list(input().split())))
set1 = set(s)
rl = []
c1 = Counter(s)
for i in set1:
	rl.append(c1[i])
SIZE = len(rl)
row = SIZE + 1
col = SIZE + 1
mat = [[0 for x in range(col)] for y in range(row)]
mat[0][0] = 1
for i in range(1, row):
	mat[i][0] = 1
	j = 1
	while j <= i and j <= k:
		mat[i][j] = mat[i - 1][j] + mat[i - 1][j - 1] * rl[i - 1]
		j = j + 1
add = sum(mat[SIZE][:k + 1]) % PUKS
print(add % PUKS)


(N, K) = [int(i) for i in input().split(' ')]
arr = [int(i) for i in input().split(' ')]
map = {}
mod = 10 ** 9 + 7
for i in arr:
	if i in map:
		map[i] = (map[i] + 1) % mod
	else:
		map[i] = 1
count = list(map.keys())
K = min(len(count), K)
dp = [[0] * (K + 1) for i in range(len(count) + 1)]
for i in range(len(count) + 1):
	for j in range(K + 1):
		if j == 0 or i == 0:
			dp[i][j] = 1
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * map[count[i - 1]] % mod) % mod
print(dp[len(count)][K])


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
M = 10 ** 9 + 7
farr = []
j = 0
f = 0
c = 0
while j < len(l):
	if f == 0:
		f = l[j]
		c = c + 1
		if j == len(l) - 1:
			farr.append(c)
		j = j + 1
	elif f != 0:
		if l[j] == f:
			c = c + 1
			if j == len(l) - 1:
				farr.append(c)
			j = j + 1
		else:
			farr.append(c)
			f = 0
			c = 0
cnt = 1
arr = farr.copy()
z = 1
while z <= k:
	if z == 1:
		cnt = cnt + len(l) % M
	else:
		ic = 0
		i = 0
		kc = 0
		while i < len(farr):
			kc = arr[i]
			arr[i] = ic * farr[i] % M
			ic = ic + kc
			cnt = (cnt + arr[i]) % M
			i = i + 1
	z = z + 1
print(cnt % M)


import sys
from collections import Counter
from functools import reduce
m = 10 ** 9 + 7

def solve(n, k, arr):
	count = list(Counter(arr).values())
	k = min(k, len(count))
	dp = [0] * (k + 1)
	dp[0] = 1
	for i in range(1, len(count) + 1):
		for j in range(min(i, k), 0, -1):
			dp[j] = (dp[j] + dp[j - 1] * count[i - 1] % m) % m
	return reduce(lambda x, y: (x + y) % m, dp)
(n, k) = map(int, sys.stdin.readline().split())
print(solve(n, k, list(map(int, sys.stdin.readline().split()))))


import sys
input = sys.stdin.readline
M = 1000000007
nk = input().strip().split(' ')
nums = input().strip().split(' ')
n = int(nk[0])
k = int(nk[1])
num_dict = {}
uniq_nums = []
for i in range(n):
	v = int(nums[i])
	if v not in num_dict:
		num_dict[v] = 1
		uniq_nums.append(v)
	else:
		num_dict[v] += 1
nu = len(uniq_nums)
go = min(nu, k)
xx = [[0 for j in range(nu)] for j in range(go)]
for i in range(nu - 1, -1, -1):
	if i == nu - 1:
		xx[0][i] = num_dict[uniq_nums[i]]
	else:
		xx[0][i] = (xx[0][i + 1] + num_dict[uniq_nums[i]]) % M
count = 1 + xx[0][0]
for i in range(1, go):
	for j in range(nu - i - 1, -1, -1):
		xx[i][j] = (num_dict[uniq_nums[j]] * xx[i - 1][j + 1] + xx[i][j + 1]) % M
		if j == 0:
			count = (count + xx[i][j]) % M
print(count)


from collections import defaultdict
(n, k) = list(map(int, input().split()))
l = list(map(int, input().split()))
ctr = len(set(l))
l.sort()
dic = defaultdict(lambda : 0)
for i in l:
	dic[i] += 1
dic1 = defaultdict(lambda : 0)
index = 1
for i in list(dic.keys()):
	dic1[index] = dic[i]
	index += 1
dp = [[0 for i in range(k + 1)] for j in range(ctr + 1)]
dp[0][0] = 1
for row in range(1, ctr + 1):
	for col in range(k + 1):
		if col == 0:
			dp[row][col] = 1
		else:
			dp[row][col] = dp[row - 1][col] + dp[row - 1][col - 1] * dic1[row]
print(sum(dp[ctr]) % 1000000007)


def count(arr, k):
	large = 1000000000.0 + 7
	ans = [1] * (len(arr) + 1)
	for i in range(len(arr)):
		curr = arr[i]
		for j in range(i, -1, -1):
			if j == 0:
				ans[j] *= -curr
			else:
				ans[j] = ans[j - 1] - ans[j] * curr
			if ans[j] >= large:
				ans[j] %= large
	for i in range(len(ans)):
		ans[i] = abs(ans[i]) % large
	return ans
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
(dic, a) = ({}, 0)
for i in arr:
	if i not in dic:
		dic[i] = 1
	else:
		dic[i] += 1
ans = count(list(dic.values()), k)
ans = ans[::-1]
print(int(sum(ans[:k + 1]) % (1000000000.0 + 7)))


from collections import Counter

def coefficients(a):
	coeff = [1] * (len(a) + 1)
	for i in range(len(a)):
		cr = a[i]
		for j in range(i, -1, -1):
			if j == 0:
				coeff[j] = coeff[j] * -cr
			else:
				coeff[j] = coeff[j] * -cr + coeff[j - 1]
	return coeff
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
c = Counter(a)
z = coefficients(list(c.values()))
z = z[::-1]
s = 0
for i in range(min(k + 1, len(z))):
	s = (s + abs(z[i])) % 1000000007
print(s)


from collections import Counter
(n, k) = map(int, input().split())
a = [int(k) for k in input().split()]
dd = [-1]
c1 = Counter(a)
mod = int(1000000000.0 + 7)
for i in range(8001):
	if c1[i] > 0:
		dd.append(c1[i])
dp = [[0 for i in range(1100)] for i in range(1100)]
k = min(k, len(dd))
dp[0][0] = 1
for i in range(1, len(dd)):
	dp[i][0] = 1
	for j in range(1, k + 1):
		dp[i][j] = (dp[i - 1][j] + dd[i] * dp[i - 1][j - 1]) % mod
r = 0
for i in range(k + 1):
	r = (r + dp[len(dd) - 1][i]) % mod
print(r)


import collections
mod = 10 ** 9 + 7
(N, K) = map(int, input().split())
arr = list(map(int, input().split()))
count = collections.Counter(arr)
ctr = len(count)
_map = sorted(set(arr))
attach = {}
for i in range(1, ctr + 1):
	attach[_map[i - 1]] = i
for i in range(N):
	arr[i] = attach[arr[i]]
new_count = collections.Counter(arr)
dp = [[0] * (K + 1) for _ in range(ctr + 1)]
for i in range(ctr + 1):
	dp[i][0] = 1
for i in range(1, ctr + 1):
	for j in range(1, min(i + 1, K + 1)):
		dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * new_count[i]
		dp[i][j] %= mod
ans = 0
for j in range(K + 1):
	ans += dp[ctr][j]
	ans %= mod
print(ans)


from collections import Counter
from itertools import accumulate
import numpy as np
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
c = Counter(a)
dis_ele = c.keys()
dis_ele_count = len(dis_ele)
mod = 1000000007
ans = n + 1
arr = np.zeros((dis_ele_count, k + 1))
arr[:, 0] = list(dis_ele)
arr[:, 1] = list(accumulate(c.values()))
for i in range(2, k + 1):
	for j in range(i - 1, dis_ele_count):
		arr[j][i] = arr[j - 1][i - 1] % mod * c[arr[j][0]] % mod % mod + arr[j - 1][i]
	ans = (ans % mod + arr[j][i] % mod) % mod
print(int(ans) % mod)


import sys
import numpy as np
mod = 1000000007
(n, k) = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
fre = [0] * 10000
A = []
for i in range(0, n):
	fre[a[i]] += 1
for i in range(0, 8001):
	if fre[i] > 0:
		A.append(fre[i])
kk = min(len(A), k) + 1
S = np.zeros(kk, dtype=int)
S[0] = 1
for a in A:
	S[1:kk] = (S[1:kk] + a * S[0:kk - 1] % mod) % mod
ans = 0
for s in S:
	ans = (ans + s) % mod
print(ans)


from collections import Counter
(N, K) = (int(x) for x in input().split(' '))
A = (int(x) for x in input().split(' '))
C = Counter(A)
R = [1]
for (n, c) in C.items():
	R.append(0)
	for i in range(len(R) - 1, 0, -1):
		R[i] += R[i - 1] * c
		R[i] = R[i] % 1000000007
print(sum(R[:K + 1]) % 1000000007)


import numpy as np
MOD = 1000000007
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for x in a:
	d[x] = d.get(x, 0) + 1
c = len(d.keys())
freq = list(d.values())
k = min(k, c)
dp = np.zeros((k + 1, c + 1), dtype=int)
for i in range(1, k + 1):
	for j in range(1, c + 1):
		if i == 1:
			dp[i][j] = (dp[i][j - 1] + freq[j - 1]) % MOD
		elif j >= i:
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1] * freq[j - 1]) % MOD
ans = 1
for i in range(1, k + 1):
	ans += dp[i][c]
	ans %= MOD
print(ans)


(n, k) = input().split(' ')
k = int(k)
n = int(n)
M = 1000000007
a = input().split(' ')
for i in range(len(a)):
	a[i] = int(a[i])
a.sort()
freq = {}
for item in a:
	if item in freq:
		freq[item] += 1
	else:
		freq[item] = 1
a2 = []
for (key, value) in freq.items():
	a2.append(value % M)
coeff = [0] * (len(a2) + 1)
coeff[len(a2)] = 1
for i in range(1, len(a2) + 1):
	for j in range(len(a2) - i - 1, len(a2)):
		coeff[j] += -1 * a2[i - 1] * coeff[j + 1]
		abs(coeff[j]) % M
coeff = coeff[::-1]
sum = 0
for i in range(min(k + 1, len(a2) + 1)):
	sum = (sum % M + abs(coeff[i])) % M
print(sum)


def compute_coeff(roots, k):
	mod = 10 ** 9 + 7
	res = [1 for i in range(len(roots) + 1)]
	for i in range(len(roots)):
		cur_root = roots[i]
		for j in range(i, -1, -1):
			if j == 0:
				res[j] *= -cur_root
			else:
				res[j] = res[j - 1] - res[j] * cur_root
			if res[j] >= mod:
				res[j] %= mod
	for i in range(len(res)):
		res[i] = abs(res[i]) % mod
	return res
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
(d, a) = (dict(), 0)
for i in arr:
	if i not in d.keys():
		d[i] = 1
	else:
		d[i] += 1
ans = compute_coeff(list(d.values()), k)
ans = ans[::-1]
print(sum(ans[:k + 1]) % (10 ** 9 + 7))


def pr_sum(dp, row, n):
	pre = []
	ssf = 0
	for i in range(n):
		ssf += dp[row - 1][i]
		pre.append(ssf)
	return pre
(n, k) = map(int, input().split())
lst = list(map(int, input().split()))
cnt = [0] * 8000
for ele in lst:
	cnt[ele] += 1
counter = []
for ele in cnt:
	if ele:
		counter.append(ele)
n = min(1007, k)
a = len(counter)
dp = [[0 for i in range(a)] for i in range(n)]
dp[0] = counter
ans = 1
for i in range(1, n):
	prefix_sum = pr_sum(dp, i, a)
	ans += prefix_sum[-1]
	for j in range(1, a):
		cell_val = prefix_sum[j - 1] * counter[j]
		dp[i][j] = cell_val
ans += sum(dp[-1])
print(ans % 1000000007)


(n, k) = map(int, input().split())
array = list(map(int, input().split()))
d = dict()
for v in array:
	if v not in d:
		d[v] = 1
	else:
		d[v] += 1
prime = 10 ** 9 + 7
count = len(d)
dp = [[0 for i in range(count)] for j in range(count)]
freq = list()
for x in d:
	freq.append(d[x])
j = 0
total = 0
for v in d:
	if j == 0:
		dp[0][j] = d[v] % prime
	else:
		dp[0][j] = (d[v] + dp[0][j - 1]) % prime
	j += 1
for i in range(1, count):
	for j in range(count):
		if j == 0:
			dp[i][j] = 0
		else:
			dp[i][j] = (dp[i - 1][j - 1] * freq[j] + dp[i][j - 1]) % prime
if k == 0:
	print(1)
else:
	for i in range(count):
		if i < k:
			total = (total + dp[i][count - 1]) % prime
		else:
			break
	print(total + 1)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
count = [0] * 8001
for i in l:
	count[i] += 1
arr = []
for i in count:
	if i != 0:
		arr.append(i)
arr.sort()
n = len(arr)
k = min(k, n)
dp = [[0 for i in range(n)] for i in range(k)]
sum = 0
for i in range(n):
	dp[0][i] = arr[i]
	sum += arr[i]
for i in range(1, k):
	S = dp[i - 1][0]
	s = 1
	ns = 0
	for j in range(n - s):
		z = sum - S
		dp[i][j] = dp[0][j] * z
		ns = ns + dp[i][j]
		S = S + dp[i - 1][j + 1]
		s += 1
	sum = ns
ans = 0
for i in range(k):
	for j in dp[i]:
		ans = ans + j
print((ans + 1) % 1000000007)


from collections import Counter
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
mod = 10 ** 9 + 7
unique_arr = list(set(arr))
freq = Counter(arr)
n = len(unique_arr)
k = min(k, n)
dp = [[0] * (k + 1) for i in range(n + 1)]
for i in range(n + 1):
	dp[i][0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		dp[i][j] = (dp[i - 1][j] + freq[unique_arr[i - 1]] * dp[i - 1][j - 1]) % mod
		dp[i][j] = dp[i][j] % mod
ans = 0
for i in range(0, k + 1):
	ans += dp[n][i]
print(ans % mod)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
x = []
x = dict()
for i in range(0, n):
	try:
		x[a[i]] += 1
	except:
		x[a[i]] = 1
x = list(x.values())
x = [1] + x
n = len(x)
k = min(1007, k)
dp = []
te = []
te = [0] * (k + 1)
for i in range(n + 1):
	dp.append(te[:])
dp[0][0] = 1
m = 1000000007
for i in range(1, n):
	dp[i][0] = 1
	for j in range(1, k + 1):
		dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * x[i] % m) % m
ans = 0
for i in range(0, k + 1):
	ans = (ans + dp[n - 1][i]) % m
print(ans)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
d = {}
mod = 1000000007
for i in arr:
	try:
		d[i] += 1
	except:
		d[i] = 1
arr = [d[i] for i in d.keys()]
z = len(arr) - 1
mat = [[0 for i in range(z + 1)] for i in range(k + 1)]
mat[1] = arr[:]
for i in range(1, z + 1):
	mat[1][i] += mat[1][i - 1]
su = sum(arr)
for i in range(2, k + 1):
	if i > len(arr):
		break
	for j in range(z - i + 2):
		x = arr[j] * (mat[i - 1][z - i + 2] - mat[i - 1][j]) % mod
		try:
			mat[i][j] = mat[i][j - 1] + x
		except:
			mat[i][j] = x
	su = (su + mat[i][z - i + 1]) % mod
print(su + 1)


from itertools import chain
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
l = {}
for i in A:
	if i in l:
		l[i] += 1
	else:
		l[i] = 1
q = list(l.values())
x = [1]
for i in q:
	x = [a + b * i for (a, b) in zip(chain([0], x), chain(x, [0]))]
answer = 0
x = x[::-1]
answer = sum(x[:K + 1])
print(answer % 1000000007)


def nkmethod(d):
	modval = 10 ** 9 + 7
	val = 1
	for i in d:
		val *= d[i] + 1
	val = val % modval
	return val

def nlkmethod(n, k, l, d):
	modval = 10 ** 9 + 7
	if k == 0:
		return 1
	elif k == 1:
		return n
	else:
		val = 1 + n
		lv = [d[i] for i in d]
		lv = sorted(lv)
		lvlen = len(d)
		dp2d = [j for j in lv]
		sumdp2d = []
		vv = 0
		for i in dp2d[:0:-1]:
			vv += i
			sumdp2d = [vv] + sumdp2d
		for i in range(2, k + 1):
			if lvlen - i + 1 == 0:
				break
			dp2d = []
			for j in range(lvlen - i + 1):
				tempv = lv[j] * sumdp2d[j]
				dp2d.append(tempv)
				val += tempv
			sumdp2d = []
			vv = 0
			for j in dp2d[:0:-1]:
				vv += j
				sumdp2d = [vv] + sumdp2d
		val = val % modval
		return val
(n, k) = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]
d = {}
for i in l:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
if n == k:
	print(nkmethod(d))
else:
	print(nlkmethod(n, k, l, d))


from collections import Counter
import math
mod = 1000000007
cnt = 1
j = 0
(n, k) = map(int, input().split())
SUM = 1 + n
sum2 = 0
arr1 = [int(i) for i in input().split()]
arr2 = Counter(arr1)
for (key, value) in arr2.items():
	j = j + 1
	if value != 1:
		cnt = 0
if cnt == 1:
	for i in range(2, k + 1):
		c = math.factorial(n) // math.factorial(n - i) // math.factorial(i)
		SUM = (SUM % mod + c % mod) % mod
	print(SUM)
else:
	(r, c) = (j + 1, j + 1)
	arr = [[0 for i in range(c)] for j in range(r)]
	if j == 1:
		print(SUM)
	else:
		if k >= j:
			k = j
		i = 0
		for (key, value) in arr2.items():
			arr[0][i] = value
			sum2 = (sum2 % mod + value % mod) % mod
			i = i + 1
		i = 1
		while i < j and i < k:
			sum1 = 0
			sum3 = 0
			x = 0
			while x < j - i:
				sum1 = sum1 + arr[i - 1][x]
				arr[i][x] = arr[0][x] * (sum2 - sum1)
				sum3 = sum3 + arr[i][x]
				x = x + 1
			sum2 = sum3
			SUM = (SUM % mod + sum3 % mod) % mod
			i = i + 1
		print(SUM)


(n, k) = map(int, input().strip().split())
arr = [int(i) for i in input().strip().split()]

def countFreq(arr):
	d = dict()
	for i in range(len(arr)):
		if arr[i] in d.keys():
			d[arr[i]] += 1
		else:
			d[arr[i]] = 1
		list = []
	for x in d:
		list.append(d[x])
	return list
c = countFreq(arr)
n = 100000
a = [0] * n
b = [0] * n
a[1] = c[0]
a[0] = 1
b[1] = c[0]
b[0] = 1
p = 1
for i in range(1, len(c)):
	while i >= 0:
		a[i + 1] = a[i] * c[p] + b[i + 1]
		a[i + 1] = a[i + 1] % 1000000007
		b[i + 1] = a[i + 1]
		i = i - 1
	p = p + 1
if k <= p:
	p = k
ans = 0
for i in range(p + 1):
	ans = ans + b[i] % 1000000007
print(ans % 1000000007)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
dic = {}
for i in a:
	if i not in dic:
		dic[i] = 1
	else:
		dic[i] += 1
li = list(dic.values())
ans = 1 + n
mi = min(k, len(li))
te = []
for i in range(len(li)):
	t = 0
	for j in range(i + 1, len(li)):
		t += li[i] * li[j]
	if i > 0 and t > 0:
		te.append(t)
	ans += t
for i in range(2, mi):
	dummy = []
	tesum = sum(te)
	for j in range(len(te)):
		if j > 0:
			tesum -= te[j - 1]
		t = li[j] * tesum
		ans += t
		if j > 0:
			dummy.append(t)
	te = dummy
print(ans % (10 ** 9 + 7))


(n, k) = input().split()
n = int(n)
k = int(k)
s = 0
arr = list(map(int, input().split()))
arr1 = [0 for i in range(8001)]
arr2 = []
for i in arr:
	arr1[i] += 1
for i in arr1:
	if i >= 1:
		arr2.append(i)
p = len(arr2)
arr2.sort()
flist = [[0 for i in range(p)] for j in range(k)]
sum1 = 0
for i in range(p):
	flist[0][i] = arr2[i]
	sum1 += arr2[i]
fsum = sum1
for i in range(1, k):
	sum2 = 0
	for j in range(p):
		sum1 -= flist[i - 1][j]
		flist[i][j] = arr2[j] * sum1
		sum2 = sum2 + flist[i][j]
		if sum1 <= 0:
			break
	sum1 = sum2
	fsum += sum2
print((fsum + 1) % 1000000007)


import collections
import gc
from itertools import combinations
mod = 1000000007

def finalans(a, k1):
	sizeA = len(a)
	sumArray = [0] * (sizeA + 1)
	totalSum = sum(a)
	sumArray[0] = totalSum
	for i in range(1, sizeA + 1):
		sumArray[i] = sumArray[i - 1] - a[i - 1]
	summ = 0
	productArray1 = sumArray[:-1]
	productArray = []
	for k in range(k1 + 1):
		if k == 0:
			summ += 1
		elif k == 1:
			summ += totalSum
		elif k == 2:
			xx = len(productArray1)
			for i in range(1, xx):
				productArray.append(productArray1[i] * a[i - 1])
			productArray1 = productArray[:]
			summ = (summ + sum(productArray)) % mod
		else:
			xx = len(productArray1)
			productArray.clear()
			temp = sum(productArray1[1:])
			for i in range(1, xx):
				productArray.append(temp * a[i - 1])
				temp -= productArray1[i]
			productArray1 = productArray[:]
			summ = (summ + sum(productArray)) % mod
	return summ

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
(n, k) = map(int, str(input()).split(' '))
l = list(map(int, str(input()).split(' ')))
temp = collections.Counter(l)
res = 0
s = set(l)
lis = list(s)
lens = len(s)
if lens == n:
	for j in range(k + 1):
		res = (res + ncr(n, j, mod)) % mod
	print(res)
elif lens <= k:
	t1 = list(temp.values())
	pro = 1
	for ele in t1:
		pro = pro * (ele + 1) % mod
	print(pro)
else:
	a = list(temp.values())
	s = 0
	s = finalans(a, k)
	print(s)


mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
l = [0]
a.sort()
for i in range(0, n):
	if a[i] == a[i - 1]:
		l[-1] += 1
	else:
		l.append(1)
maxxl = min(k, len(l))
array = []
for i in range(maxxl + 1):
	temp = [0] * len(l)
	array.append(temp)
for i in range(1, maxxl + 1):
	temp = 0
	for j in range(1, len(l)):
		if i == 1:
			array[i][j] = l[j]
		elif j >= i:
			temp += array[i - 1][j - 1]
			array[i][j] = temp * l[j] % mod
ans = 0
for i in range(len(array)):
	for j in range(len(array[i])):
		ans = (ans + array[i][j]) % mod
ans += 1
print(ans % mod)


import collections
import math

def CountFreq(arr):
	return collections.Counter(arr)

def nCr(n, i):
	npr = math.factorial(n) // math.factorial(n - i)
	ncr = npr // math.factorial(i)
	return ncr
l = 1000000007
c = 0
j = 0
(n, k) = map(int, input().split())
m = math.factorial(n)
list1 = [int(i) for i in input().split()]
list2 = CountFreq(list1)
for (key, value) in list2.items():
	j = j + 1
	if value != 1:
		c = 1
s1 = 1 + n
if c == 0:
	for i in range(2, k + 1):
		npr = m // math.factorial(n - i)
		ncr = npr // math.factorial(i)
		s1 = (s1 % l + ncr % l) % l
	print(s1)
else:
	s2 = 0
	(rows, cols) = (j + 1, j + 1)
	arr = [[0 for i in range(cols)] for j in range(rows)]
	if j == 1:
		print(s1)
	else:
		if k >= j:
			k = j
		i = 0
		for (key, value) in list2.items():
			arr[0][i] = value
			s2 = (s2 % l + value % l) % l
			i = i + 1
		i = 1
		while i < j and i < k:
			sm1 = 0
			s3 = 0
			z = 0
			while z < j - i:
				sm1 = sm1 + arr[i - 1][z]
				arr[i][z] = arr[0][z] * (s2 - sm1)
				s3 = s3 + arr[i][z]
				z = z + 1
			s2 = s3
			s1 = (s1 % l + s3 % l) % l
			i = i + 1
		print(s1)


(n, k) = list(map(int, input().split()))
x = list(map(int, input().split()))
l = [0 for i in range(100001)]
for i in x:
	l[i] += 1
l = list([a for a in l if a != 0])
k = min(k, len(l))
dp = [[0 for i in range(len(l) + 1)] for j in range(k)]
for i in range(1, len(l) + 1):
	dp[0][i] = dp[0][i - 1] + l[i - 1]
ans = dp[0][len(l)] + 1
for i in range(1, k):
	for j in range(1, len(l) + 1):
		dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1] * l[j - 1]) % 1000000007
	ans = (ans + dp[i][len(l)]) % 1000000007
print(ans)


D = 1000000007
(N, K) = map(int, input().split())
s = list(map(int, input().split()))
S = set()
M = [0 for x in range(8000)]
for x in s:
	n = x
	M[n] += 1
	S.add(n)
L = list(S)
sz = len(L)
if sz > K:
	R = [0 for x in range(K + 1)]
	R[0] = 1
	mx = 1
	for x in L:
		n = M[x]
		p = mx
		while p > 0:
			R[p] = (R[p] + n * R[p - 1]) % D
			p -= 1
		mx = min(K, mx + 1)
	r = 0
	for x in R:
		r += x
	r = r % D
else:
	r = 1
	for x in L:
		n = M[x]
		r = r * (n + 1) % D
print(r)


import numpy as np
import collections
nk = list(map(int, input().split()))
inp = list(map(int, input().split()))
counter = collections.Counter(inp)
A = list(counter.values())
k = nk[1]
p = 10 ** 9 + 7
kk = min(len(A), k) + 1
S = np.zeros(kk, dtype=int)
S[0] = 1
for a in A:
	S[1:kk] = S[1:kk] % p + a % p * S[0:kk - 1] % p % p
print(S.sum() % p)


from collections import Counter
BIGN = 1000000007

def calcans(m: Counter, k: int):
	nums = list(m.values())
	pref = []
	c = 0
	buff = 0
	for i in nums:
		buff += i
		pref.append(buff)
		c += 1
	if k == 1:
		return pref[c - 1] % BIGN
	ans = 0
	pref2 = [0] * c
	i = c - 1
	while i > 0:
		ans += nums[i] * pref[i - 1]
		pref2[i] = ans
		i -= 1
	ans = ans + pref[c - 1]
	if k == 2:
		return ans % BIGN
	idx = 1
	while k > 2:
		buffans = 0
		i = c - 1
		while i > idx:
			buffans += nums[i] * (pref2[idx] - pref2[i])
			pref2[i] = buffans
			i -= 1
		ans += buffans
		idx += 1
		k -= 1
	return ans % BIGN
(n, k) = tuple([int(x) for x in str(input()).split(' ')])
a = [int(x) for x in str(input()).split(' ')]
c = Counter(a)
key = list(c.keys())
val = list(c.values())
ans = calcans(c, k)
print((ans + 1) % BIGN)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
o = 10 ** 9 + 7
h = {}
for i in l:
	try:
		h[i] = h[i] + 1
	except:
		h[i] = 1
u = []
for i in h:
	u.append(h[i])
z = u[:]
a = 0
for i in range(1, len(u)):
	s = 0
	v = [0] * len(u)
	if m == 1:
		break
	for j in range(i, len(u)):
		s = (s + u[j - 1] % o) % o
		v[j] = s * z[j] % o
	a = (a + sum(v) % o) % o
	m = m - 1
	u = v
print((a + (1 + sum(z))) % o)


def multiply(A, B, m, n):
	prod = [0] * (m + n - 1)
	for i in range(m):
		for j in range(n):
			x = A[i] * B[j] % 1000000007
			prod[i + j] = (prod[i + j] + x) % 1000000007
	return prod
(n, k) = [int(x) for x in input().split(' ')]
if n != 1:
	s = [int(x) for x in input().split(' ')]
	arr = [0] * 1000000
	m = 0
	for i in s:
		arr[i] += 1
		if m < i:
			m = i
	A = [1, 0]
	B = [1]
	for i in range(2, m + 1):
		if arr[i] != 0:
			B.append(arr[i])
			A = multiply(A, B, len(A), len(B))
			B = [1]
	out = 0
	for i in range(k + 1):
		if i < len(A):
			out = (out + A[i]) % 1000000007
	print(out)
else:
	s = int(input())
	print(pow(2, 0))


from collections import defaultdict
(n, k0) = map(int, input().split())
a = list(map(int, input().split()))
d = defaultdict(int)
for i in a:
	d[i] += 1
k = list(d.keys())
k.sort()
dp = [0] * (len(k) + 1)
dp[0] = 1
m = 10 ** 9 + 7
for (j, key) in enumerate(k):
	for i in range(len(k), 0, -1):
		dp[i] = (dp[i] % m + dp[i - 1] * d[key] % m) % m
s = 0
for i in range(min(k0, len(k)) + 1):
	s = (s + dp[i]) % m
print(s)


try:
	from collections import Counter
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = Counter(l)
	k = min(k, len(c))
	ar = [0] * (k + 1)
	ar[0] = 1
	for _ in c:
		for i in range(k, 0, -1):
			ar[i] = (ar[i] + ar[i - 1] * c[_] % 1000000007) % 1000000007
	ans = 0
	for _ in ar:
		ans = (ans + _) % 1000000007
	print(ans % 1000000007)
except:
	pass


M = 1000000007
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for i in a:
	if i not in d:
		d[i] = 1
	else:
		d[i] += 1
s = set(a)
l = []
for i in d:
	if len(l) == 0:
		l.append(d[i])
	else:
		l.append(d[i] + l[-1])
ans = 1 + n
st = l[-1]
b = list(d.keys())
k = min(k, n)
for i in range(2, k + 1):
	t = 0
	for j in range(len(s)):
		if j + i > len(s):
			break
		if st - l[j] >= 0:
			l[j] = d[b[j]] * (st - l[j]) % M
		else:
			l[j] = d[b[j]] * (st - l[j] + M) % M
		t = (t + l[j]) % M
		l[j] = t
	st = t
	ans = (ans + st) % M
print(ans)


def vietaFormula(freq, n):
	coeff = [0] * (n + 1)
	coeff[n] = 1
	for i in range(1, n + 1):
		for j in range(n - i - 1, n):
			coeff[j] += -1 * freq[i - 1] * coeff[j + 1]
	coeff = coeff[::-1]
	return coeff

def print_ans(n, k, a):
	dic = dict()
	for i in a:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	n = len(dic)
	freq = [dic[x] for x in dic]
	del a
	coeff = vietaFormula(freq, n)
	st = 1
	for x in range(1, min(k + 1, len(coeff))):
		if x % 2 == 1:
			st += -1 * coeff[x]
		else:
			st += coeff[x]
	print(st // coeff[0] % 1000000007)
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
print_ans(n, k, a)


from collections import Counter
from functools import reduce

def main():
	(n, k) = [int(ele) for ele in input().strip().split()]
	a = [int(ele) for ele in input().strip().split()]
	freqArray = list(Counter(a).values())
	n = len(freqArray)
	sum1 = sum(freqArray, 1) % 1000000007
	fre = [[0 for i in range(n)] for j in range(n)]
	for j in range(n):
		fre[0][j] = freqArray[j]
	for i in range(1, k):
		sum2 = 0
		for j in range(1, n - i + 1):
			sum2 += fre[i - 1][j]
		for j in range(0, n - i):
			fre[i][j] = freqArray[j] * sum2
			sum2 -= fre[i - 1][j + 1]
			sum1 = (sum1 % 1000000007 + fre[i][j] % 1000000007) % 1000000007
	print(sum1)
main()


def SOE(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def dp(arr):
	i = 1
	while i <= prime[max_num]:
		j = 1
		while j <= min(i, k):
			if j == 1:
				arr[i][j] = (arr[i - 1][j] + f[i]) % (10 ** 9 + 7)
			else:
				arr[i][j] = arr[i - 1][j - 1] * f[i] % (10 ** 9 + 7) + arr[i - 1][j]
			j = j + 1
		i = i + 1
(n, k) = [int(x) for x in input().split()]
num = [int(x) for x in input().split()]
prime = SOE(8000)
prime_count = 1
for i in range(2, 8000):
	if prime[i] == True:
		prime[i] = prime_count
		prime_count = prime_count + 1
f = [0 for x in range(1008)]
max_num = -1
for j in range(len(num)):
	f[prime[num[j]]] += 1
	if num[j] > max_num:
		max_num = num[j]
arr = [[0 for x in range(1008)] for p in range(1008)]
dp(arr)
print(sum(arr[prime[max_num]]) % (10 ** 9 + 7) + 1)


def s(K):
	dp = [[0 for i in range(8010)] for j in range(8010)]
	for i in range(len(v)):
		dp[i][0] = 1
	for i in range(1, len(v) + 1):
		for j in range(len(v) + 1):
			dp[i][j] = dp[i - 1][j] % M + v[i - 1] * dp[i - 1][j - 1] % M
			dp[i][j] %= M
	ans = 0
	for k in range(K + 1):
		ans += dp[len(v)][k]
		ans %= M
	return ans

def precalc():
	facts = [1]
	for i in range(1, 8008):
		facts.append(facts[-1] * i)
	return facts
facts = precalc()
M = 1000000007
(n, K) = map(int, input().split())
a = list(map(int, input().split()))
A = [0 for i in range(8008)]
for i in a:
	A[i] += 1
ans = 1
b = list(set(a))
m = len(b)
nf = facts[m]
ans = 1
if K == n:
	for i in b:
		ans *= A[i] + 1
		ans %= M
	print(ans % M)
	exit(0)
if n == m:
	for k in range(1, K + 1):
		ans += nf // (facts[k] * facts[n - k])
		ans = ans % M
	print(ans % M)
else:
	v = []
	for i in A:
		if i != 0:
			v.append(i % M)
	print(s(K) % M)


(n, k) = map(int, input().split())
a = [int(n) for n in input().split()]
d = dict()
for i in range(n):
	if a[i] in d:
		d[a[i]] += 1
	else:
		d[a[i]] = 1
b = list(d.values())
b.sort()
post = []
su = 0
for i in range(len(b)):
	su += b[len(b) - 1 - i]
	post += [su]
temp = len(b)
if temp < k:
	k = temp
su = 0
t = len(post)
mod = 10 ** 9 + 7
for j in range(1, k):
	ct = 0
	for i in range(temp - j):
		ct += post[i] * b[temp - j - i - 1]
		su += post[i] * b[temp - j - i - 1]
		post[i] = ct
su += n + 1
print(su % mod)


def postfix(arr1, k):
	for i in range(k - 1, 0, -1):
		arr1[i - 1] = arr1[i - 1] + arr1[i]

def modify(arr1, k, a):
	for i in range(1, k):
		arr1[i - 1] = a[i - 1] * arr1[i]

def allcombination(arr1, k):
	s = 0
	a = arr1[:]
	for i in range(1, k):
		postfix(arr1, len(arr1) - i + 1)
		s1 = 0
		for j in range(1, len(arr1) - i + 1):
			s1 += a[j - 1] * arr1[j]
		s += s1
		modify(arr1, len(arr1), a)
	return s
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
d = {}
for i in arr:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
s = 1 + n
arr1 = list(d.values())
arr1.sort(reverse=False)
if k > len(arr1):
	k = len(arr1)
s += allcombination(arr1, k)
print(s % 1000000007)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
M = 10 ** 9 + 7
farr = []
d = {}
for i in l:
	if i in d:
		d[i] = d[i] + 1
	else:
		d[i] = 1
for i in d:
	farr.append(d[i])
cnt = 1
arr = farr.copy()
z = 1
while z <= k:
	if z == 1:
		cnt = (cnt + sum(arr)) % M
	else:
		ic = 0
		i = 0
		kc = 0
		while i < len(farr):
			kc = arr[i]
			arr[i] = ic * farr[i] % M
			ic = ic + kc
			cnt = (cnt + arr[i]) % M
			i = i + 1
	z = z + 1
print(cnt % M)


from collections import defaultdict

def solve(arr, k):
	k = min(k, 1007)
	mod = pow(10, 9) + 7
	s = set(arr)
	count = defaultdict(lambda : 0)
	for ele in arr:
		count[ele] += 1
	dp = [[0 for _ in range(k + 1)] for _ in range(len(s) + 1)]
	for i in range(len(dp)):
		dp[i][0] = 1
	temp = list(s)
	temp = [0] + temp
	for i in range(1, len(dp)):
		for j in range(1, k + 1):
			if j > i:
				dp[i][j] = 0
			else:
				dp[i][j] = (dp[i - 1][j] + count[temp[i]] * dp[i - 1][j - 1] % mod) % mod
	ans = 0
	for i in range(0, k + 1):
		ans = (ans + dp[-1][i]) % mod
	return ans
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
ans = solve(arr, k)
print(ans)


def modulus(n):
	mod = int(1000000000.0) + 7
	if n < 0:
		n += mod
	else:
		n = n % mod
	return n
(n, k) = list(map(int, input().strip().split()))
array = list(map(int, input().strip().split()))
freak = []
for i in list(set(array)):
	freak.append(array.count(i))
dp = [[0] * len(freak) for _ in range(k)]
for i in range(len(freak)):
	dp[0][i] = freak[i]
for row in range(1, k):
	for col in range(0, len(freak) - row):
		dp[row][col] = modulus(freak[col] * sum(dp[row - 1][col + 1:]))
ans = 1
for i in dp:
	ans += sum(i)
ans = modulus(ans)
print(ans)


M = 1000000007
import sys

class recursionlimit:

	def __init__(self, limit):
		self.limit = limit
		self.old_limit = sys.getrecursionlimit()

	def __enter__(self):
		sys.setrecursionlimit(self.limit)

	def __exit__(self, type, value, tb):
		sys.setrecursionlimit(self.old_limit)
with recursionlimit(100005):

	def SOP(n, k, a, dp):
		if k == -1:
			return 1
		if n == -1:
			return 0
		if dp[n][k] != -1:
			return dp[n][k]
		ans1 = a[n] * SOP(n - 1, k - 1, a, dp) % M
		ans2 = SOP(n - 1, k, a, dp)
		dp[n][k] = (ans1 + ans2) % M
		return dp[n][k]
	(N, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a_set = list(set(a))
	a_count = []
	for x in a_set:
		a_count.append(a.count(x))
	len_a_count = len(a_count)
	k = min(len(a_set), k)
	dp = [[-1 for i in range(k)] for j in range(len_a_count)]
	final_ans = 0
	for i in range(k + 1):
		final_ans = (final_ans + SOP(len_a_count - 1, i - 1, a_count, dp)) % M
	print(final_ans)


mod = 10 ** 9 + 7

def fact():
	f = [1]
	for i in range(1, 8008):
		f.append(f[-1] * i)
	return f
f = fact()
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
A = [0 for i in range(8080)]
for i in a:
	A[i] += 1
s = list(set(a))
m = len(s)
nf = f[m]
if k == n:
	ans = 1
	for i in s:
		ans *= A[i] + 1
		ans %= mod
	print(ans % mod)
	exit(0)
if n == m:
	ans = 1
	for i in range(1, k + 1):
		ans += nf // (f[i] * f[n - i])
		ans = ans % mod
	print(ans % mod)
else:
	freq = []
	for i in A:
		if i != 0:
			freq.append(i % mod)
	z = len(freq)
	dp = [[0 for i in range(8080)] for j in range(8080)]
	for i in range(z):
		dp[i][0] = 1
	for i in range(1, z + 1):
		for j in range(z + 1):
			dp[i][j] = dp[i - 1][j] % mod + freq[i - 1] * dp[i - 1][j - 1] % mod
			dp[i][j] %= mod
	ans = 0
	for i in range(k + 1):
		ans += dp[len(freq)][i]
		ans %= mod
	print(ans % mod)


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
(d, s, temp, arr) = ({}, 0, [], [])
arr.append([])
for i in a:
	d[i] = 0
for i in a:
	d[i] += 1
for i in d:
	arr[0].append(d[i])
	s += d[i]
	temp.append(s)
for i in range(1, k):
	arr.append([])
	val = 0
	for j in range(len(arr[0]) - i):
		v = arr[0][j] * (temp[-i] - temp[j])
		arr[i].append(v)
		s += v
		val += v
		temp[j] = val
print((s + 1) % 1000000007)


import itertools
import math
import string
from collections import Counter
M = 10 ** 9 + 7

def ans(a, k):
	kk = 0
	if len(a) < k:
		kk = len(a) + 1
	else:
		kk = k + 1
	s = [0] * kk
	s[0] = 1
	s1 = s[:]
	for i in range(0, len(a)):
		for j in range(1, kk):
			s[j] = (s[j] % M + a[i] * s1[j - 1] % M) % M
		s1 = s[:]
	su = 0
	for i in range(0, kk):
		su = (su % M + s[i] % M) % M
	print(su % M)
(n, k) = map(int, input().split())
a = [int(x) for x in input().split()]
c = list(Counter(a).values())
ans(c, k)


mod = 1000000007
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
dic = {}
s = 0
temp = []
arr2 = []
arr2.append([])
for x in arr:
	dic[x] = 0
for x in arr:
	dic[x] = dic[x] + 1
for x in dic:
	arr2[0].append(dic[x])
	s = s + dic[x]
	temp.append(s)
for x in range(1, k):
	arr2.append([])
	cc = 0
	for y in range(len(arr2[0]) - x):
		v = arr2[0][y] * (temp[-x] - temp[y])
		arr2[x].append(v)
		s = s + v
		cc = cc + v
		temp[y] = cc
print((s + 1) % mod)


import collections

def prepare_nck(n, k):
	ncr = [0] * (k + 1)
	for i in range(k + 1):
		if ncr[i] != 0:
			break
		if i == 0:
			nxt = 1
		else:
			nxt = ncr[i - 1] * (n - (i - 1)) // i
		ncr[i] = nxt
		if n - i <= k:
			ncr[n - i] = nxt
	return ncr

def sum_ncr_mod(n, k, mod):
	ncr = prepare_nck(n, k)
	result = 0
	for ncr_val in ncr:
		result = (result + ncr_val) % mod
	return result

def count_frequency(arr):
	freq = {}
	for item in arr:
		if item in freq:
			freq[item] += 1
		else:
			freq[item] = 1
	return freq

def cal_result(a, n, k, mod):
	a_set = set(a)
	freq = count_frequency(a)
	k = min(k, len(a_set))
	cf = [0] * (len(a_set) + 1)
	freq_val = list(freq.values())
	cf[0] = 1
	cf[1] = freq_val[0] % mod
	index = 2
	for i in range(1, len(freq_val)):
		val = freq_val[i]
		for j in range(index, 0, -1):
			cf[j] = (cf[j] + val * cf[j - 1]) % mod
		index += 1
	result = 0
	for i in range(k + 1):
		result = (result + cf[i]) % mod
	return result

def solve():
	mod = 10 ** 9 + 7
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a_set = set(a)
	if n == len(a_set):
		print(sum_ncr_mod(n, k, mod))
		return
	print(cal_result(a, n, k, mod))
solve()


import numpy as np
from collections import defaultdict
import sys
MOD = 1000000000.0 + 7
(n, k) = map(int, sys.stdin.readline().split(' '))
arr = [int(x) for x in sys.stdin.readline().split(' ')]
A = []
d = defaultdict(int)
for ele in arr:
	d[ele] += 1
for key in d.keys():
	A.append(d[key])
kk = min(len(A), k) + 1
result = np.zeros(kk, dtype=int)
result[0] = 1
for a in A:
	result[1:kk] = (result[1:kk] + a * result[0:kk - 1] % MOD) % MOD
ans = 0
for r in result:
	ans = (ans + r) % MOD
print(int(ans % MOD))