2225 합분해

#include <stdio.h>
 
long long dp[205][205] = { 0 };
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i <= n; i++) {
        dp[i][1] = 1;        
    }
    for (int i = 0; i <= m; i++) {
        dp[0][i] = 1;
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            long long sum = 0;
            for (int k = 0; k <= i; k++) {
                sum += dp[k][j - 1] % 1000000000;
            }
            dp[i][j] = sum % 1000000000;
        }
    }
    printf("%lld", dp[n][m]);
}