Language: C++

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
 
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
 
typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;
 
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 3007;
const int MOD = 998244353;

mt19937 rng;

Int dp[MAX][MAX][MAX];

int nx[MAX];

int main(int argc, char* argv[])
{
	//ios::sync_with_stdio(false); cin.tie(0);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());

    string s;
    cin >> s;
    int k;
    cin >> k;
    if (k > SZ(s))
        k = SZ(s);

    reverse(ALL(s));

    dp[0][0][0] = 1;

    nx[SZ(s)] = SZ(s);

    RFOR(i,SZ(s), 0) {
        if (s[i] == '0')
            nx[i] = i;
        else
            nx[i] = nx[i + 1];
    }

    FOR(i,0,SZ(s) + 1) {
        RFOR(j,i + 1,0) {
            FOR(k,0,i + 1) {
                if (dp[i][j][k] == 0)
                    continue;
                if ((i == SZ(s) || s[i] == '0') && j > 0) {
                    dp[i][j - 1][k] += dp[i][j][k];
                    dp[i][j - 1][k] %= MOD;
                }
                if (i == SZ(s))
                    continue;
                dp[i + 1][j][k] += dp[i][j][k];
                dp[i + 1][j][k] %= MOD;
                if (s[i] == '1' && nx[i] != SZ(s)) {
                    int cnt = nx[i] - i;
                    dp[nx[i] + 1][j + cnt][k + cnt] += dp[i][j][k];
                    dp[nx[i] + 1][j + cnt][k + cnt] %= MOD;
                }
            }
        }
    }

    Int res = 0;
    FOR(i, 0, k + 1) {
        // cout << i << ' ' << dp[SZ(s)][0][i] << endl;
        res += dp[SZ(s)][0][i];
        res %= MOD;
    }

    cout << res << endl;
    
    
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
	return 0;
}



Compiler output:
/tmp/ccDQolVX.o: in function `main':
a.cc:(.text+0x149): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
a.cc:(.text+0x19b): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
a.cc:(.text+0x1ba): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
a.cc:(.text+0x1d2): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
a.cc:(.text+0x58e): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
a.cc:(.text+0x5cc): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
a.cc:(.text+0x5e9): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
a.cc:(.text+0x67c): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
a.cc:(.text+0x6dc): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
a.cc:(.text+0x736): relocation truncated to fit: R_X86_64_PC32 against symbol `nx' defined in .bss section in /tmp/ccDQolVX.o
collect2: error: ld returned 1 exit status