/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Ido Kessler
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <cstdint>
#include <cassert>

#include <tuple>
#include <cmath>
#include <random>

using ll = long long int;
using ull = unsigned long long int;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using pi = std::pair<int, int>;
using vpi = std::vector<pi>;
using vvpi = std::vector<vpi>;
using pll = std::pair<ll, ll>;
using vpll = std::vector<pll>;
using vvpll = std::vector<vpll>;
#define all(x) (x).begin(), (x).end()
#define fori(i, n) for(int i = 0; i < (int)(n); i++)
#define rep(i, s, e) for(int i = (int)(s); i <= (int)(e); ++i)
#define repr(i, s, e) for(int i = (int)(s); i >= (int)(e); --i)
#define pb push_back
template<typename T> void mk_unique(std::vector<T>& l) { if (!std::is_sorted(all(l))) std::sort(all(l)); auto it = std::unique(l.begin(), l.end()); auto d = std::distance(l.begin(), it); l.resize(d); }
template<typename T> T &smax(T& l, const T&r) { if(l<r) l=r; return l; }
template<typename T> T &smin(T& l, const T&r) { if(r < l) l=r; return l; }
constexpr int MOD = 998244353;//1000000007;
namespace io{class input_reader{
void throw_error(){throw std::runtime_error("No more inputs while reading number");}
template<typename T>inline void readIntegerValue(T&f){bool positive=true;f=0;char c;
if(!in.get(c))throw_error();
while(c<'0'||c>'9'){if(c=='-')positive=false;if(!in.get(c))throw_error();}
while(c>='0'&&c<='9'){f=(f<<3)+(f<<1)+(c&15);if(!in.get(c))break;}
if(!positive)f*=-1;}
public:
std::istream&in;
explicit input_reader(std::istream&in):in(in){}
inline void read(int&f){readIntegerValue(f);}
inline void read(short&f){readIntegerValue(f);}
inline void read(long int&f){readIntegerValue(f);}
inline void read(long long int&f){readIntegerValue(f);}
inline void read(unsigned int&f){readIntegerValue(f);}
inline void read(unsigned short&f){readIntegerValue(f);}
inline void read(unsigned long int&f){readIntegerValue(f);}
inline void read(unsigned long long int&f){readIntegerValue(f);}
template<typename T>inline void read(std::vector<T>&f){for(auto&i:f)read(i);}
template<typename T,int N>inline void read(std::array<T,N>&res){for(auto&i:res)read(i);}
template<typename T1,typename T2>inline void read(std::pair<T1,T2>&p){read(p.first,p.second);}
template<typename T>inline void read(T&f){in>>f;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t),read(args...);}
template<typename T>inline void readArray(int n,T*res){while(n--)read(*(res++));}
template<typename T>inline input_reader&operator>>(T&t){return read(t),*this;}
};}
namespace io{class output_writer{
std::ostream&out;
template<typename T>inline void printIntegerHelper(T x){if(x>=10)printIntegerHelper(x/10);out.put(x%10+48);}
template<typename T>inline void printInteger(T x){if(x<0)out.put('-'),x=-x;printIntegerHelper(x);}
template<typename T>inline void printArray(T&ar){bool first=true;for(auto&t:ar)print((first)? first=false,"":" ",t);}
public:
explicit output_writer(std::ostream&out):out(out){}
inline void flush(){out.flush();}
inline void print(){}
inline void print(char x){out.put(x);}
inline void print(short x){printInteger(x);}
inline void print(int x){printInteger(x);}
inline void print(long int x){printInteger(x);}
inline void print(long long int x){printInteger(x);}
inline void print(unsigned short x){printInteger(x);}
inline void print(unsigned int x){printInteger(x);}
inline void print(unsigned long int x){printInteger(x);}
inline void print(unsigned long long int x){printInteger(x);}
template<typename T1>inline void print(const T1&t1){out<<t1;}
template<typename T1,typename T2>inline void print(const std::pair<T1,T2>&t1){println(t1.first,' ',t1.second);}
template<typename T1>inline void print(const std::vector<T1>&t1){printArray(t1);}
template<typename T1,int N>inline void print(const std::array<T1,N>&t1){printArray(t1);}
template<typename T1,int N,int M>inline void print(const std::array<std::array<T1,M>,N>&t1){for(auto&t:t1)println(t);}
template<typename T1>inline void print(const std::vector<std::vector<T1>>&t1){bool first=true;for(auto&t:t1)print((first)? first=false,"":"\n",t);}
template<typename T,typename...Args>inline void print(const T&t,Args...args){print(t),print(args...);}
template<typename...Args>inline void println(Args...args){print(args...),print('\n');}
template<typename T>output_writer&operator<<(const T&t){return print(t),*this;}
};}
inline ll pow_mod(ll a,ll b,const ll MOD){ll res=1;for(ll i=1;b;b^=b&i,i<<=1,a=(a*a)%MOD)if(b&i)res=(res*a)%MOD;return res;}
inline ll mod_inv(const ll a,const ll MOD){return pow_mod(a,MOD-2,MOD);}
template<typename T>inline T gcd(T a,T b){T t;while(a!=0)t=a,a=b%a,b=t;return b;}
template<typename T>T lcm(const T &a,const T &b) {assert(a!=0&&b!=0);return a/gcd(a,b)*b;}
namespace math {
template<class T> int gMOD(T v){int res = (int)(v%MOD);if(res>=0) return res; return res + MOD;};
class mod_int{
using mi=mod_int;
int v;
public:
mod_int(int v):v(gMOD(v)){}
mod_int(unsigned int v):v(gMOD(v)){}
mod_int(long long int v):v(gMOD(v)){}
mod_int(unsigned long long int v):v(gMOD(v)){}
mod_int(long int v):v(gMOD(v)){}
mod_int(unsigned long int v):v(gMOD(v)){}
mod_int()=default;
mod_int(const mi& o)=default;
mod_int(mi&& o)=default;
inline mi& operator=(const mi& o)=default;
inline mi& operator=(mi&& o)=default;
inline mi& operator++(){if(v==MOD-1)v=0;else v++;return*this;}
inline mi& operator--(){if(v==0)v=MOD-1;else v--;return*this;}
inline mi operator++(int){mi t=*this;++(*this);return t;}
inline mi operator--(int){mi t=*this;--(*this);return t;}
inline bool friend operator==(const mi&lhs,const mi&rhs){return lhs.v==rhs.v;}
inline bool friend operator!=(const mi&lhs,const mi&rhs){return lhs.v!=rhs.v;}
template<typename T> inline bool friend operator==(const mi&lhs,const T&rhs){return lhs==mi(rhs);}
template<typename T> inline bool friend operator!=(const mi&lhs,const T&rhs){return lhs!=mi(rhs);}
inline mi friend operator-(const mi&lhs,const mi&rhs){mi res;res.v=lhs.v-rhs.v;if(res.v<0)res.v+=MOD;return res;}
inline mi friend operator+(const mi&lhs,const mi&rhs){mi res;res.v=lhs.v+rhs.v-MOD;if(res.v<0)res.v+=MOD;return res;}
inline mi friend operator*(const mi&lhs,const mi&rhs){return{((((long long int)lhs.v)*rhs.v))};}
inline mi friend operator/(const mi&lhs,const mi&rhs){return lhs*rhs.inv();}
template <typename T> inline mi friend operator-(const mi&lhs,const T&rhs){return lhs-mi(rhs);}
template <typename T> inline mi friend operator+(const mi&lhs,const T&rhs){return lhs+mi(rhs);}
template <typename T> inline mi friend operator*(const mi&lhs,const T&rhs){return lhs*mi(rhs);}
template <typename T> inline mi friend operator/(const mi&lhs,const T&rhs){return lhs/mi(rhs);}
template <typename T> inline mi& operator-=(const T&rhs){return*this=*this-rhs;}
template <typename T> inline mi& operator+=(const T&rhs){return*this=*this+rhs;}
template <typename T> inline mi& operator*=(const T&rhs){return*this=*this*rhs;}
template <typename T> inline mi& operator/=(const T&rhs){return*this=*this/rhs;}
inline mi inv()const{return pow(MOD-2);}
inline mi pow(long long int pw)const{mi res=1,val=*this;while(pw){if(pw&1)res*=val;val*=val;pw>>=1;}return res;}
inline operator int()const {return v;}
inline friend std::istream& operator>>(std::istream& in,mi&rhs){long long int v;in>>v;rhs={v};return in;}
inline friend std::ostream& operator<<(std::ostream& out,mi&rhs){out<<rhs.v;return out;}
};}
namespace math{
mod_int factorial(int n) {
static std::vector<mod_int>mem;static mod_int last;
if (mem.empty())last={1},mem.push_back(last);
while (n>=(int)mem.size())mem.push_back(mem.back()*last++);
return mem[n];}

mod_int n_choose_k(int n, int k){return factorial(n)/(factorial(k)*factorial(n-k));}
}
const double PI = 3.14159265358979323846264338327950288419716939937510;
std::mt19937 get_random_engine(){return std::mt19937(std::random_device()());}
template<typename T=int>T myrand(T high = std::numeric_limits<T>::max()) {assert(high > 0);
static std::mt19937 random_engine = get_random_engine();
return std::uniform_int_distribution<T>(0, high - 1)(random_engine);}
//#include "prioity_queue_with_changes/pq_with_changes.h"
//#include "points_query/point_query.hpp"
//#include "numeric/numeric.hpp"
//#include "hashes/hashes.hpp"
//#include "graphs/graphs.hpp"
//#include "geometry/geometry.hpp"
//#include "extension_operations/extensions.hpp"
//#include "ranges/ranges.hpp"
//#include "matching/unweighted_max_matching.hpp"
//#include "lists/lists.hpp"
using mi = math::mod_int;
using vmi = std::vector<mi>;
using vvmi = std::vector<std::vector<mi>>;

