output_description: Print the number of possible combinations of numbers of people in the n rooms
  now, modulo (10^9 + 7).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      n k
attempt: from functools import lru_cache
  
  
  CHECK = False
  
  N, K = list(map(int, input().split()))
  
  MOD = 10**9 + 7
  
  
  @lru_cache(maxsize=None)
  def modInverse(a, p):
      # Fermat's little theorem, a**(p-1) = 1 mod p
      return pow(a, p - 2, p)
  
  
  if CHECK:
      fact = [1]
      for i in range(1, 2 * N + 1):
          fact.append((fact[-1] * i) % MOD)
  
      def nCr(n, r, p=MOD):
          # Modulo binomial coefficients
          return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p
  
  
  if N - 1 <= K:
      # Any combo is achievable so this is stars and bars
      # N people into N rooms, which means N - 1 dividers
      stars = N
      bars = N - 1
      print(nCr(stars + bars, bars))
  else:
      # Group by number of empty rooms
      # With K moves there can only be at most K empty rooms
      # Max of N - 1 empty rooms in general
      assert K + 1 < N
      tot = 0
      comb1 = 1
      comb2 = 1
      for numEmpty in range(K + 1):
          way3 = comb1 * comb2
          if CHECK:
              numNonEmpty = N - numEmpty
              stars = numEmpty  # Everyone moving into an occupied room
              bars = numNonEmpty - 1  # Number of dividers
              way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)
  
              way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)
  
              assert way1 % MOD == way2 % MOD == way3 % MOD
          tot += way3
  
          j = numEmpty + 1
          invJ = modInverse(j, MOD)
          comb1 = (N + 1 - j) * comb1 * invJ % MOD
          comb2 = (N - j) * comb2 * invJ % MOD
      print(tot % MOD)
  
problem_description: Statement
  
  There is a building with n rooms, numbered 1 to n.
  
  We can move from any room to any other room in the building.
  
  Let us call the following event a **move** : a person in some room i goes to
  another room j~ (i \neq j).
  
  Initially, there was one person in each room in the building.
  
  After that, we know that there were exactly k moves happened up to now.
  
  We are interested in the number of people in each of the n rooms now. How many
  combinations of numbers of people in the n rooms are possible?
  
  Find the count modulo (10^9 + 7).
samples: [{"input": "3 2", "output": "10\n    \n\nLet c_1, c_2, and c_3 be the number of people in Room 1, 2, and 3 now,\nrespectively. There are 10 possible combination of (c_1, c_2, c_3):\n\n  * (0, 0, 3)\n  * (0, 1, 2)\n  * (0, 2, 1)\n  * (0, 3, 0)\n  * (1, 0, 2)\n  * (1, 1, 1)\n  * (1, 2, 0)\n  * (2, 0, 1)\n  * (2, 1, 0)\n  * (3, 0, 0)\n\nFor example, (c_1, c_2, c_3) will be (0, 1, 2) if the person in Room 1 goes to\nRoom 2 and then one of the persons in Room 2 goes to Room 3.\n\n* * *"}, {"input": "200000 1000000000", "output": "607923868\n    \n\nPrint the count modulo (10^9 + 7).\n\n* * *"}, {"input": "15 6", "output": "22583772"}]