[백준] 2225번 : 합분해 with python3

n, k = map(int,input().split())

d = [[0]*(n+1) for j in range(k+1)]
# d[k][n] = 0부터 n까지의 정수 k개를 더해서 그 합이 n이 되는 경우의 수
d[0][0] = 1

for i in range(1,k+1):
    d[i][0] = 1
    for j in range(1,n+1):
        for p in range(0,j+1):
            d[i][j] += d[i-1][j-p]
            # i가 숫자의 개수이다.
            # i-1개의 것 중 p를 갖고 있는 수의 개수를 더하는 것이다.
            d[i][j] %= 1000000000

print(d[k][n])