using namespace std;

class CShift {
    class Solver {
    public:
        io::input_reader in;
        io::output_writer out;

        Solver(std::istream &in, std::ostream &out) : in(in), out(out) {}

        void solve() {
            // <code here>
            string s;
            int k;
            in >> s >> k;
            s.pb('0');
            int number_of_1 = 0;
            for (char c : s) if (c == '1') number_of_1++;
            vi chunk_of_1;
            int n = s.size();
            for (int i = 0; i < n; i++) {
                int j = i;
                int cur = 0;
                while (j < n && s[j] == '1') cur++, j++;
                chunk_of_1.pb(cur);
                i = j;
            }
            n = chunk_of_1.size();
            vector<vvmi> dp(n + 1, vvmi(number_of_1 + 1, vmi(number_of_1 + 1)));
            dp[0][0][0] = 1;
            int ones_left = number_of_1;
            fori(i, n) {
                ones_left -= chunk_of_1[i];
                fori(action_used, number_of_1 + 1) {
                    fori(action_paid_for, action_used + 1) {
                        int cur = dp[i][action_used][action_paid_for];
                        if (cur == 0) continue;
                        fori(noo2u, chunk_of_1[i] + ones_left + 1) {
                            if (noo2u < chunk_of_1[i]) {
                                if (action_paid_for + chunk_of_1[i] - noo2u <= action_used) {
                                    dp[i + 1][action_used][action_paid_for + chunk_of_1[i] - noo2u] += cur;
                                }
                            } else if (noo2u == chunk_of_1[i]) {
                                dp[i + 1][action_used][action_paid_for] += cur;
                            } else {
                                int missing1 = noo2u - chunk_of_1[i];
                                if (missing1 > ones_left) break;

                                int new_action = action_used + missing1;
                                if (new_action > k || new_action > number_of_1) break;
                                dp[i + 1][new_action][action_paid_for] += cur;
                            }
                        }
                    }
                }
            }
            mi ans = 0;
            fori(i, number_of_1 + 1) ans += dp.back()[i][i];
            // </code here>
            out.println(ans);
        }
    };

public:
    void solve(std::istream &in, std::ostream &out) {
        Solver(in, out).solve();
    }
};

int main() {
	std::ios_base::sync_with_stdio(false), cin.tie(0);
	CShift solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 19928