백준 - 10164 : 격자상의 경로 (S1)

 1N, M, K = map(int, input().split())
 2K -= 1
 3ox = K % M
 4oy = K // M
 5def solve(sx, sy, ex, ey):
 6    dp = [[0]*M for _ in range(N)]
 7    dp[sy][sx] = 1
 8    for i in range(sy, ey+1):
 9        for j in range(sx, ex+1):
10            if i-1 >= 0:
11                dp[i][j] += dp[i-1][j]
12            if j-1 >= 0:
13                dp[i][j] += dp[i][j-1]
14    return dp[ey][ex]
15
16if K != -1:
17    print (solve(0, 0, ox, oy) * solve(ox, oy, M-1, N-1))
18else:
19    print (solve(0, 0, M-1, N-1))