1629F1 - Game on Sum (Easy Version) - CodeForces Solution

import sys
import math

R = lambda : sys.stdin.readline().rstrip()
MIS = lambda : map(int, R().split())
sys.setrecursionlimit(10**6)


mod = 1000000007

def f(a, b):
    if dp[a][b] != -1: return dp[a][b]
    if a == b:
        dp[a][b] = K*a%mod
        return dp[a][b]
    if b == 0:
        dp[a][b] = 0
        return dp[a][b]

    dp[a][b] = (f(a-1, b)+f(a-1, b-1))%mod
    if dp[a][b]&1:
        dp[a][b] *= mod//2+1
    else:
        dp[a][b] //= 2
    return dp[a][b]

for _ in range(int(R())):
    N, M, K = MIS()
    dp = [[-1] * (M+1) for _ in range((N+1))]
    print(f(N, M)%mod)