#include <bits/stdc++.h>
#define ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;


const int mod = 998244353;

const int N = 307;

int dp[N][N][2*N][2];

inline int sum(int x, int y) {
	if (x+y < 0) return x+y+mod;
	if (x+y >= mod) return x+y-mod;
	return x+y;
}
 
inline int mult(int x, int y) {
	return ((ll) x * y) % mod;
}

int main(){
#ifdef LOCAL
	freopen("I_input.txt", "r", stdin);
	//freopen("I_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string s;
	cin >> s;

	int k;
	cin >> k;

	vector<int> arr;

	int R = 0;

	int now = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == '1') {
			R++;
			now++;
		}
		else {
			arr.push_back(now);
			now = 0;
		}
	}

	arr.push_back(now);

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

	int cur = 0;

	for (int i = 0; i < arr.size(); ++i) {

		for (int was = 0; was <= R; ++was) {
			for (int delta = 0; delta <= 2*s.size(); ++delta) {
				int T = sum(dp[i][was][delta][0], dp[i][was][delta][1]);
				if (T == 0) continue;

				for (int be = 0; be <= arr[i] && was+be <= R; ++be) {
					dp[i+1][was + be][delta + arr[i] - be][0] = sum(dp[i+1][was + be][delta + arr[i] - be][0], T);
				}

				if (i + 1 < arr.size() && was + arr[i] + 1 <= R) {
					dp[i+1][was+arr[i]+1][delta+1][1] = sum(dp[i+1][was+arr[i]+1][delta+1][1], T);
				}
			}
		}

		for (int was = 0; was <= R; ++was) {
			for (int delta = 0; delta <= 2*s.size(); ++delta) {
				if (dp[i+1][was][delta][1] && was+1 <= R) {
					dp[i+1][was+1][delta+1][1] = sum(dp[i+1][was][delta][1], dp[i+1][was+1][delta+1][1]);
				}
			}
		}

		cur += arr[i];

		for (int was = 0; was < cur; ++was) for (int delta = 0; delta <= 2*s.size(); ++delta) {
			dp[i+1][was][delta][0] = 0;
			dp[i+1][was][delta][1] = 0;
		}

	}

	//cout << dp[3][2][2][0] << " " << R << endl;

	int ans = 0;

	for (int delta = 0; delta <= 2*s.size(); ++delta) if (delta <= 2*k) {

		int T = sum(dp[arr.size()][R][delta][0], dp[arr.size()][R][delta][1]);

		ans = sum(ans, T);
	}

	cout << ans;

}

#include <bits/stdc++.h>

const double PI = 3.14159265358979323846;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<ll> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}


bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//const ll mod = 1e10;
//typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;



unordered_map<string, ll> check(int n, string &s) {
    unordered_map<string, ll> ans;
    rep(i, 1 << n) {
        string a, b;
        rep(j, n) {
            if ((i >> j) & 1) a.push_back(s[j]);
            else b.push_back(s[j]);
        }
        ans[a + ' ' + b]++;
    }
    return ans;
}

int main() {
    int n;
    string s;
    cin >> n >> s;

    string a = s.substr(0, n);
    string b = s.substr(n);

    unordered_map<string, ll> m1 = check(n, a);
    reverse(b.begin(), b.end());
    unordered_map<string, ll> m2 = check(n, b);

    ll ans = 0;
    for (auto &e : m1) {
        ll now = e.second * m2[e.first];
        ans += now;
    }
    cout << ans << endl;


}
