Bharat was given a problem to solve, by his brother, Lord Ram. The problem was like, given integers, $N$ and $K$, Bharat has to find the number (possibilities) of non-increasing arrays of length $K$, where each element of the array is between $1$ and $N$ (both inclusive). He was confused, regarding this problem. So, help him solve the problem, so that, he can give the answer of the problem, to his brother, Lord Rama. Since, the number of possible sub-arrays can be large, Bharat has to answer the problem as "number of possible non-increasing arrays", modulo  $10^9$ $+$ $7$.

-----Input:-----
- Two space-seperated integers, $N$ and $K$.

-----Output:-----
- Output in a single line, the number of possible non-increasing arrays, modulo $10^9$ $+$ $7$.

-----Constraints:-----
- $1 \leq N, K \leq 2000$

-----Sample Input:-----
2 5

-----Sample Output:-----
6

-----Explanation:-----
- Possible Arrays, for the "Sample Case" are as follows: 
- {1, 1, 1, 1, 1}
- {2, 1, 1, 1, 1}
- {2, 2, 1, 1, 1} 
- {2, 2, 2, 1, 1}
- {2, 2, 2, 2, 1}
- {2, 2, 2, 2, 2}
- Hence, the answer to the "Sample Case" is $6$ ($6$ % ($10^9$ $+$ $7$)).

Difficulty: interview

Starter code:

Solutions:
import math
p=7+10**9
n,k=list(map(int,input().split()))
c=math.factorial(n+k-1)//((math.factorial(k))*(math.factorial(n-1)))
print(c%p)


from math import *
 
# Function to find the nCr 
def printNcR(n, r): 
 
 # p holds the value of n*(n-1)*(n-2)..., 
 # k holds the value of r*(r-1)... 
 p = 1
 k = 1
 
 # C(n, r) == C(n, n-r), 
 # choosing the smaller value 
 if (n - r < r): 
  r = n - r 
 
 if (r != 0):  
  while (r): 
   p *= n 
   k *= r 
 
   # gcd of p, k 
   m = gcd(p, k) 
 
   # dividing by gcd, to simplify product 
   # division by their gcd saves from the overflow 
   p //= m 
   k //= m 
 
   n -= 1
   r -= 1
 
  # k should be simplified to 1 
  # as C(n, r) is a natural number 
  # (denominator should be 1 )  
 
 else: 
  p = 1
 
 # if our approach is correct p = ans and k =1 
 return p
 
n,k=map(int,input().split())
print(int(printNcR(n+k-1,k)%(1000000000+7)))

import numpy as np
MOD = 1000000007

N,K = list(map(int,input().split()))
a = np.ones(N)

for i in range(K-1):
 a = np.cumsum(a)
 a = np.mod(a,MOD)
print(int(np.sum(a)) % MOD)


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 
a,b=map(int,input().split())
m=10**9+7
print(ncr(a+b-1,b,m))

# cook your dish here
import math

mod = 10**9 + 7

def main():
 N,K = list(map(int,input().split()))
 dp = [1]*(K+1)
 for j in range(1,N):
  val = 1
  for i in range(1,K+1):
   dp[i] = (dp[i-1] + dp[i])%mod
 print(dp[K])
 
def __starting_point():
 main()

__starting_point()

import math
k,n=map(int,input().split())
x=10**9+7
print((math.factorial(n+k-1)//(math.factorial(k-1)*math.factorial(n)))%x)

# cook your dish here
# import sys
# sys.stdin = open('input.txt', 'r') 
# sys.stdout = open('output.txt', 'w')

import math
import collections
from sys import stdin,stdout,setrecursionlimit
import bisect as bs
setrecursionlimit(2**20)
M = 10**9+7

def nCrModp(n, r, p): 
 if (r > n- r): 
  r = n - r 
 C = [0 for i in range(r + 1)] 
 
 C[0] = 1
 
 for i in range(1, n + 1): 
  for j in range(min(i, r), 0, -1): 
   C[j] = (C[j] + C[j-1]) % p 
 
 return C[r] 
 

# T = int(stdin.readline())
# for _ in range(T):
 # n = int(stdin.readline())
n,k = list(map(int,stdin.readline().split()))
 # a = list(map(int,stdin.readline().split()))
 # q = list(map(int,stdin.readline().split()))
 # b = list(map(int,stdin.readline().split()))
 # a = stdin.readline().strip('\n')
N = n+k-1
R = n-1
print(nCrModp(N,R,M))

MOD = 10 ** 9 + 7

n, k = map(int, input().split())

pre = [[0] * k for _ in range(n+1)]

for i in range(1, n+1):
 pre[i][0] = i
 for j in range(1, k):
  pre[i][j] = (pre[i-1][j] + pre[i][j-1]) % MOD

print(pre[n][k-1])

# Python3 function to 
# calculate nCr % p 
def ncr(n, r, p): 
 # initialize numerator 
 # and denominator 
 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 
M=10**9+7
N,K=map(int,input().split())
ans=0
for i in range(N,0,-1):
 ans+=ncr(N-i+K-1,K-1,M)
 ans%=M
print(ans) 

import sys
from collections import defaultdict
sys.setrecursionlimit(3000)

R = lambda t = int: t(eval(input()))
RL = lambda t = int: [t(x) for x in input().split()]
RLL = lambda n, t = int: [RL(t) for _ in range(n)]


MOD = 10**9 + 7
 
def divc(x):
 return pow(x, MOD-2, MOD)
 
def C(n,k):
 r = 1
 for i in range(k + 1, n+1):
  r = r * i % MOD
 t = 1
 for i in range(1,n-k+1):
  t = t * i % MOD
 return r * divc(t) % MOD

def solve():
 N, K = RL()
 print(C(K+N-1,N-1)) 

T = 1
for t in range(1, T + 1):
 solve()


from math import factorial as fact
mod = 10**9 + 7

def C(n, k):
 return (fact(n) // (fact(k) * fact(n - k)))

n, m = map(int, input().split())
print(C(n + m - 1, m) % mod)