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: interview

Starter code:

Solutions:
# cook your dish here
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))

# cook your dish here
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) = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
print(solve(arr, n, k))

# cook your dish here
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) = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
print(solve(arr, n, k))

# cook your dish here
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 = [-2]+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) = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
print(solve(arr, n, k))

# cook your dish here
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 = [-1]+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) = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
print(solve(arr, n, k))

# cook your dish here
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 = [-1]+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) = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
print(solve(arr, n, k))

from collections import defaultdict
n,k = list(map(int,input().split()))
l = list(map(int,input().split()))
ctr = len(set(l))
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(dic1)
#print(*dp)
print(sum(dp[ctr])%1000000007)



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(dic1)
#print(*dp)
print(sum(dp[ctr])%1000000007)



# cook your dish here
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(l1))
 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(v+1):
  ans += dp[len(l1)-1][i]
  ans = ans%P
 print(ans)
  
 
 
def __starting_point():
 main()

__starting_point()

# cook your dish here
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(l1))
 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()

# cook your dish here
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(l1))
 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()

# cook your dish here
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()

# cook your dish here
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 = {}
 v = min(k+1, len(list(set(arr))))
 
 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())
 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()

# cook your dish here
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])
# print(l)
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]
# print(dp)
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(dp)
print(ans)


# cook your dish here
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])
# print(l)
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]
# print(dp)
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(dp)
print(ans)



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

n,k = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
M = 10**9+7
farr = []
arr = []
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)
   arr.append(c)

  j = j + 1

 elif(f != 0):
  if l[j] == f:
   c = c+1
   #j = j + 1
   if j == len(l) - 1:
    farr.append(c)
    arr.append(c)

   j = j + 1

  else:
   farr.append(c)
   arr.append(c)
   f = 0
   c = 0

cnt = 1
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)

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
   #j = j + 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)

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
   #j = j + 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+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)

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

#print(farr)
cnt = 1
arr = farr.copy()
#print(arr)
#print(sum(arr))
z = 1
while(z <= k):
 if z == 1:
  cnt = (cnt+sum(arr))%M
  #print(cnt)

 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)

# creating a modulus function for efficiency purpose
def modulus(n):
 # defining modulus
 mod = int(1e9) + 7
 if n < 0:
  n += mod
 else:
  n = n % mod
 return n
# taking input
n,k = list(map(int, input().strip().split()))
array = list(map(int, input().strip().split()))
# creating a frequency array called freak
freak = []
for i in list(set(array)):
 freak.append(array.count(i))
# creating a DP Matrix of zeros initially
dp = [[0]*len(freak) for _ in range(k)]
# elements of first row of DP matrix will be same as the freak array
for i in range(len(freak)):
 dp[0][i] = freak[i]
# starting calculations from the second row onwards
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:]))
# answer will be sum[dp] plus 1 for empty set
ans = 1
for i in dp:
 ans += sum(i)
ans = modulus(ans)
# printing the answer
print(ans)