Robocontest.uz | Editorial 📕

#include <stdio.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int mod = 1000000007;

    long int dp[n+1][k+1];

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = 0;
        }
    }

    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod;
            if (j >= i) {
                dp[i][j] = (dp[i][j] - dp[i-1][j-i]+mod) % mod;
            }
        }
    }

    printf("%d\n", dp[n][k]);

    return 0;
}

#include <stdio.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int mod = 1000000007;

    long int dp[n+1][k+1];

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = 0;
        }
    }

    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod;
            if (j >= i) {
                dp[i][j] = (dp[i][j] - dp[i-1][j-i]+mod) % mod;
            }
        }
    }

    printf("%d\n", dp[n][k]);

    return 0;
}