Code : K Zero Stream

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

void inc(int &a, int b) {
    a += b;
    a %= mod;
}

void solve(int n, int k) {
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    // dp[i][x] is the number of good binary strings of length n that has x
    // zeroes as its suffix.

    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int x = 0; x < k; x++) {
            // Append a one.
            inc(dp[i + 1][0], dp[i][x]);

            // Append a zero if allowed.
            if (x + 1 < k) {
                inc(dp[i + 1][x + 1], dp[i][x]);
            }
        }
    }

    int ans = 0;
    for (int x = 0; x < k; x++) {
        inc(ans, dp[n][x]);
    }
    cout << ans << "\n";
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, k;
        cin >> n >> k;
        solve(n, k);
    }
    return 0;
}