[Gold 5] 2225번 합분해

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int k = Integer.parseInt(arr[1]);
        int[][] dp = new int[n+1][k+1];
        
        for(int i=1; i<=n; i++) { dp[i][1] = 1; }  
        for(int i=1; i<=k; i++) { dp[0][i] = 1; dp[1][i] = i; }
        
        for(int i=2; i<=n; i++) {
            for(int j=2; j<=k; j++) {
                for(int t=0; t<=i; t++) {
                    dp[i][j] += dp[i-t][j-1];
                    dp[i][j] %= 1_000_000_000;
                }
            }
        }
        
        System.out.println(dp[n][k]);
    }
}