이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 점화식을 구하기 위해 각 n과 k에 대한 결과들을 정리해보았다. 그 결과 다음과 같은 점화식이 도출되었다.

# n/k>=2 and i>=2 and j>=4
dp[1][num]=num
dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%1000000003

이 점화식을 통해 문제를 금방 해결할 수 있었다.

Code

n=int(input())
k=int(input())
if n/k<2:
    print(0)
    quit()
dp=[[0 for _ in range(n+1)] for _ in range(k+1)]
for i in range(1, n+1):
    dp[1][i]=i%1000000003
for i in range(2, k+1):
    for j in range(4, n+1):
        dp[i][j]=(dp[i-1][j-2]+dp[i][j-1])%1000000003
print(dp[k][n]%1000000003)