# your code goes here

mod = 1e9 + 7
    
# @lru_cache(maxsize=None)
def solve(n,k,target,dp):
    if n==0 and target==0:
        return 1
    if n<0 or target<0:
        return 0
    if dp[n][target]!=-1:
        return dp[n][target]
    
    ans = 0
    for i in range(1,k+1):
        ans = (ans%mod + solve(n-1,k,target-i,dp)%mod)%mod
    

    dp[n][target]=int(ans)
    return dp[n][target]


class Solution:  

    def method1(self, n: int, k: int, target: int) -> int:
        dp = [[-1]*(target+2)]*(n+1)
        # dp = [[-1] * (target+2) for _ in range(n+1)]
        return solve(n,k,target,dp)
        
    def method2(self, n: int, k: int, target: int) -> int:
        # dp = [[-1]*(target+2)]*(n+1)
        dp = [[-1] * (target+2) for _ in range(n+1)]
        return solve(n,k,target,dp)

obj = Solution()
print(obj.method1(2,6,7))
print(obj.method2(2,6,7))