You have d dice, and each die has f faces numbered 1, 2, ..., f.
Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.
 
Example 1:
Input: d = 1, f = 6, target = 3
Output: 1
Explanation: 
You throw one die with 6 faces.  There is only one way to get a sum of 3.

Example 2:
Input: d = 2, f = 6, target = 7
Output: 6
Explanation: 
You throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:
1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:
Input: d = 2, f = 5, target = 10
Output: 1
Explanation: 
You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.

Example 4:
Input: d = 1, f = 2, target = 3
Output: 0
Explanation: 
You throw one die with 2 faces.  There is no way to get a sum of 3.

Example 5:
Input: d = 30, f = 30, target = 500
Output: 222616187
Explanation: 
The answer must be returned modulo 10^9 + 7.

 
Constraints:

1 <= d, f <= 30
1 <= target <= 1000

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        

Solutions:
from math import comb
from math import pow

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target < d * 1 or target > d * f:
			return 0
		target = target - d
		sum = 0
		i = 0
		j = 0
		while i <= target:
			y = target - i
			if j % 2 == 0:
				sum = int(sum + comb(d, j) * comb(y + d - 1, y))
			else:
				sum = int(sum - comb(d, j) * comb(y + d - 1, y))
			j = j + 1
			i = i + f
		return int(sum) % 1000000007


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target < d or target > d * f:
			return 0
		total_sum = 0
		cache_sum = []
		if target > d * (1 + f) / 2:
			target = d * (1 + f) - target
		for i in range(target, -1, -1):
			num = 0 if i > f else 1
			total_sum += num
			cache_sum.append(total_sum)
		cache_sum = cache_sum[::-1]
		cache_sum[0] = cache_sum[1]
		for i in range(2, d + 1):
			total_sum = 0
			for j in range(target, -1, -1):
				total_sum += cache_sum[max(j - f, 0)] - cache_sum[j]
				cache_sum[j] = total_sum
		return cache_sum[-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		@lru_cache(None)
		def solve(s, t):
			if s == 0:
				if t == 0:
					return 1
				return 0
			ans = 0
			for i in range(1, f + 1):
				if t >= i:
					ans += solve(s - 1, t - i)
			return ans
		return solve(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = {0: 1}
		MOD = 10 ** 9 + 7
		for i in range(d):
			ndp = {}
			for (k, v) in list(dp.items()):
				for w in range(1, f + 1):
					if k + w <= target:
						ndp[k + w] = (ndp.get(k + w, 0) + dp[k]) % MOD
			dp = ndp.copy()
		return dp.get(target, 0)


class Solution:
	seen = {}

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		results = {}
		results[1] = {}
		for i in range(1, min(f, target) + 1):
			results[1][i] = 1
		for i in range(2, d + 1):
			results[i] = {}
			for (val, times) in list(results[i - 1].items()):
				for j in range(1, min(f, target) + 1):
					results[i][j + val] = results[i].get(j + val, 0) + times
		return results[d].get(target, 0) % 1000000007


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		return memoization(d, f, target)
from functools import lru_cache
mod = 10 ** 9 + 7

@lru_cache(maxsize=None)
def memoization(d, f, t):
	if d == 0:
		return int(t == 0)
	return sum((memoization(d - 1, f, t - v) for v in range(1, f + 1))) % mod


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		@lru_cache(maxsize=None)
		def dp(d, t):
			print((d, t))
			if d == 0:
				return 1 if t == 0 else 0
			return sum((dp(d - 1, t - x) for x in range(1, f + 1)))
		return dp(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mem = collections.defaultdict(int)
		mem[0] = 1
		for i in range(d):
			curr = collections.defaultdict(int)
			for face in range(1, f + 1):
				for (val, count) in list(mem.items()):
					newVal = face + val
					if newVal <= target:
						curr[newVal] += count
			mem = curr
		return mem[target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0] * (target + 1) for i in range(d + 1)]
		MOD = 1000000007
		dp[0][0] = 1
		for dice in range(1, d + 1):
			for target in range(1, target + 1):
				if target > dice * f:
					continue
				else:
					face = 1
					while face <= f and face <= target:
						dp[dice][target] = (dp[dice][target] + dp[dice - 1][target - face]) % MOD
						face += 1
		return dp[-1][-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		MOD = 10 ** 9 + 7
		dp = [0] * (target + 1)
		dp[0] = 1
		for i in range(1, d + 1):
			if target < i:
				break
			t = min(i * f, target)
			dp[t] = sum((dp[t - j] for j in range(max(1, t - (i - 1) * f), min(f, t - i + 1) + 1))) % MOD
			for t in reversed(range(i, t)):
				dp[t] = dp[t + 1] - dp[t] + (dp[t - f] if t - f >= i - 1 else 0)
		return dp[target]


class Solution:

	def numRollsToTarget(self, d, f, target):
		dp = [0] * (target + 1)
		dp[0] = 1
		for i in range(d):
			for j in range(target, -1, -1):
				tot = 0
				for k in range(1, 1 + min(f, j)):
					tot += dp[j - k]
				dp[j] = tot
		return dp[target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target > d * f:
			return 0
		if target == d * f:
			return 1
		if d == 1:
			return 1
		if f > target:
			f = target
		MOD = 10 ** 9 + 7
		dp = [[0 for j in range(d * f + 1 + 1)] for i in range(d + 1)]
		for i in range(1, f + 1):
			dp[1][i] = 1
		for i in range(d + 1):
			for j in range(d * f + 1 + 1):
				for t in range(1, f + 1):
					if j - t >= i - 1:
						dp[i][j] += dp[i - 1][j - t] % MOD
		return dp[d][target] % MOD


class Solution:

	@lru_cache(None)
	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d == 0 or target <= 0:
			return d == 0 and target == 0
		res = 0
		for i in range(1, f + 1):
			res = (res + self.numRollsToTarget(d - 1, f, target - i)) % (10 ** 9 + 7)
		return res


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def helper(rolls_left, t):
			if not t and (not rolls_left):
				return 1
			if not rolls_left or not t:
				return 0
			ret = 0
			for v in range(1, min(f + 1, t + 1)):
				if (rolls_left - 1, t - v) not in memo:
					memo[rolls_left - 1, t - v] = helper(rolls_left - 1, t - v)
				ret += memo[rolls_left - 1, t - v]
			return ret
		return helper(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		modulo = 1000000007
		memo = {}

		def recurseRoll(d, target):
			if d < 0:
				return 0
			if target < 0:
				return 0
			if target == 0 and d == 0:
				return 1
			s = 0
			for i in range(1, f + 1):
				if (d - 1, target - i) in memo:
					s += memo[d - 1, target - i]
				else:
					s += recurseRoll(d - 1, target - i)
			memo[d, target] = s
			return s
		return recurseRoll(d, target) % modulo


from functools import lru_cache

class Solution:

	@lru_cache
	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0] * (target + 1) for _ in range(d + 1)]
		dp[0][0] = 1
		for i in range(1, d + 1):
			for j in range(target + 1):
				if dp[i - 1][j] > 0:
					for k in range(1, f + 1):
						if j + k <= target:
							dp[i][j + k] += dp[i - 1][j]
							dp[i][j + k] %= 10 ** 9 + 7
		return dp[d][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dpMatrix = [[0 for i in range(target + 1)] for i in range(d)]
		for i in range(1, min(f + 1, len(dpMatrix[0]))):
			dpMatrix[0][i] = 1
		for i in range(1, len(dpMatrix)):
			for j in range(1, len(dpMatrix[0])):
				calcSum = 0
				for k in range(j - 1, max(-1, j - f - 1), -1):
					calcSum += dpMatrix[i - 1][k]
				dpMatrix[i][j] = calcSum
		return dpMatrix[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def helper(d, target):
			if d == 0:
				return 0 if target > 0 else 1
			if (d, target) in memo:
				return memo[d, target]
			to_return = 0
			for k in range(max(0, target - f), target):
				to_return += helper(d - 1, k)
			memo[d, target] = to_return
			return to_return
		return helper(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mem = {(0, 0): 1}

		def find(d: int, target: int):
			if (d, target) in mem:
				return mem[d, target]
			if d == 0:
				return 0
			res = 0
			d -= 1
			for i in range(1, min(target - d, f) + 1):
				res += find(d, target - i)
			mem[d + 1, target] = res
			return res
		return find(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp_map = {}
		for i in range(target):
			dp_map[1, i + 1] = 0
		for i in range(f):
			dp_map[1, i + 1] = 1

		def recurse_with_mem(d, target):
			if (d, target) in dp_map:
				return dp_map[d, target]
			if target <= 0:
				return 0
			num_ways = 0
			for i in range(f):
				num_ways += recurse_with_mem(d - 1, target - i - 1)
			dp_map[d, target] = num_ways
			return num_ways
		return recurse_with_mem(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def dp(d, target):
			nonlocal memo, f
			if d == 0:
				return 1 if target == 0 else 0
			if (d, target) in memo:
				return memo[d, target]
			res = 0
			for i in range(max(0, target - f), target):
				res += dp(d - 1, i)
			memo[d, target] = res
			return res
		return dp(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d > target or d * f < target:
			return 0
		if f > target:
			f = target
		memo = [[0 for _ in range(target)] for _ in range(d)]
		for i in range(f):
			memo[0][i] = 1
		for (i, row) in enumerate(memo[1:]):
			for (j, _2) in enumerate(row):
				if j - f < 0:
					memo[i + 1][j] = sum(memo[i][0:j]) % 1000000007
				else:
					memo[i + 1][j] = sum(memo[i][j - f:j]) % 1000000007
		return memo[-1][-1] % 1000000007


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		self.mapx = {}
		return self.rec(d, f, target)

	def rec(self, d, f, target):
		if d == 0:
			if target == 0:
				return 1
			return 0
		count = 0
		for num in range(1, f + 1):
			if target - num >= 0:
				nextState = (d - 1, target - num)
				if nextState not in self.mapx:
					count += self.rec(d - 1, f, target - num)
				else:
					count += self.mapx.get(nextState, 0)
		count = count % 1000000007
		self.mapx[d, target] = count
		return count


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		cache = {}

		def helper(d, target):
			if d == 0 and target == 0:
				return 1
			if d == 0:
				return 0
			if (d, target) in cache:
				return cache[d, target]
			result = 0
			for i in range(max(0, target - f), target):
				result += helper(d - 1, i)
			cache[d, target] = result
			return result
		return helper(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		self.dic = {}
		self.f = f
		return self.dfs(d, target) % (10 ** 9 + 7)

	def dfs(self, dices, tar):
		if (dices, tar) in self.dic:
			return self.dic[dices, tar]
		elif tar < 0:
			return 0
		elif dices == 1 and tar <= self.f:
			return 1
		elif dices == 1:
			return 0
		else:
			r = 0
			for i in range(1, min(self.f + 1, tar)):
				r += self.dfs(dices - 1, tar - i)
			self.dic[dices, tar] = r
			return r


class Solution:

	def numRollsToTarget(self, k: int, f: int, target: int) -> int:
		d = {}

		def h(x, t):
			v = (x, t)
			if v in d:
				return d[v]
			if x == 0 and t == 0:
				return 1
			if x == 0 or t == 0:
				return 0
			s = 0
			for i in range(1, f + 1):
				s += h(x - 1, t - i)
			d[v] = s
			return s
		x = h(k, target)
		return x % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		D = {}

		def func(d, f, target):
			res = 0
			if d == 0 and target == 0:
				return 1
			if d == 0 and target != 0:
				return 0
			if target < 0:
				return 0
			for i in range(1, f + 1):
				if (d - 1, target - i) not in D:
					D[d - 1, target - i] = func(d - 1, f, target - i)
				res += D[d - 1, target - i]
				res = res % (10 ** 9 + 7)
			return res
		return func(d, f, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		prev_dp = [0] * (target + 1)
		prev_dp[0] = 1
		for num_dice in range(1, d + 1):
			curr_dp = [0] * (target + 1)
			for face in range(1, f + 1):
				for total in range(face, target + 1):
					curr_dp[total] = (curr_dp[total] + prev_dp[total - face]) % (10 ** 9 + 7)
			prev_dp = curr_dp
		return prev_dp[-1]


class Solution:

	def numRollsToTarget(self, d, f, target, result=0):
		MOD = 7 + 1000000000.0
		dp = [0] * (1 + target)
		dp[0] = 1
		for i in range(1, 1 + d):
			newDP = [0] * (1 + target)
			prev = dp[0]
			for j in range(1, 1 + target):
				newDP[j] = prev
				prev = (prev + dp[j]) % MOD
				if j >= f:
					prev = (prev - dp[j - f] + MOD) % MOD
			dp = newDP
		return int(dp[-1])


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		DP = {}

		def get_rolls(n, t):
			if n == 1:
				if 0 < t <= f:
					return 1
				return 0
			if (n, t) in DP:
				return DP[n, t]
			total = 0
			for i in range(1, f + 1):
				total += get_rolls(n - 1, t - i)
			DP[n, t] = total
			return total
		return get_rolls(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp1 = [0] * (target + 1)
		dp2 = [0] * (target + 1)
		dp1[0] = 1
		for i in range(1, d + 1):
			for j in range(1, target + 1):
				for k in range(1, min(j, f) + 1):
					dp2[j] = dp2[j] + dp1[j - k]
			dp1 = dp2
			dp2 = [0] * (target + 1)
		return dp1[target] % (10 ** 9 + 7)


class Solution:

	def __init__(self):
		self.dp = []

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		for dice in range(0, d + 1):
			self.dp.append([-1] * (target + 1))
		return self.rollDice(d, f, target) % (10 ** 9 + 7)

	def rollDice(self, d: int, f: int, target: int) -> int:
		if self.dp[d][target] != -1:
			return self.dp[d][target]
		if d == 1:
			if f >= target:
				return 1
			else:
				return 0
		self.dp[d][target] = 0
		for nextRoll in range(1, f + 1):
			if target - nextRoll > 0:
				self.dp[d][target] += self.rollDice(d - 1, f, target - nextRoll)
		return self.dp[d][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def find_next(dice_left, current_val):
			if current_val > target:
				return 0
			if dice_left == 0:
				if current_val == target:
					return 1
				return 0
			if (dice_left, current_val) not in seen:
				combinations = 0
				for i in range(1, f + 1):
					combinations += find_next(dice_left - 1, current_val + i)
				seen[dice_left, current_val] = combinations % 1000000007
			return seen[dice_left, current_val]
		seen = {}
		return find_next(d, 0)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		bottomWidth = f + (d - 1) * (f - 1)
		currentLayer = [0 for i in range(bottomWidth)] + [1 for i in range(f)] + [0 for i in range(bottomWidth)]
		nextLayer = []
		for run in range(d - 1):
			for i in range(f, len(currentLayer) - f):
				localSum = 0
				for j in range(i, f + i):
					localSum += currentLayer[j]
				nextLayer += [localSum]
			neededZeros = [0 for i in range((len(currentLayer) - len(nextLayer)) // 2)]
			currentLayer = neededZeros + nextLayer + neededZeros
			nextLayer = []
		while 0 in currentLayer:
			currentLayer.remove(0)
		if target - d >= len(currentLayer):
			return 0
		else:
			return currentLayer[target - d] % (10 ** 9 + 7)


class Solution:

	def numRolls(self, d, f, target, memo):
		if target < d:
			return 0
		if d == 1:
			return int(target <= f)
		if (d, f, target) in memo:
			return memo[d, f, target]
		total = 0
		for new_target in range(target - f, target):
			total += self.numRolls(d - 1, f, new_target, memo)
			total = total % (10 ** 9 + 7)
		memo[d, f, target] = total
		return total

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}
		ans = self.numRolls(d, f, target, memo)
		return ans


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = defaultdict(int)

		def solve(d, f, target):
			if (d, f, target) in memo:
				return memo[d, f, target]
			if d == 0:
				if target != 0:
					return 0
				else:
					return 1
			dp = 0
			for i in range(1, f + 1):
				dp += solve(d - 1, f, target - i)
			memo[d, f, target] = dp
			return dp
		return solve(d, f, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [1 if i < f else 0 for i in range(target)]
		for n in range(2, d + 1):
			new_dp = [0 for _ in range(target)]
			cumsum = 0
			for i in range(target - 1):
				cumsum += dp[i]
				if i >= f:
					cumsum -= dp[i - f]
				new_dp[i + 1] = cumsum
			dp = new_dp
		return dp[-1] % (10 ** 9 + 7)


class Solution:

	def helper(self, d, f, target):
		if d == 0:
			if target == 0:
				return 1
			else:
				return 0
		if (d, target) in self.memo:
			return self.memo[d, target]
		count = 0
		for i in reversed(list(range(1, min(target + 1, f + 1)))):
			count += self.helper(d - 1, f, target - i)
		self.memo[d, target] = count
		return count

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		self.memo = dict()
		return self.helper(d, f, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		return self.recurse(d, 0, f, 0, target, {}) % (10 ** 9 + 7)

	def recurse(self, dices, dno, faces, cursum, target, cache):
		if cursum > target:
			return 0
		if dno == dices:
			if cursum == target:
				return 1
			return 0
		if (dno, cursum) in cache:
			return cache[dno, cursum]
		ways = 0
		for curface in range(1, faces + 1):
			ways += self.recurse(dices, dno + 1, faces, cursum + curface, target, cache)
		cache[dno, cursum] = ways
		return ways


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}
		return self.num_rolls_util(memo, d, f, target, 0, 0)

	def num_rolls_util(self, memo, d, f, target, level, cur_sum):
		if level == d:
			return cur_sum == target
		if (level, cur_sum) in memo:
			return memo[level, cur_sum]
		res = 0
		for i in range(1, f + 1):
			if cur_sum + i <= target:
				res += self.num_rolls_util(memo, d, f, target, level + 1, cur_sum + i)
		memo[level, cur_sum] = res
		return res % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		store = {}

		def helper(d, f, target):
			if d == 0 or f == 0 or target <= 0:
				return 0
			if d == 1 and target > f:
				return 0
			if d == 1 and target <= f:
				return 1
			if (d, f, target) in store:
				return store[d, f, target]
			n = 0
			for i in range(1, f + 1):
				n += helper(d - 1, f, target - i)
			store[d, f, target] = n
			return n
		return helper(d, f, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def dfs(n, t):
			if n == 0:
				return t == 0
			if (n, t) in memo:
				return memo[n, t]
			ret = 0
			for face in range(1, f + 1):
				ret += dfs(n - 1, t - face)
			memo[n, t] = ret % (10 ** 9 + 7)
			return memo[n, t]
		return dfs(d, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def backtrack(index=d - 1, target=target, dp={}):
			if index == -1 and target == 0:
				return 0
			if index < 0 or target <= 0:
				return None
			if (index, target) in dp:
				return dp[index, target]
			if target > f:
				start = f
			else:
				start = target
			count = 0
			for i in range(start, 0, -1):
				res = backtrack(index - 1, target - i, dp)
				if res != None:
					count += res if res else 1
			dp[index, target] = count if count else None
			return dp[index, target]
		count = backtrack()
		return count % (10 ** 9 + 7) if count != None else 0


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def helper(d, target):
			if d == 0 and target == 0:
				return 1
			if d == 0:
				return 0
			if (target, d) in memo:
				return memo[target, d]
			num_ways = 0
			for i in range(1, f + 1):
				if target - i >= 0:
					num_ways += helper(d - 1, target - i)
			memo[target, d] = num_ways
			return num_ways
		return helper(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [0] * (target + 1)
		dp[0] = 1
		for i in range(1, d + 1):
			temp = [0] * (target + 1)
			for j in range(1, target + 1):
				temp[j] = sum((dp[j - k] if k <= j else 0 for k in range(1, f + 1)))
			dp = temp
		return dp[target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target > 900:
			return 0
		memo = {}

		def dfs(dice, t):
			if dice == 0 and t == 0:
				return 1
			if dice == 0 or t == 0:
				return 0
			if (dice, t) in memo:
				return memo[dice, t]
			count = 0
			for n in range(1, f + 1):
				count += dfs(dice - 1, t - n)
			memo[dice, t] = count % (10 ** 9 + 7)
			return memo[dice, t]
		return dfs(d, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		modulo = 10 ** 9 + 7
		dp = [[0 for i in range(target + 1)] for j in range(d + 1)]
		for dd in range(1, d + 1):
			for tt in range(dd, min(f * dd, target) + 1):
				if dd == 1:
					dp[dd][tt] = 1
				else:
					end = tt - 1
					start = max(1, tt - f)
					dp[dd][tt] = sum(dp[dd - 1][start:end + 1])
		return dp[d][target] % modulo


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mem = {}

		def dfs(l, target):
			if (l, target) in mem:
				return mem[l, target]
			if l == d:
				return int(target == 0)
			MOD = 1000000000.0 + 7
			ans = 0
			for i in range(1, f + 1):
				ans = (ans + dfs(l + 1, target - i)) % MOD
			mem[l, target] = ans
			return ans
		return int(dfs(0, target))


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def count_for_roll(num_dice, curr_target):
			if num_dice == 0 and curr_target == 0:
				return 1
			if num_dice == 0 or curr_target == 0:
				return 0
			if (num_dice, curr_target) in memo:
				return memo[num_dice, curr_target]
			curr_count = 0
			for face in range(1, f + 1):
				new_target = curr_target - face
				if new_target < 0:
					break
				curr_count += count_for_roll(num_dice - 1, new_target)
			memo[num_dice, curr_target] = curr_count
			return curr_count % mod
		memo = {}
		mod = 10 ** 9 + 7
		return count_for_roll(d, target)


class Solution:

	def helper(self, d, f, target, cursum, dp):
		if d == 0:
			if target == cursum:
				return 1
			else:
				return 0
		if cursum > target:
			return 0
		cnt = 0
		if (d, cursum) in dp:
			return dp[d, cursum]
		for i in range(1, f + 1):
			cnt += self.helper(d - 1, f, target, cursum + i, dp)
		dp[d, cursum] = cnt % (pow(10, 9) + 7)
		return cnt % (pow(10, 9) + 7)

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = {}
		return self.helper(d, f, target, 0, dp)


from collections import defaultdict

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = defaultdict(int)

		def helper(d, target):
			if d == 0:
				return 1 if target == 0 else 0
			if (d, target) in memo:
				return memo[d, target]
			for c in range(max(0, target - f), target):
				memo[d, target] += helper(d - 1, c)
			return memo[d, target]
		return helper(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		cache = {}

		def helper(d, target):
			if target == 0 and d == 0:
				return 1
			if d == 0:
				return 0
			if (d, target) in cache:
				return cache[d, target]
			ways = 0
			for i in range(1, f + 1):
				if target - i >= 0:
					ways = (ways + helper(d - 1, target - i)) % 1000000007
			cache[d, target] = ways
			return cache[d, target]
		return helper(d, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}
		MOD = pow(10, 9) + 7

		def dfs(d_left=d, target_left=target):
			if (d_left, target_left) in memo:
				return memo[d_left, target_left]
			if not d_left:
				return 1 if not target_left else 0
			else:
				memo[d_left, target_left] = 0
				for face in range(1, min(f + 1, target_left + 1)):
					memo[d_left, target_left] += dfs(d_left - 1, target_left - face)
				return memo[d_left, target_left]
		return dfs() % MOD


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		BASE = 10 ** 9 + 7
		memo = {(0, 0): 1}

		def dfs(num, tar):
			nonlocal BASE
			if (num, tar) in memo:
				return memo[num, tar]
			if num == 0 or tar == 0:
				return -1
			cnt = 0
			for i in range(1, f + 1):
				sub = dfs(num - 1, tar - i)
				if sub != -1:
					cnt += sub
			memo[num, tar] = cnt % BASE
			return memo[num, tar]
		dfs(d, target)
		return memo[d, target]


class Solution:

	def numRollsToTarget(self, D: int, F: int, target: int) -> int:
		dp = [[0] * (target + 1) for _ in range(2)]
		dp[0][0] = 1
		for d in range(1, D + 1):
			cd = d & 1
			pd = d - 1 & 1
			dp[cd][0] = 0
			for t in range(1, target + 1):
				dp[cd][t] = (dp[cd][t - 1] + dp[pd][t - 1] - (dp[pd][t - F - 1] if t - F - 1 >= 0 else 0)) % 1000000007
		return dp[D & 1][target]

	def numRollsToTarget(self, D: int, F: int, target: int) -> int:
		dp = [0] * (target + 1)
		dp[0] = 1
		for d in range(1, D + 1):
			ndp = [0] * (target + 1)
			for i in range(1, target + 1):
				ndp[i] = sum((dp[i - f] for f in range(1, F + 1) if i - f >= 0)) % 1000000007
			dp = ndp
		return dp[-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		self.map = collections.defaultdict(int)
		return self.noOfWays(d, f, target)

	def noOfWays(self, d, f, target):
		if d == 0 and target == 0:
			return 1
		elif d == 0:
			return 0
		if (d, target) in self.map:
			return self.map[d, target]
		res = 0
		for i in range(1, f + 1):
			res += self.noOfWays(d - 1, f, target - i)
		self.map[d, target] = res
		return res % (10 ** 9 + 7)


MOD = 10 ** 9 + 7

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		ways = [0] + [1] * min(f, target) + [0] * max(target - f, 0)
		for _ in range(d - 1):
			for i in reversed(range(1, target + 1)):
				ways[i] = 0
				for j in range(1, min(i, f + 1)):
					ways[i] = (ways[i] + ways[i - j]) % MOD
		return ways[target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}
		mod = int(math.pow(10, 9) + 7)

		def recur(d, target):
			if (d, target) in memo:
				return memo[d, target]
			if d < 0 or target < 0:
				return 0
			if d == 0 and target == 0:
				return 1
			ways = 0
			for i in range(1, f + 1):
				if target - i < 0:
					break
				ways = int(ways + recur(d - 1, target - i)) % mod
			memo[d, target] = ways
			return ways
		return recur(d, target)


class Solution:

	@lru_cache(None)
	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [1] + [0] * target
		mod = 10 ** 9 + 7
		for _ in range(d):
			for i in range(target, -1, -1):
				dp[i] = sum((dp[i - ff] for ff in range(1, f + 1) if i >= ff)) % mod
		return dp[-1] % mod
		dp = [[0] * (target + 1) for _ in range(d + 1)]
		mod = 10 ** 9 + 7
		dp[0][0] = 1
		for i in range(1, d + 1):
			for j in range(1, target + 1):
				dp[i][j] = sum((dp[i - 1][j - ff] for ff in range(1, f + 1) if j >= ff))
		return dp[-1][-1] % mod


class Solution:

	def __init__(self):
		self.memo = {}

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		res = 0
		if (d, target) in self.memo:
			return self.memo[d, target]
		for i in range(1, f + 1):
			if target - i == 0 and d == 1:
				res += 1
			elif target - i > 0 and d > 1:
				res += self.numRollsToTarget(d - 1, f, target - i)
		self.memo[d, target] = res
		return res % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
		for dd in range(1, d + 1):
			for tt in range(dd, min(f * dd, target) + 1):
				if dd == 1:
					dp[dd][tt] = 1
				else:
					dp[dd][tt] = sum(dp[dd - 1][max(1, tt - f):tt])
		return dp[d][target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		self.cache = {}
		return self.helper(0, 0, d, f, target) % (10 ** 9 + 7)

	def helper(self, currD, currSum, d, f, target):
		if currD == d:
			return currSum == target
		if currD in self.cache and currSum in self.cache[currD]:
			return self.cache[currD][currSum]
		ways = 0
		for i in range(1, f + 1):
			ways += self.helper(currD + 1, currSum + i, d, f, target)
		if currD not in self.cache:
			self.cache[currD] = {}
		self.cache[currD][currSum] = ways
		return ways


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0] * (target + 1) for _ in range(d + 1)]
		dp[0][0] = 1
		for i in range(1, d + 1):
			for j in range(1, target + 1):
				dp[i][j] = sum((dp[i - 1][j - k] for k in range(1, min(f, j) + 1)))
		return dp[-1][-1] % (10 ** 9 + 7)


from math import comb

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dic = {}
		return self.helper(d, f, target, dic)

	def helper(self, d2, f2, target2, dic):
		if target2 == 0 and d2 == 0:
			return 1
		if (d2, f2, target2) in dic:
			return dic[d2, f2, target2]
		if target2 < d2 or d2 * f2 < target2:
			dic[d2, f2, target2] = 0
			return 0
		elif d2 == 1:
			dic[d2, f2, target2] = 1
			return 1
		tot = 0
		for i in range(0, d2 + 1):
			num_poss = self.helper(d2 - i, f2 - 1, target2 - i * f2, dic) * comb(d2, i)
			tot += num_poss % (10 ** 9 + 7)
		dic[d2, f2, target2] = tot % (10 ** 9 + 7)
		return tot % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for x in range(d + 1)] for y in range(target + 1)]
		for i in range(1, min(f + 1, target + 1)):
			dp[i][1] = 1
		for i in range(1, target + 1):
			for j in range(2, d + 1):
				val = 0
				for k in range(1, f + 1):
					if i - k >= 0:
						val += dp[i - k][j - 1]
				dp[i][j] = val
		return dp[target][d] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [0 for _ in range(target + 1)]
		dp[0] = 1
		for i in range(1, d + 1):
			new = [0]
			for j in range(1, target + 1):
				new.append(0)
				for k in range(1, f + 1):
					if j - k >= 0:
						new[-1] += dp[j - k]
			dp = new
		return dp[-1] % (10 ** 9 + 7)
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(target + 1)]]
		for i in range(1, min(f + 1, target + 1)):
			dp[0][i] = 1
		for i in range(2, d + 1):
			dp.append([0 for _ in range(target + 1)])
			for t in range(i, target + 1):
				for d in range(1, min(t, f + 1, target + 1)):
					if t - d >= 0 and dp[-2][t - d]:
						dp[-1][t] += dp[-2][t - d]
					else:
						0
			dp.pop(0)
		for row in dp:
			0
		return dp[0][-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = [0] * (target + 1)
		memo[0] = 1
		maxV = 10 ** 9 + 7
		for _ in range(d):
			for tv in range(target, -1, -1):
				memo[tv] = 0
				for fv in range(1, f + 1):
					memo[tv] += memo[tv - fv] if tv - fv >= 0 else 0
				memo[tv] %= maxV
		return memo[-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		n = target
		ways = [[0 for i in range(n + 1)] for j in range(d + 1)]
		ways[0][0] = 1
		for i in range(1, d + 1):
			for j in range(n + 1):
				c = 0
				for k in range(1, f + 1):
					c += ways[i - 1][j - k] if j - k >= 0 else 0
				ways[i][j] = c
		return ways[d][n] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [0] * (target + 1)
		dp[0] = 1
		M = 10 ** 9 + 7
		for i in range(d):
			n_dp = [0] * (target + 1)
			for j in range(target + 1):
				for m in range(1, f + 1):
					if j + m > target:
						break
					n_dp[j + m] += dp[j]
			dp = [k % M for k in n_dp]
		return dp[-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [0] * (target + 1)
		dp[0] = 1
		for i in range(d):
			dp_new = [0] * len(dp)
			for i in range(1, len(dp)):
				for j in range(1, f + 1):
					if i - j >= 0:
						dp_new[i] = (dp_new[i] + dp[i - j]) % (10 ** 9 + 7)
			dp = dp_new
		return dp[-1] % (10 ** 9 + 7)


class Solution:
	cache = {}

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d == 1:
			if f < target:
				return 0
			else:
				return 1
		if (d, f, target) in self.cache:
			return self.cache[d, f, target]
		else:
			num = sum((self.numRollsToTarget(d - 1, f, target - i) for i in range(1, min(f + 1, target)))) % (10 ** 9 + 7)
			self.cache[d, f, target] = num
		return num


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = {}
		for k in range(1, f + 1):
			dp[1, k] = 1

		def dfs_num_rolls(dice_left, tot_left):
			if tot_left > f ** dice_left or tot_left < 0 or dice_left == 0:
				dp[dice_left, tot_left] = 0
				return 0
			if (dice_left, tot_left) in dp:
				return dp[dice_left, tot_left]
			total = 0
			for k in range(1, f + 1):
				total += dfs_num_rolls(dice_left - 1, tot_left - k) % (10 ** 9 + 7)
			total = total % (10 ** 9 + 7)
			dp[dice_left, tot_left] = total
			return total
		dfs_num_rolls(d, target)
		return dp[d, target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def rec(d, target):
			if d == 0:
				if target == 0:
					return 1
				else:
					return 0
			if target <= 0:
				return 0
			if (d, target) in memo:
				return memo[d, target]
			count = 0
			for i in range(1, f + 1):
				count += rec(d - 1, target - i)
			memo[d, target] = count
			return count
		return rec(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0] * (target + 1) for _ in range(d)]
		l = min(target + 1, f + 1)
		for i in range(1, l):
			dp[0][i] = 1
		for level in range(1, d):
			for face in range(1, f + 1):
				for t in range(1, target + 1):
					if t - face > 0:
						dp[level][t] += dp[level - 1][t - face]
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def helper(d, target, map):
			if (d, target) in map:
				return map[d, target]
			if d == target:
				return 1
			elif d == 0 or target < d:
				return 0
			map[d, target] = 0
			for num in range(1, f + 1):
				map[d, target] += helper(d - 1, target - num, map)
			return map[d, target]
		helperMap = {}
		return helper(d, target, helperMap) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mod = 10 ** 9 + 7
		dp = [[0] * (target + 1) for i in range(d + 1)]
		dp[0][0] = 1
		for i in range(1, d + 1):
			nxt = [[0] * (target + 1) for i in range(d + 1)]
			for j in range(1, target + 1):
				nxt[i][j] = sum((dp[i - 1][j - x] for x in range(1, f + 1) if j >= x)) % mod
			dp = nxt
		return dp[-1][-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0] * (target + 1) for i in range(d)]
		for i in range(1, min(target + 1, f + 1)):
			dp[0][i] = 1
		for i in range(1, d):
			for j in range(1, target + 1):
				for num in range(1, f + 1):
					if j - num >= 0:
						dp[i][j] += dp[i - 1][j - num]
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = dict()

		def fun(d, target):
			mod = int(1000000000.0 + 7)
			if target == 0 and d == 0:
				return 1
			if target == 0 and d != 0:
				return 0
			if target < 0:
				return 0
			if d == 0:
				return 0
			if (d, target) in dp:
				return dp[d, target]
			tmp = 0
			for i in range(1, f + 1):
				tmp += fun(d - 1, target - i) % mod
				tmp %= mod
			dp[d, target] = tmp
			return tmp
		return fun(d, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		arr = [[0 for i in range(target + 1)] for i in range(d)]
		for i in range(1, min(f, target) + 1):
			arr[0][i] = 1
		for row in range(1, d):
			temp = 0
			for col in range(row + 1, target + 1):
				temp += arr[row - 1][col - 1]
				if col >= f + 1:
					temp -= arr[row - 1][col - f - 1]
				arr[row][col] = temp
		return arr[d - 1][target] % 1000000007


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d > target or (d == 1 and target > f):
			return 0
		if d == target or d == 1:
			return 1
		dp = [[0 for i in range(target + 1)] for j in range(2)]
		dp_1 = [0 for i in range(target + 1)]
		for i in range(1, min(target + 1, f + 1)):
			dp_1[i] = 1
		dp[0] = dp_1
		for i in range(2, d + 1):
			dp[1] = [0 for i in range(target + 1)]
			for j in range(i, target + 1):
				if i == j:
					dp[1][j] = 1
					continue
				for k in range(1, min(j + 1, f + 1)):
					dp[1][j] += dp[0][j - k] * dp_1[k]
			dp[0] = dp[1]
		return dp[1][-1] % 1000000007


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0] * target for _ in range(d)]
		for i in range(d):
			for j in range(target):
				if i == 0 and j + 1 <= f:
					dp[i][j] = 1
				elif i == 0:
					dp[i][j] = 0
				elif j >= i:
					for k in range(1, f + 1):
						if j - k >= 0:
							dp[i][j] += dp[i - 1][j - k]
		return dp[d - 1][target - 1] % 1000000007


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		opt = [[0] * (target + 1) for _ in range(d + 1)]
		opt[0][0] = 1
		mod = 10 ** 9 + 7
		for i in range(1, d + 1):
			for j in range(1, target + 1):
				sum_children = 0
				face_val = 1
				while face_val <= f and j - face_val >= 0:
					sum_children += opt[i - 1][j - face_val] % mod
					face_val += 1
				opt[i][j] = sum_children % mod
		return opt[d][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def num_rolls_util(level, target):
			if level * f < target or target < level:
				return 0
			if level == 0:
				return 1
			res = 0
			for i in range(max(0, target - f), target):
				if (level - 1, i) in memo:
					res += memo[level - 1, i]
				else:
					tmp = num_rolls_util(level - 1, i)
					memo[level - 1, i] = tmp
					res += tmp
			return res % (10 ** 9 + 7)
		return num_rolls_util(d, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(max(target + 1, f + 1))] for _ in range(d + 1)]
		for i in range(1, f + 1):
			dp[1][i] = 1
		for dice in range(1, d + 1):
			for values in range(1, target + 1):
				for i in range(1, f + 1):
					if values - i < 1:
						break
					dp[dice][values] += dp[dice - 1][values - i]
		return dp[d][target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		z = 10 ** 9 + 7

		def sol(n, m, t):
			dp = [[0 for i in range(t + 1)] for j in range(n + 1)]
			for i in range(1, min(t + 1, m + 1)):
				dp[1][i] = 1
			for i in range(1, n + 1):
				for j in range(1, t + 1):
					for k in range(1, min(j, m + 1)):
						dp[i][j] += dp[i - 1][j - k] % z
			return dp[n][t] % z
		return sol(d, f, target) % z


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for j in range(target + 1)] for i in range(d + 1)]
		dp[0][0] = 1
		for i in range(d):
			for ff in range(1, f + 1):
				for sm in range(target):
					if sm + ff <= target:
						dp[i + 1][sm + ff] += dp[i][sm]
		return dp[d][target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def dfs(d, target):
			if (d, target) in cache:
				return cache[d, target]
			if target < 0 or d < 0:
				return 0
			if target == 0 and d == 0:
				return 1
			ways = 0
			for i in range(1, f + 1):
				ways += dfs(d - 1, target - i)
			cache[d, target] = ways
			return ways
		cache = {}
		mod = 10 ** 9 + 7
		return dfs(d, target) % mod


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def dp(dice, target):
			if (dice, target) in memo:
				return memo[dice, target]
			if dice <= 0 or target <= 0:
				return 0
			if dice == 1:
				if target >= 1 and target <= f:
					return 1
				else:
					return 0
			rolls = 0
			for i in range(1, f + 1):
				rolls += dp(dice - 1, target - i) % 1000000007
			memo[dice, target] = rolls % 1000000007
			return memo[dice, target] % 1000000007
		return dp(d, target) % 1000000007


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d == 1:
			return int(f >= target)
		dp = [[0] * target for _ in range(d)]
		f = min(f, target)
		for i in range(f):
			dp[0][i] = 1
		for i in range(1, d):
			for j in range(i, target):
				for face in range(1, f + 1):
					if face > j:
						break
					dp[i][j] = (dp[i - 1][j - face] + dp[i][j]) % (1000000000.0 + 7)
		return int(dp[-1][-1])


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for j in range(target + 1)] for i in range(d)]
		for i in range(f):
			if i + 1 <= target:
				dp[0][i + 1] = 1
		for i in range(1, d):
			for j in range(1, target + 1):
				k = 1
				while j - k > 0 and k <= f:
					dp[i][j] += dp[i - 1][j - k]
					k += 1
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		self.sols = {}
		self.sols[d, f, target] = self.iter(d, f, target)
		return self.sols[d, f, target] % (10 ** 9 + 7)

	def iter(self, d, f, target):
		if d == 0:
			return 1 if target == 0 else 0
		if (d, f, target) in self.sols:
			return self.sols[d, f, target]
		self.sols[d, f, target] = sum([self.iter(d - 1, f, target - i) for i in range(1, f + 1)])
		return self.sols[d, f, target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		MOD = 10 ** 9 + 7
		mem = []
		for di in range(d + 1):
			cr = [0 for i in range(target + 1)]
			mem.append(cr)
		mem[0][0] = 1
		print(mem)
		for ti in range(1, target + 1):
			for di in range(1, d + 1):
				for fi in range(1, f + 1):
					if ti - fi >= 0:
						mem[di][ti] += mem[di - 1][ti - fi]
		return mem[d][target] % MOD


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		M = 10 ** 9 + 7
		dp = [[0 for j in range(max(target, f) + 1)] for i in range(d + 1)]
		for j in range(1, f + 1):
			dp[1][j] = 1
		for i in range(2, d + 1):
			for j in range(i, max(target, f) + 1):
				for k in range(1, f + 1):
					if j >= k:
						dp[i][j] += dp[i - 1][j - k]
		return dp[-1][target] % M


class Solution:

	def __init__(self):
		self.cache = dict()

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def helper(d, r):
			if d < 0 or r < 0:
				return 0
			if d == 0 and r == 0:
				return 1
			elif d != 0 and r != 0:
				if (d, r) not in self.cache:
					self.cache[d, r] = 0
					for i in range(1, f + 1):
						self.cache[d, r] += helper(d - 1, r - i)
				return self.cache[d, r]
			else:
				return 0
		return helper(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, dice: int, faces: int, target: int) -> int:
		table = [[0 for _ in range(target + 1)] for _ in range(dice + 1)]
		table[0][0] = 1
		mod = 10 ** 9 + 7
		for d in range(1, dice + 1):
			for i in range(1, target + 1):
				for f in range(1, min(i + 1, faces + 1)):
					table[d][i] = (table[d][i] + table[d - 1][i - f]) % mod
		return table[-1][-1]


class Solution:

	def numRollsToTarget(self, N: int, faces: int, total: int) -> int:
		DP = {}
		DP[0] = [0] * (total + 1)
		DP[1] = [0] + [1] * faces + [0] * (total - faces)
		for die in range(2, N + 1):
			DP[die] = [0] * (total + 1)
			for i in range(1, total + 1):
				count = 0
				for j in range(1, faces + 1):
					if i - j >= 1 and DP[die - 1][i - j] > 0:
						if die == 2:
							print((i, j))
						count += DP[die - 1][i - j]
				DP[die][i] = count
				print(count)
		ans = DP[N][total]
		return ans % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(d)] for _ in range(target + 1)]
		for i in range(1, target + 1):
			dp[i][0] = 1 if i <= f else 0
		for di in range(1, d):
			for t in range(1, target + 1):
				sub_targets = [t - face if t >= face else 0 for face in range(1, f + 1)]
				dp[t][di] = sum([dp[sub][di - 1] for sub in sub_targets])
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d, f, target):
		dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
		dp[0][0] = 1
		mod = 10 ** 9 + 7
		for i in range(d + 1):
			for t in range(1, target + 1):
				for val in range(1, min(f, t) + 1):
					dp[i][t] = (dp[i][t] + dp[i - 1][t - val]) % mod
		return dp[d][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def num_rolls_recur(d, target):
			key = (d, target)
			if key in memo:
				return memo[key]
			if target < 0:
				return 0
			if d == 0:
				if target == 0:
					return 1
				return 0
			num_ways = 0
			for i in range(1, f + 1):
				num_ways = (num_ways + num_rolls_recur(d - 1, target - i)) % (pow(10, 9) + 7)
			memo[key] = num_ways
			return num_ways
		return num_rolls_recur(d, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
		for i in range(1, min(f + 1, target + 1)):
			dp[1][i] = 1
		for i in range(1, d + 1):
			for j in range(2, target + 1):
				for k in range(1, f + 1):
					if j - k >= 0:
						dp[i][j] += dp[i - 1][j - k]
		return dp[-1][-1] % 1000000007


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target == d or target == d * f:
			return 1
		T = [0 for i in range(target + 1)]
		m = 10 ** 9 + 7
		T[0] = 1
		for i in range(0, d):
			for j in range(target, -1, -1):
				T[j] = 0
				for k in range(1, f + 1):
					if j >= k:
						T[j] += T[j - k] % m
						T[j] %= m
		return T[target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mod = 10 ** 9 + 7
		dp = [[0] * d for i in range(target + 1)]
		for i in range(1, target + 1):
			dp[i][0] = int(i <= f)
		for dd in range(1, d):
			for ff in range(1, f + 1):
				for i in range(target + 1):
					if i + ff <= target:
						dp[i + ff][dd] = (dp[i + ff][dd] + dp[i][dd - 1]) % mod
		return dp[-1][-1]


MOD = 1000000007

class Solution:
	dyn = {}

	def _get_res(self, d, f, target):
		if d == 1:
			return 1 if 0 < target and target <= f else 0
		if (d, f, target) in self.dyn:
			return self.dyn[d, f, target]
		res = 0
		for i in range(1, f + 1):
			res += self._get_res(d - 1, f, target - i)
		self.dyn[d, f, target] = res
		return res

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		return self._get_res(d, f, target) % MOD


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		maxAmount = 10 ** 9 + 7
		if target < 1 or d * f < target:
			return 0
		dpPrev = [(i, 1) for i in range(1, f + 1)]
		for roundNo in range(2, d + 1):
			numWays = defaultdict(int)
			for (i, v) in dpPrev:
				for num in range(1, f + 1):
					numWays[i + num] += v
			dpPrev = []
			for k in numWays:
				dpPrev.append((k, numWays[k]))
		for pair in dpPrev:
			if pair[0] == target:
				return pair[1] % maxAmount
		return 0


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		MOD = 10 ** 9 + 7
		f = min(target, f)
		dp = [[0 for val in range(target + 1)] for die in range(d)]
		for i in range(1, f + 1):
			dp[0][i] = 1
		for i in range(1, d):
			for val in range(target + 1):
				for face in range(1, f + 1):
					if val - face >= 0:
						dp[i][val] = (dp[i - 1][val - face] + dp[i][val]) % MOD
		return dp[-1][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mod = 10 ** 9 + 7
		dp = [[0 for i in range(target + 1)] for j in range(d + 1)]
		dp[1] = [0] + [1 for i in range(f)] + [0 for i in range(target - f)]
		for i in range(1, d + 1):
			if i == 1 or i == 0:
				continue
			for j in range(1, target + 1):
				for k in range(1, f + 1):
					if j - k > 0:
						dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod
		return dp[-1][-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
		for dCand in range(1, d + 1):
			for targetCand in range(1, target + 1):
				if dCand == 1:
					dp[dCand][targetCand] = 1 if targetCand <= f else 0
					continue
				allCombos = 0
				for option in range(1, f + 1):
					allCombos += dp[dCand - 1][max(0, targetCand - option)]
				dp[dCand][targetCand] = allCombos % (10 ** 9 + 7)
		return dp[d][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def auxNumRolls(d, f, target, memoization):
			if target < d or target > d * f:
				return 0
			if d == 1:
				return 1
			ans = 0
			for i in range(1, f + 1):
				if (d - 1, target - i) not in memoization:
					memoization[d - 1, target - i] = auxNumRolls(d - 1, f, target - i, memoization)
				ans += memoization[d - 1, target - i]
			return ans
		return auxNumRolls(d, f, target, {}) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mod = 10 ** 9 + 7
		state = [1] + [0] * target
		for i in range(d):
			for j in range(target, -1, -1):
				state[j] = 0
				for k in range(1, min(f, j) + 1):
					state[j] += state[j - k]
					state[j] %= mod
		return state[-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = [[0] * (target + 1) for _ in range(d + 1)]
		for i in range(1, d + 1):
			for j in range(1, target + 1):
				if i == 1:
					if 1 <= j <= f:
						memo[i][j] = 1
					continue
				for t in range(1, f + 1):
					if j >= t:
						memo[i][j] += memo[i - 1][j - t]
		return memo[d][target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = []
		mod = math.pow(10, 9) + 7
		for _ in range(d + 1):
			dp.append((target + 1) * [0])
		for i in range(target + 1):
			dp[0][i] = 0
		for i in range(d + 1):
			dp[i][0] = 0
		for i in range(min(f, target)):
			dp[1][i + 1] = 1
		for i in range(2, d + 1):
			for j in range(1, target + 1):
				for roll in range(1, f + 1):
					if j - roll >= 0:
						dp[i][j] = (dp[i][j] % mod + dp[i - 1][j - roll] % mod) % mod
		return int(dp[d][target])


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mod = int(1000000000.0) + 7
		dp = [[0 for _ in range(d + 1)] for _ in range(target + 1)]
		for i in range(1, min(target + 1, f + 1)):
			dp[i][1] = 1
		for i in range(2, target + 1):
			for j in range(2, d + 1):
				for k in range(1, min(f + 1, i + 1)):
					dp[i][j] += dp[i - k][j - 1]
		return dp[target][d] % mod


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d * f < target or d > target:
			return 0
		prev = {0: 1}
		for x in range(d):
			curr = {}
			for y in range(1, f + 1):
				for (prev_sum, count) in list(prev.items()):
					curr_sum = prev_sum + y
					if curr_sum <= target:
						curr[curr_sum] = curr.get(curr_sum, 0) + count
			prev = curr
		return prev[target] % (10 ** 9 + 7) if target in prev else 0


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		DP = [[0] * (target + 1) for _ in range(d + 1)]
		for i in range(f + 1):
			if i <= target:
				DP[1][i] = 1
		if d == 1:
			return DP[d][target]
		for j in range(2, d + 1):
			for i in range(1, target + 1):
				for val in range(1, f + 1):
					if 0 < i - val < len(DP[j]):
						DP[j][i] += DP[j - 1][i - val]
		return DP[d][target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, n: int) -> int:
		mod = 10 ** 9 + 7
		dp = [0 for i in range(n + 1)]
		dp[0] = 1
		temp = [0 for i in range(n + 1)]
		lol = [0 for i in range(n + 1)]
		for i in range(1, d + 1):
			for j in range(i, n + 1):
				for k in range(1, min(f + 1, j + 1)):
					temp[j] += dp[j - k]
					temp[j] = temp[j] % mod
			dp = temp.copy()
			temp = lol.copy()
		return dp[-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mod = 1000000000 + 7
		dp = [[0 for i in range(target + 1)] for j in range(d)]
		for i in range(d):
			for j in range(target + 1):
				if i == 0:
					dp[i][j] = 1 if j >= 1 and j <= f else 0
				else:
					for l in range(1, f + 1):
						if j - l > 0:
							dp[i][j] += dp[i - 1][j - l]
							dp[i][j] %= mod
		return dp[d - 1][target] % mod


class Solution:

	def numRollsToTarget(self, d, f, target):
		mod_v = 10 ** 9 + 7
		dp = [[0] * (target + 1) for _ in range(d + 1)]
		for i in range(1, f + 1):
			if i > target:
				break
			dp[1][i] = 1
		for i in range(2, d + 1):
			for j in range(i, target + 1):
				for k in range(1, f + 1):
					if j - k >= 0:
						dp[i][j] += dp[i - 1][j - k]
						dp[i][j] %= mod_v
					else:
						break
		return dp[d][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		opt = [[0 for i in range(target + 1)] for x in range(d)]
		for i in range(1, target + 1):
			if i <= f:
				opt[0][i] = 1
		for i in range(1, d):
			for j in range(1, target + 1):
				for h in range(1, f + 1):
					if j - h > -1:
						opt[i][j] += opt[i - 1][j - h]
		return opt[d - 1][target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d * f < target or d > target:
			return 0
		if d == 1:
			if target <= f:
				return 1
			else:
				return 0
		M = 10 ** 9 + 7
		dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
		dp[0][0] = 1
		for i in range(1, d + 1):
			for j in range(1, target + 1):
				if j == 1:
					dp[i][j] = dp[i - 1][0]
				elif j <= f:
					dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]
				else:
					dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] - dp[i - 1][j - f - 1]
		return dp[d][target] % M


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp: List[List[int]] = [[0] * (d + 1) for _ in range(target + 1)]
		for i in range(1, f + 1):
			if i <= target:
				dp[i][1] = 1
			else:
				break
		for j in range(2, d + 1):
			for i in range(j, target + 1):
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] - dp[i - min(i - 1, f) - 1][j - 1]
		return dp[target][d] % (10 ** 9 + 7)


class Solution(object):

	def numRollsToTarget(self, d, f, t):
		mod = 1000000000 + 7
		dp = [[0 for i in range(t + 1)] for j in range(d)]
		for i in range(d):
			for j in range(t + 1):
				if i == 0:
					dp[i][j] = 1 if j >= 1 and j <= f else 0
				else:
					for l in range(1, f + 1):
						if j - l > 0:
							dp[i][j] += dp[i - 1][j - l]
							dp[i][j] %= mod
		return dp[d - 1][t] % mod
ob = Solution()
print(ob.numRollsToTarget(2, 6, 7))


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		MOD = 1000000007
		dp = [[0] * 1001 for _ in range(31)]
		mint = min(f, target)
		targetMax = d * f
		for i in range(1, mint + 1):
			dp[1][i] = 1
		for i in range(2, d + 1):
			for j in range(i, targetMax + 1):
				for k in range(1, min(j, f) + 1):
					dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD
		return dp[d][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, s: int) -> int:
		mem = [[0 for _ in range(s + 1)] for _ in range(d + 1)]
		mem[0][0] = 1
		for i in range(1, d + 1):
			for j in range(1, s + 1):
				mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1]
				if j - f - 1 >= 0:
					mem[i][j] -= mem[i - 1][j - f - 1]
		return mem[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
		dp[0][0] = 1
		mod = 10 ** 9 + 7
		for i in range(1, d + 1):
			for j in range(1, target + 1):
				ff = 1
				highest_die = min(j, f)
				while ff <= highest_die:
					dp[i][j] += dp[i - 1][j - ff]
					dp[i][j] %= mod
					ff += 1
		return dp[d][target] % mod


class Solution:

	@lru_cache(maxsize=None)
	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0] + [0] * target for _ in range(d)]
		for i in range(d):
			for j in range(1, target + 1):
				for k in range(1, f + 1):
					if k > j:
						break
					if i == 0:
						dp[i][j] = int(j == k)
					else:
						dp[i][j] += dp[i - 1][j - k]
					if dp[i][j] > 10 ** 9:
						dp[i][j] = dp[i][j] % 10 ** 9 - 7 * (dp[i][j] // 10 ** 9)
		return dp[-1][-1]


from functools import lru_cache

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d * f < target:
			return 0

		@lru_cache(maxsize=None)
		def dfs(index, target):
			if index == d:
				if target == 0:
					return 1
				return 0
			if target <= 0:
				return 0
			ret = [0] * (f + 1)
			for num in range(1, f + 1):
				ret[num] = dfs(index + 1, target - num)
			return sum(ret) % (10 ** 9 + 7)
		return dfs(0, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		m = collections.defaultdict(int)
		m[0, 0] = 0
		for t in range(1, 1 + f):
			m[1, t] = 1
		for i in range(1, 1 + d):
			for j in range(1, 1 + target):
				for k in range(1, min(1 + f, j)):
					m[i, j] += m[i - 1, j - k]
		return m[d, target] % (10 ** 9 + 7)


class Solution:

	def helper(self, d, f, target, num_ways):
		if d == 0:
			if target == 0:
				return 1
			else:
				return 0
		if (d, target) in num_ways:
			return num_ways[d, target]
		for face in range(1, f + 1):
			num_ways[d, target] += self.helper(d - 1, f, target - face, num_ways)
		return num_ways[d, target]

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		num_ways = collections.defaultdict(int)
		self.helper(d, f, target, num_ways)
		return num_ways[d, target] % (1000000000 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		f = min(target, f)
		MOD = 10 ** 9 + 7
		dp = [[None for _ in range(target + 1)] for _ in range(d + 1)]
		for i in range(1, f + 1):
			dp[1][i] = 1
		for i in range(2, d + 1):
			for j in range(1, target + 1):
				dp[i][j] = 0
				for k in range(1, f + 1):
					if j - k >= 1 and dp[i - 1][j - k] is not None:
						dp[i][j] += dp[i - 1][j - k]
				dp[i][j] %= MOD
		return dp[d][target] if dp[d][target] is not None else 0


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mod = 1000000007
		dp = [[0] * (d + 1) for i in range(target + 1)]
		for tar in range(1, target + 1):
			if f >= tar:
				dp[tar][1] = 1
		for dice in range(2, d + 1):
			for tar in range(1, target + 1):
				for possVal in range(1, f + 1):
					if tar - possVal >= 1:
						dp[tar][dice] = (dp[tar][dice] + dp[tar - possVal][dice - 1]) % mod
		print(dp)
		return dp[-1][-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if not d or not f or (not target):
			return 0
		dp = [[0] * (target + 1) for _ in range(d + 1)]
		dp[0][0] = 1
		for i in range(1, len(dp)):
			for j in range(1, len(dp[0])):
				k = 1
				while k <= min(j, f):
					dp[i][j] += dp[i - 1][j - k]
					k += 1
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		table = [[0] * (target + 1) for i in range(d + 1)]
		for j in range(1, min(f + 1, target + 1)):
			table[1][j] = 1
		for i in range(2, d + 1):
			for j in range(1, target + 1):
				for k in range(1, min(f + 1, j)):
					table[i][j] += table[i - 1][j - k]
		return table[-1][-1] % 1000000007


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0] * (target + 1) for _ in range(d + 1)]
		md = pow(10, 9) + 7
		dp[0][0] = 1
		for trial in range(1, d + 1):
			for i in range(target):
				for face in range(1, f + 1):
					if i + face <= target:
						dp[trial][i + face] += dp[trial - 1][i]
						dp[trial][i + face] %= md
		return dp[-1][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(d + 1)] for _ in range(target + 1)]
		if target < d:
			return 0
		for i in range(2, d + 1):
			dp[1][i] = 0
		for i in range(1, min(f + 1, target + 1)):
			dp[i][1] = 1
		for D in range(2, d + 1):
			for s in range(1, target + 1):
				for k in range(1, f + 1):
					dp[s][D] += dp[s - k][D - 1] if s - k >= 1 and D > 1 else 0
					dp[s][D] = dp[s][D] % 1000000007
		return dp[target][d]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dice = [k for k in range(1, f + 1)]
		dp = [[0 for _ in range(d + 1)] for _ in range(target + 1)]

		def numRolls(d, f, target):
			for j in range(1, min(f + 1, target + 1)):
				dp[j][1] = 1
			for i in range(2, d + 1):
				for j in range(1, target + 1):
					for new_t in list(map(lambda k: j - k, dice)):
						if new_t >= 0:
							dp[j][i] += dp[new_t][i - 1]
						dp[j][i]
			return dp[target][d] % (10 ** 9 + 7)
		return numRolls(d, f, target)


MODULE = 10 ** 9 + 7

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target < d:
			return 0
		dp = [[0] * (target + 1) for _ in range(d + 1)]
		for i in range(1, f + 1):
			if i > target:
				break
			dp[1][i] = 1
		for i in range(1, d + 1):
			for j in range(1, target + 1):
				for face in range(1, f + 1):
					if j >= face:
						dp[i][j] = (dp[i][j] + dp[i - 1][j - face]) % MODULE
		return dp[d][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(max(target + 1, f + 1))] for _ in range(d + 1)]
		for i in range(1, f + 1):
			dp[1][i] = 1
		break_flag = False
		for i in range(1, d):
			break_flag = False
			for j in range(1, max(target + 1, f + 1)):
				for n in range(1, f + 1):
					if j + n <= max(target, f):
						dp[i + 1][j + n] += dp[i][j]
					else:
						break
						break_flag = True
				if break_flag:
					break
		return dp[d][target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d == 0:
			return 0
		q = collections.deque([(i + 1, 1) for i in range(f)])
		visited = {(0, 0): 1}
		while q:
			(s, di) = q.popleft()
			if (s, di) in visited:
				continue
			npath = sum((visited.get((s - i - 1, di - 1), 0) for i in range(f)))
			if di == d:
				if s == target:
					return npath % 1000000007
				else:
					continue
			visited[s, di] = npath
			q += [(s + i + 1, di + 1) for i in range(f)]
		return 0


from itertools import product

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for i in range(target + 1)] for j in range(d + 1)]
		dp[0][0] = 1
		mod = 10 ** 9 + 7
		for i in range(1, d + 1):
			for j in range(1, target + 1):
				k = 1
				while k <= min(j, f):
					dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod
					k += 1
		return dp[d][target] % mod


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		rolls = []
		for i in range(d + 1):
			rolls.append([0] * (target + 1))
		for i in range(target + 1):
			rolls[0][i] = 0
		for i in range(d + 1):
			rolls[i][0] = 0
		for i in range(1, target + 1):
			if i <= f:
				rolls[1][i] = 1
		for i in range(2, d + 1):
			for j in range(1, target + 1):
				k = 1
				while k <= f:
					if j - k < 0:
						break
					rolls[i][j] += rolls[i - 1][j - k]
					k += 1
		return rolls[d][target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def rec_find_target_sum(d, f, target):
			if (d, f, target) in memo:
				return memo[d, f, target]
			if d == 0 or d * f < target or target <= 0:
				return 0
			if d == 1:
				return 1
			possibs = 0
			for face in range(f):
				possibs += rec_find_target_sum(d - 1, f, target - face - 1)
			memo[d, f, target] = possibs
			return possibs
		memo = {}
		return rec_find_target_sum(d, f, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def rollDice(d, target):
			if target < 0 or target > f * d:
				memo[d, target] = 0
				return 0
			if d == 0:
				return 0 if target > 0 else 1
			if (d, target) in memo:
				return memo[d, target]
			total = 0
			for num in range(1, f + 1):
				total += rollDice(d - 1, target - num)
			memo[d, target] = total
			return total
		return rollDice(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def helper(h, d, target):
			if target <= 0 or target > d * f:
				return 0
			if d == 1:
				return 1
			if (d, target) in h:
				return h[d, target]
			res = 0
			for i in range(1, f + 1):
				res += helper(h, d - 1, target - i)
			h[d, target] = res
			return h[d, target]
		h = {}
		return helper(h, d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [1] + [0] * target
		for i in range(d):
			for j in range(target, -1, -1):
				dp[j] = sum(dp[max(0, j - f):j])
		return dp[target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d * f < target:
			return 0
		elif d * f == target:
			return 1
		mod = int(10 ** 9 + 7)
		dp = [[0] * (target + 1) for _ in range(d + 1)]
		for j in range(1, min(f + 1, target + 1)):
			dp[1][j] = 1
		for i in range(2, d + 1):
			for j in range(1, target + 1):
				for k in range(1, f + 1):
					if j - k >= 0:
						dp[i][j] += dp[i - 1][j - k]
				dp[i][j] %= mod
		return dp[-1][-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		faces = [i for i in range(1, f + 1)]
		cache = {}

		def dfs(left, numDice):
			re = 0
			if (left, numDice) in cache:
				return cache[left, numDice]
			if left > f * (d - numDice):
				cache[left, numDice] = 0
				return 0
			if numDice == d:
				return 1 if left == 0 else 0
			else:
				for face in faces:
					numDice += 1
					if left - face >= 0:
						re += dfs(left - face, numDice)
					numDice -= 1
				cache[left, numDice] = re
				return re
		return dfs(target, 0) % (10 ** 9 + 7)


from functools import lru_cache
MOD = 10 ** 9 + 7

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		sol = [0] * (target + 1)
		sol[0] = 1
		for _ in range(1, d + 1):
			nxt = [0] * (target + 1)
			for i in range(target + 1):
				(start, end) = (max(i - f, 0), i - 1)
				nxt[i] = sum(sol[start:end + 1]) % MOD
			sol = nxt
		return sol[target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		res = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
		modula = 10 ** 9 + 7
		res[0][0] = 1
		for dice in range(1, d + 1):
			for i in range(dice, target + 1):
				interestMinRange = max(0, i - f)
				res[dice][i] = sum(res[dice - 1][interestMinRange:i]) % modula
		return res[-1][-1]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def helper(dices, total):
			if total < 0:
				return 0
			if dices == 0 and total == 0:
				return 1
			if dices > 0 and total == 0:
				return 0
			if dices * f < total:
				memo[dices, total] = 0
				return 0
			if (dices, total) in memo:
				return memo[dices, total]
			ways = 0
			for num in range(1, f + 1):
				ways += helper(dices - 1, total - num)
			memo[dices, total] = ways
			return ways
		return helper(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d, f, target):
		if target < d or target > d * f:
			return 0
		dp = [[0 for _ in range(d * f + 1)] for _ in range(d + 1)]
		for v in range(1, f + 1):
			dp[1][v] = 1
		for dcnt in range(2, d + 1):
			for total in range(dcnt, target + 1):
				for v in range(1, f + 1):
					dp[dcnt][total] += dp[dcnt - 1][total - v]
		return dp[d][target] % (10 ** 9 + 7)

class Solution:

	def numRollsToTarget(self, d, f, target):
		if target < d or target > d * f:
			return 0
		dp = [[0 for _ in range(d * f + 1)] for _ in range(d + 1)]
		for v in range(1, f + 1):
			dp[1][v] = 1
		for dcnt in range(2, d + 1):
			for total in range(dcnt, target + 1):
				for v in range(1, f + 1):
					dp[dcnt][total] += dp[dcnt - 1][total - v]
		return dp[d][target] % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target < d or target > d * f:
			return 0
		mod_val = 10 ** 9 + 7
		dp = [0] * (target + 1)
		dp[0] = 1
		for r in range(1, d + 1):
			if r > 1:
				dp[r - 2] = 0
			for i in range(target, r - 1, -1):
				dp[i] = sum(dp[max(0, i - f):i]) % mod_val
		return dp[target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target < d or target > d * f:
			return 0
		if target == d * f:
			return 1
		mem = {}
		mod = int(1000000000.0 + 7)

		def dice(k, target):
			if target == 0:
				return 0
			if k == 1:
				if target <= f:
					return 1
				else:
					return 0
			if (k, target) in mem:
				return mem[k, target]
			ans = 0
			for i in range(1, f + 1):
				if target >= i and target <= f * k:
					ans += dice(k - 1, target - i) % mod
			ans %= mod
			mem[k, target] = ans
			return ans
		return dice(d, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		module = 10 ** 9 + 7
		self.m = {}

		def dfs(d, f, target):
			if d == 0 and target == 0:
				return 1
			if d == 0 and target != 0:
				return 0
			if d * f < target or d > target:
				return 0
			if (d, target) in self.m:
				return self.m[d, target]
			res = 0
			for i in range(1, f + 1):
				res = (res + dfs(d - 1, f, target - i)) % module
			self.m[d, target] = res
			return res
		return dfs(d, f, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target > d * f or target < d:
			return 0
		targets = {}
		faces = [i for i in range(1, f + 1)]

		def solve(target, numDice):
			ways = 0
			if (target, numDice) in targets:
				return targets[target, numDice]
			if target > f * (d - numDice):
				targets[target, numDice] = 0
				return 0
			if numDice == d:
				return 1 if target == 0 else 0
			else:
				for face in faces:
					if target - face >= 0:
						ways += solve(target - face, numDice + 1)
				targets[target, numDice] = ways
				return ways
		return solve(target, 0) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		def foo(dices, need):
			if dices == 0:
				return int(need == 0)
			elif (dices, need) in m:
				return m[dices, need]
			elif need > f * dices:
				m[dices, need] = 0
				return 0
			ret = 0
			for i in range(1, f + 1):
				ret += foo(dices - 1, need - i)
			m[dices, need] = ret
			return ret
		m = {}
		return foo(d, target) % (10 ** 9 + 7)


MOD = 10 ** 9 + 7
from collections import defaultdict

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}
		if target > f * d:
			return 0
		if target == f * d:
			return 1

		def F(j, memo, left):
			if (j, left) in memo.keys():
				return memo[j, left]
			if left < 0:
				return 0
			if j == d - 1:
				memo[j, left] = int(left <= f and left >= 1)
				return memo[j, left]
			ans = 0
			for i in range(1, f + 1):
				ans += F(j + 1, memo, left - i)
			memo[j, left] = ans
			return memo[j, left]
		F(0, memo, target)
		return memo[0, target] % MOD


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d * f < target:
			return 0
		if d * f == target:
			return 1

		def dfs(j, left, memo):
			if (j, left) in memo.keys():
				return memo[j, left]
			if left < 0:
				return 0
			if j == d - 1:
				return int(left > 0 and left <= f)
			ans = 0
			for i in range(1, f + 1):
				ans += dfs(j + 1, left - i, memo)
			memo[j, left] = ans
			return memo[j, left]
		return dfs(0, target, {}) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		matrix = [[1 if 1 <= x <= f and y == 0 else 0 for x in range(target + 1)] for y in range(0, d)]
		for row in range(1, d):
			for (col, val) in enumerate(matrix[row]):
				matrix[row][col] = sum(matrix[row - 1][max(0, col - f):max(0, col)])
		return matrix[d - 1][target] % (10 ** 9 + 7)


class Solution:

	def __init__(self):
		self.memo = {}

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d * f < target:
			return 0
		if d == 1:
			return 1
		if (d, target) in self.memo:
			return self.memo[d, target]
		numWays = 0
		for i in range(1, f + 1):
			if target - i > 0:
				ways = self.memo.get((d - 1, target - i), self.numRollsToTarget(d - 1, f, target - i))
				numWays += ways
		self.memo[d, target] = numWays
		return numWays % (10 ** 9 + 7)


class Solution:
	MODULO = 10 ** 9 + 7
	table = {}

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		return self.recursive(d, f, target) % self.MODULO

	def recursive(self, d: int, f: int, target: int):
		if target < d or target > d * f:
			return 0
		if d == 1 and target <= f:
			return 1
		sum_ = 0
		for i in range(1, f + 1):
			idx = (d - 1, f, target - i)
			if idx not in self.table:
				self.table[idx] = self.recursive(*idx)
			sum_ += self.table[idx] % self.MODULO
		return sum_


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def solve(dice, target):
			if target > dice * f:
				memo[dice, target] = 0
				return 0
			if dice == 0:
				return target == 0
			if target == 0:
				return 0
			if (dice, target) in memo:
				return memo[dice, target]
			ways = 0
			for num in range(1, f + 1):
				ways += solve(dice - 1, target - num)
			memo[dice, target] = ways
			return ways
		return solve(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		memo = {}

		def rolls(dice, t):
			if t > f * dice:
				memo[dice, t] = 0
				return 0
			if dice == 0:
				return t == 0
			if target < 0:
				return 0
			if (dice, t) in memo:
				return memo[dice, t]
			solu = 0
			for num in range(1, f + 1):
				solu += rolls(dice - 1, t - num)
			memo[dice, t] = solu
			return solu
		return rolls(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		@lru_cache(None)
		def dfs(dice_left, curr_sum):
			if curr_sum > target:
				return 0
			if dice_left == 0:
				return 1 if curr_sum == target else 0
			count = 0
			for i in range(1, f + 1):
				count += dfs(dice_left - 1, curr_sum + i)
			return count % 1000000007
		return dfs(d, 0)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(dice, target):
			if target == 0:
				return int(dice == 0)
			elif target < 0 or dice <= 0:
				return 0
			else:
				res = 0
				for x in range(1, f + 1):
					res += dp(dice - 1, target - x)
				return res % MOD
		return dp(d, target)


import functools

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		@functools.lru_cache(None)
		def helper(idx, curr):
			if curr > target:
				return 0
			if idx == d:
				return int(curr == target)
			res = 0
			for num in range(1, f + 1):
				res += helper(idx + 1, curr + num)
			return res % (10 ** 9 + 7)
		return helper(0, 0)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		@lru_cache(maxsize=None)
		def nrolls(d, t):
			if d == 0:
				if t == 0:
					return 1
				else:
					return 0
			if d > t or t < 0:
				return 0
			res = 0
			for i in range(1, f + 1):
				res += nrolls(d - 1, t - i)
			return res % (10 ** 9 + 7)
		return nrolls(d, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target > d * f:
			return 0
		dicti = collections.defaultdict(int)

		def dice_target(rem_dice, summ):
			if rem_dice == 0:
				return 1 if summ == target else 0
			if summ > target:
				return 0
			if (rem_dice, summ) in dicti:
				return dicti[rem_dice, summ]
			for i in range(1, f + 1):
				dicti[rem_dice, summ] += dice_target(rem_dice - 1, summ + i)
			return dicti[rem_dice, summ]
		return dice_target(d, 0) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d * f < target or d > target:
			return 0
		if d == 1 and f >= target:
			return 1
		rows = d + 1
		cols = target + 1
		dp = [[0 for _ in range(cols)] for _ in range(rows)]
		for i in range(1, min(f + 1, cols)):
			dp[1][i] = 1
		for i in range(2, rows):
			for j in range(i, cols):
				start = max(1, j - f)
				dp[i][j] = sum(dp[i - 1][start:j]) % 1000000007
		return dp[d][target]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
		dp[0][0] = 1
		for i in range(1, d + 1):
			for j in range(i * 1, min(target + 1, i * f + 1)):
				for r in range(1, f + 1):
					if j - r >= 0:
						dp[i][j] += dp[i - 1][j - r]
		return dp[-1][-1] % (10 ** 9 + 7)
		self.res = 0

		def dfs(dice, sum):
			for i in range(1, f + 1):
				if dice == d:
					if sum + i == target:
						self.res += 1
				elif sum + i < target:
					dfs(dice + 1, sum + i)
		dfs(1, 0)
		return self.res


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if not d or not f or target == 0:
			return 0

		def dfs(d, f, hash_map, target):
			if target == 0 and d == 0:
				return 1
			if target <= 0 or target > d * f or target < d:
				return 0
			if (d, target) in hash_map:
				return hash_map[d, target]
			cnt = 0
			for i in range(1, f + 1):
				if target - i < 0:
					break
				cnt += dfs(d - 1, f, hash_map, target - i)
				cnt %= 1000000007
			hash_map[d, target] = cnt
			return hash_map[d, target]
		return dfs(d, f, {}, target)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d <= target <= d * f:
			mod = 10 ** 9 + 7

			def rec(d, f, t):
				if d == 1:
					return 1 if 0 < t <= f else 0
				elif (d, t) in memo:
					return memo[d, t]
				else:
					temp = sum([rec(d - 1, f, t - x) for x in range(1, f + 1)])
					memo[d, t] = temp
					return temp
			memo = {}
			return rec(d, f, target) % mod
		return 0


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		dp = {}
		for i in range(1, f + 1):
			dp[i] = 1
		for i in range(d - 1):
			temp = {}
			for val in dp:
				for dice in range(1, f + 1):
					if val + dice <= target:
						temp[val + dice] = temp.get(val + dice, 0) + dp[val]
			dp = temp
		if not target in dp:
			return 0
		return dp[target] % (10 ** 9 + 7)


class Solution:

	def __init__(self):
		self.mem = {}

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if target < d or target > d * f:
			return 0
		if d == 0 or target == 0:
			return 0
		if d == 1 and target <= f:
			return 1
		key = (d, f, target)
		if key in self.mem:
			return self.mem[key]
		Sum = 0
		for i in range(1, f + 1):
			Sum += self.numRollsToTarget(d - 1, f, target - i)
			Sum %= 10 ** 9 + 7
		self.mem[key] = Sum
		return self.mem[key]


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		@lru_cache(None)
		def dfs(left, k):
			if left == k:
				return 1
			if left > k:
				return 0
			if k == 0:
				if left == 0:
					return 1
				else:
					return 0
			if left < 0:
				return 0
			s = 0
			for i in range(1, f + 1):
				if k - i < 0:
					break
				s += dfs(left - 1, k - i)
			return s % (10 ** 9 + 7)
		return dfs(d, target) % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		current_sums = {}
		current_sums[0] = 1
		new_sums = {}
		out = 0
		for die in range(1, d + 1):
			for face in range(1, f + 1):
				for summ in list(current_sums.keys()):
					curr = summ + face
					if curr == target and die == d:
						out += current_sums[summ]
					elif curr < target:
						if curr in list(new_sums.keys()):
							new_sums[curr] += current_sums[summ]
						else:
							new_sums[curr] = current_sums[summ]
			current_sums = new_sums
			new_sums = {}
		return out % (10 ** 9 + 7)


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		@lru_cache(maxsize=None)
		def func(d, target):
			if d == 0:
				return 1 if target == 0 else 0
			if d > target or target < 0:
				return 0
			return sum([func(d - 1, target - i) % (1000000000.0 + 7) for i in range(1, f + 1)]) % (1000000000.0 + 7)
		if d < 1 or f < 1 or target < 1:
			return 0
		return int(func(d, target))


from functools import lru_cache
MOD = 10 ** 9 + 7

class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:

		@lru_cache(None)
		def dp(i, k):
			if i == d:
				return k == 0
			return sum((dp(i + 1, k - face) for face in range(1, f + 1)))
		return dp(0, target) % MOD


class Solution:

	def numRollsToTarget(self, d: int, f: int, target: int) -> int:
		if d == 1:
			return 1 if f >= target else 0
		dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
		dp[0][0] = 1
		for i in range(1, d + 1):
			for j in range(i, min(i * f, target) + 1):
				for k in range(1, min(j, f) + 1):
					dp[i][j] += dp[i - 1][j - k]
		return dp[d][target] % (pow(10, 9) + 7)

	def __numRollsToTarget(self, d: int, f: int, target: int) -> int:
		mem = {}
		return self.dp(d, f, target, mem) % (pow(10, 9) + 7)

	def dp(self, d, f, target, mem):
		if d == 0:
			return 1 if target == 0 else 0
		if d * f < target:
			return 0
		if (d, target) in mem:
			return mem[d, target]
		res = 0
		for i in range(1, f + 1):
			if target - i < 0:
				break
			res += self.dp(d - 1, f, target - i, mem)
		mem[d, target] = res
		return res