stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

#include<algorithm>

#include<cmath>

#include<string>



using namespace std;



#define rep(i, n) for(int i = 0; i < n; i++)

#define repn(i, n) for(int i = 1; i <= n; i++)

#define repr(i, n) for(int i = (n-1); i >= 0; i--)

#define all(x) (x).begin(), (x).end()

#define lint long long



const int MAX_V = 100005;

vector<int> to[MAX_V];

bool seen[MAX_V];





int dfs(int s){

    seen[s] = true;

    if(to[s].empty()) return 1;

    else return dfs(to[s][0]) + 1;

}



int main(){

    int n, k; cin>>n>> k;

    int R, S, P; cin>>R>>S>>P;

    string t; cin >> t;



    for(int i = 0; i < n-k; i++){

        if(t[i] == t[i+k]){

            to[i].push_back(i+k);

        }

    }



    long ans = 0;

    rep(i, n){

        if(!seen[i]){

            int res = (dfs(i) + 1) / 2;

            int po;

            if(t[i] == 'r') po = P;

            else if(t[i] == 's') po = R;

            else po = S;

            ans += po * res;

        }

    }



    cout << ans << endl;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)

#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)

#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)

#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)

#define all(x) (x).begin(), (x).end()

#define lint long long

#define ulint unsigned long long

#define ldou long double

#define fi first

#define se second

#define setpre(x) std::cout << fixed << setprecision(x)

#define ii(x) int x; cin >> (x)

#define ii2(x, y) int x, y; cin >> (x) >> (y)

#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)

#define out(x) cout << (x) << endl

#define outs(x) cout << (x) << " "

#define yn(x) cout << ((x)?("Yes"):("No")) << endl

#define YN(x) cout << ((x)?("YES"):("NO")) << endl

#define bit_c(x) __builtin_popcountll(x)



inline void logger(){ std::cout << " [LOGGER] " << endl; }

template<typename A, typename... B>

void logger(const A& a, const B&... b){

    cout << a << " , "; logger(b...);

}



typedef pair<lint, lint> P;

const lint MOD = 1000000007;

const lint MOD9 = 998244353;

const lint INF = MOD * MOD;

const int MAX = 200005;



/* ...o(^-^)o... */



int main(){

    int n,k; cin>>n>>k;

    int r,s,p; cin>>r>>s>>p;

    string t; cin>>t;

    vector<bool> f(n);

    int res = 0;

    rep(i,n){

        if(i>=k && t[i]==t[i-k] && f[i-k]) continue;

        if(t[i]=='r') res += p;

        else if(t[i]=='s') res += r;

        else res += s;

        f[i] = true;

    }

    out(res);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

long long mod=1e9+7;

long long no[180],ans[180];

map<long long,long long> mp;

long long f(long long k)

{

    if (mp[k]) return mp[k];

    for(int i=1;i<=177;i++)

        if (k==no[i]) return mp[k]=ans[i];

    if (k%2==0) return mp[k]=(2*f(k/2-1)+f(k/2))%mod;

    return mp[k]=(f(k/2-1)+2*f(k/2))%mod;

}

int main()

{

     long long n;

     cin>>n;

     no[1]=0;no[2]=1;no[3]=2;

     ans[1]=1;ans[2]=2;ans[3]=4;

     for(int i=2;i<=59;i++)

     {

          no[3*i-2]=(1ll<<i)-2;

          no[3*i-1]=no[3*i-2]+1;

          no[3*i]=no[3*i-1]+1;

          ans[3*i-2]=(2*ans[3*i-5]+ans[3*i-4])%mod;

          ans[3*i-1]=(ans[3*i-5]+2*ans[3*i-4])%mod;

          ans[3*i]=(ans[3*i-1]+i+1)%mod;

     }

     cout<<f(n)<<endl;

     return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long ll;



const ll MOD = 1E9 + 7, MAXD = 60;



ll n;

ll f[MAXD + 1][3];



int main(){

	scanf("%lld", &n);



	f[MAXD][0] = 1;

	for (int i = MAXD - 1; i >= 0; --i){

		int z = n >> i & 1;

		if (z == 0){

			f[i][0] = (f[i + 1][0] + f[i + 1][1]) % MOD;

			f[i][1] = (f[i + 1][1]) % MOD;

			f[i][2] = (f[i + 1][1] + f[i + 1][2] * 3) % MOD;

		}

		else{

			f[i][0] = (f[i + 1][0]) % MOD;

			f[i][1] = (f[i + 1][0] + f[i + 1][1]) % MOD;

			f[i][2] = (f[i + 1][1] * 2 + f[i + 1][2] * 3) % MOD;

		}

	}



	printf("%lld\n", (f[0][0] + f[0][1] + f[0][2]) % MOD);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



typedef long long LL;

typedef long double LB;

typedef pair<int, int> PII;

typedef pair<LL, LL> PLL;



const int INF = 0x3f3f3f3f;

const LL INFL = 0x3f3f3f3f3f3f3f3fLL;

const LB eps = 1e-8;

const LL MOD = 1e9 + 7;

const int DIGS = 70;



template <typename T>

inline bool scan_d (T &ret) {

    char c;

    int sgn;

    if (c = getchar(), c == EOF) return 0; //EOF

    while (c != '-' && (c < '0' || c > '9') ) c = getchar();

    sgn = (c == '-') ? -1 : 1;

    ret = (c == '-') ? 0 : (c - '0');

    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');

    ret *= sgn;

    return 1;

}

template<typename T>

void print(T x) {

    static char s[33], *s1; s1 = s;

    if (!x) *s1++ = '0';

    if (x < 0) putchar('-'), x = -x;

    while(x) *s1++ = (x % 10 + '0'), x /= 10;

    while(s1-- != s) putchar(*s1);

}

template<typename T> void println(T x) { print(x); putchar('\n');}



LL n;

//LL dig[DIGS];

//

//void init() {

//    dig[0] = 0;

//    while(n > 0) {

//        dig[++ dig[0]] = n & 1;

//        n >>= 1;

//    }

//}

map<LL, LL> ans;

LL calc(LL x) {

    if(x == 0) return 1;

    if(x == 1) return 2;

    if(x == 2) return 4;

    LL ret = ans[x];

    if(!ret) {

        ret += calc(x >> 1);

        if(ret >= MOD) ret -= MOD;

        ret += calc((x - 1) >> 1);

        if(ret >= MOD) ret -= MOD;

        ret += calc((x - 2) >> 1);

        if(ret >= MOD) ret -= MOD;

        ans[x] = ret;

    }

    return ret;

}



int main() {

#ifdef ___LOCAL_WONZY___

//    freopen("input.txt", "r", stdin);

#endif // ___LOCAL_WONZY___

    scan_d(n);

//        init();

    println(calc(n));

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long ll;



const ll MOD = 1E9 + 7, MAXD = 60;



ll n;

ll f[MAXD + 1][3];



int main(){

	scanf("%lld", &n);



	f[MAXD][0] = 1;

	for (int i = MAXD - 1; i >= 0; --i){

		int z = n >> i & 1;

		if (z == 0){

			f[i][0] = (f[i + 1][0] + f[i + 1][1]) % MOD;

			f[i][1] = (f[i + 1][1]) % MOD;

			f[i][2] = (f[i + 1][1] + f[i + 1][2] * 3) % MOD;

		}

		else{

			f[i][0] = (f[i + 1][0]) % MOD;

			f[i][1] = (f[i + 1][0] + f[i + 1][1]) % MOD;

			f[i][2] = (f[i + 1][1] * 2 + f[i + 1][2] * 3) % MOD;

		}

	}



	printf("%lld\n", (f[0][0] + f[0][1] + f[0][2]) % MOD);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#include <algorithm>

#include <queue>

using namespace std;

long long int pow2[61] = {}; 

long long int dp[300010] = {}; 

long long int pow3[61] = {}; 

long long int P = 1e9 + 7; 

long long int ans(long long int n){

	if(n < 300000 && dp[n] > -1){return dp[n];}

        if(n == 0){

         		return dp[0] = 1; 

        }

		int a = upper_bound(pow2, pow2 + 61, n) - pow2; 

		long long int b = pow2[a] - n; 

		if(b == 1){

			if(n < 300000){return dp[n] = (pow3[a] + 1)/2 % P;}

			else{return (pow3[a] + 1)/2 % P;}

		}

		else{

			long long int Q = (P + pow3[a-1] + ans(n - pow2[a-1]) - ((n == pow2[a] - 2) ? 0 : ans(pow2[a] - n - 3))) % P;

			if(n < 300000){return dp[n] = Q;}

			else{return Q;} 		

		} 

	}

int main() {

	pow2[0] = 1, pow3[0] = 1; 

	for(int i = 1; i <= 60; i++){

		pow2[i] = pow2[i-1] * 2; 

		pow3[i] = (pow3[i-1] * 3) % P; 

	}

	for(int i = 0; i < 300000; i++){

		dp[i] = -1;  

	}

	long long int N; 

	cin >> N; 

	cout << ans(N) << endl; 

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#include <algorithm>

#include <queue>

using namespace std;

int main(){

	long long int N; 

	cin >> N; 

	long long int P = 1e9 + 7; 

	long long int dp[64][3] = {}; //dp[a,bの上位i桁まで決定済][上位i桁までの足し算でNがa+bよりどれだけ大きいか．負なら大小逆転，2以上なら追いつけないので確定でOK] = 場合の数 mod P

	dp[0][0] = 1; 

	for(int i = 1; i <= 60; i++){//Leading zerosを補って60桁と見なす．

		if((N >> (60-i)) & 1){

			dp[i][0] = dp[i-1][0]; 

			dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % P; 

          		dp[i][2] = (dp[i-1][1] * 2 + dp[i-1][2] * 3) % P; 

		}

		else{

			dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % P; 

            		dp[i][1] = dp[i-1][1]; 

            		dp[i][2] = (dp[i-1][1] + dp[i-1][2] * 3) % P; 

		}

	}

	cout << (dp[60][0] + dp[60][1] + dp[60][2]) % P << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

int N,K;

#define mod 998244353

#define MN 2005

ll fac[MN<<1],inv[MN<<1],p2[MN<<1];

ll quick_pow(ll x,ll m){

	ll res=1;

	while(m){

		if(m&1) m^=1,res=res*x%mod;

		else m>>=1,x=x*x%mod;

	}

	return res;

}

ll C(int m,int n){

	if(n<0||n>m) return 0;

	return (1LL)*fac[m]%mod*inv[n]%mod*inv[m-n]%mod;

}

ll f(int n,int k,int j){

	register int l;

	ll ans=0;

	for(l=0;l<=k;l++) ans=(ans+(p2[l]*C(n+j-1,l+j-1)%mod)*C(k,l)%mod)%mod;

	return ans;

}

ll calc(int i){

	if(K*2<=i) return 0;

	return (i-1)/2-max(0,i-1-K);

}

int main(){

	register int i;

	p2[0]=1;for(i=1;i<=4005;i++) p2[i]=p2[i-1]*2%mod;

	fac[0]=1;for(i=1;i<=4005;i++) fac[i]=fac[i-1]*i%mod;

	inv[4005]=quick_pow(fac[4005],998244351);for(i=4004;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;

	scanf("%d%d",&K,&N);

	for(i=2;i<=K*2;i++){

		ll box=calc(i);

		if(i&1) printf("%lld\n",f(N,box,K-box*2)%mod);

		else printf("%lld\n",(f(N,box,K-1-box*2)+f(N-1,box,K-1-box*2))%mod);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



const int N = 4e3 + 5;

const int P = 998244353;



int n, k, c[N][N];



void init(int n) {

	c[0][0] = 1;

	for (int i = 1; i <= n; i++) {

		c[i][0] = 1;

		for (int j = 1; j <= i; j++) {

			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;

		}

	}

}

void add(int &x, int y) {

	(x += y) >= P && (x -= P);

}

int main() {

	scanf("%d%d", &k, &n);

	init(n + k);

	for (int i = 2; i <= k + k; i++) {

		int cnt = 0, ans = 0;

		for (int j = 1; i - j >= j; j++) {

			cnt += (j <= k && i - j <= k);

		}

		for (int j = 0, sgn = 1; j <= cnt && j + j <= n; j++, sgn = P - sgn) {

			add(ans, 1LL * sgn * c[cnt][j] % P * c[n - 2 * j + k - 1][k - 1] % P);

		}

		printf("%d\n", ans);

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <vector>

#include <set>

#include <map>

#include <stack>

#include <queue>

#define rep(i,l,r) for(int i=(l);i<=(r);++i)

#define per(i,r,l) for(int i=(r);i>=(l);--i)

using namespace std;

const int maxn=4010,P=998244353;

int n,k,a[maxn],fac[maxn],ifac[maxn],inv[maxn],ans;

inline int C(int a,int b){return 1ll*fac[a]*ifac[b]%P*ifac[a-b]%P;}

inline int calc(int n,int s){

        int k2=min(k-s/2,(s-1)/2),k1=k-k2*2-!(s&1),ans=0;

        rep(i,0,k2)

            if(i&1) ans=(ans-1ll*a[k2-i]*C(k2,i)%P*C(n+k1+k2-i-1,k1+k2-i-1)%P+P)%P;

            else ans=(ans+1ll*a[k2-i]*C(k2,i)%P*C(n+k1+k2-i-1,k1+k2-i-1)%P)%P;

        return ans;

    }

int main(){

    scanf("%d%d",&k,&n);

    a[0]=inv[1]=fac[0]=ifac[0]=1;

    rep(i,2,2*max(n,k)) inv[i]=1ll*(P-P/i)*inv[P%i]%P;

    rep(i,1,2*max(n,k)) a[i]=1ll*a[i-1]*2%P,fac[i]=1ll*fac[i-1]*i%P,ifac[i]=1ll*ifac[i-1]*inv[i]%P;

    rep(i,2,2*k){

        ans=calc(n,i);

        if(i%2==0) ans=(ans+calc(n-1,i))%P;

        printf("%d\n",ans);

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



const int N = 4e3 + 5;

const int P = 998244353;



int n, k, c[N][N];



void init(int n) {

	c[0][0] = 1;

	for (int i = 1; i <= n; i++) {

		c[i][0] = 1;

		for (int j = 1; j <= i; j++) {

			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;

		}

	}

}

void add(int &x, int y) {

	(x += y) >= P && (x -= P);

}

int main() {

	scanf("%d%d", &k, &n);

	init(n + k);

	for (int i = 2; i <= k + k; i++) {

		int cnt = 0, ans = 0;

		for (int j = 1; i - j >= j; j++) {

			cnt += (j <= k && i - j <= k);

		}

		for (int j = 0, sgn = 1; j <= cnt && j + j <= n; j++, sgn = P - sgn) {

			add(ans, 1LL * sgn * c[cnt][j] % P * c[n - 2 * j + k - 1][k - 1] % P);

		}

		printf("%d\n", ans);

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):


#include <bits/stdc++.h>

using namespace std;



using ll = long long;

#define f(i,a,b) for (int i = a; i < b; i++)

#define fr(i,a,b) for (int i = b-1; i >= a; i--)



const int mod = 998244353;

const int mxn = 1e5;

int n,K;



void add(ll &a, ll b) { if (b>=mod) b%=mod; a+=b; if (a>=mod) a-=mod; }

ll modpow(ll a, ll b) {

	return b?modpow(a*a%mod,b/2)*(b&1?a:1)%mod:1;

}

struct Comb {

	ll fac[mxn], inv[mxn], twopow[mxn];	

	Comb() {

		f(i,0,mxn) {

			fac[i]=i?fac[i-1]*i%mod:1;

			twopow[i]=i?twopow[i-1]*2%mod:1;

		}

		inv[mxn-1]=modpow(fac[mxn-1],mod-2);

		fr(i,0,mxn-1) {

			inv[i]=inv[i+1]*(i+1)%mod;

		}

	}

	ll choose(int n, int r) {

		if (n<0||n<r||r<0) return 0;

		return fac[n]*inv[r]%mod*inv[n-r]%mod;

	}

	ll multichoose(int n, int k) {

		if (!n&&!k) return 1;

		return choose(n+k-1,k);

	}

	ll pow2(int n) {

		if (n<0) return 0;

		return twopow[n];

	}

} C;



ll solve(int x) {

	ll ans = 0;

	int a = 0, b = 0;

	f(i,1,K+1) {

		if (i+i==x) b++;

		if (i<=K && x-i<=K && x-i>0) a++;

	}

	a/=2;

	f(na,0,a+1) {

		f(nb,0,b+1) {

			add(ans,C.pow2(na)*C.choose(a,na)%mod*C.multichoose(na+K-2*a-b,n-na-nb));		

		}

	}

	return ans;

}



const int DEBUG = 1;



int main() {

	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

#ifdef LOCAL

	if (DEBUG) freopen("input.txt", "r", stdin);

	if (DEBUG) freopen("output.txt", "w", stdout);

#endif



	cin >> K >> n;

	for (int x = 2; x <= 2*K; x++)

		cout << solve(x) << endl;

	cout << endl;



	return 0;

}




// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int N=5000,D=998244353;



ll qpow(ll x,ll k) {

	ll ret=1;

	while(k) {

		if(k&1) ret=ret*x%D;

		x=x*x%D;

		k>>=1;

	}

	return ret;

}

ll fac[N+233],inv[N+233],tot,mul2[N+233];

void first() {

	fac[0]=inv[0]=1;

	for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%D;

	inv[N]=qpow(fac[N],D-2);

	for(int i=N-1;i;i--) inv[i]=inv[i+1]*(i+1)%D;

	mul2[0]=1;

	for(int i=1;i<=N;i++) mul2[i]=mul2[i-1]*2%D;

}

ll C(ll x,ll y) {

	if(y<0) return 0;

	return fac[x]*inv[y]%D*inv[x-y]%D;

}

ll calc(ll x,ll y,ll z) {//x position,y pair limit,z others

	ll ret=0;

	for(int i=0;i<=min(y,x);i++)

		ret=(ret+C(y,i)*mul2[i]%D*C(x+z-1,i+z-1))%D;

	return ret;

}

int n,K;

int main() {

	first();

	scanf("%d%d",&K,&n);

	for(int i=2;i<=(K<<1);i++) {

		int p=0,o;

		for(int j=1,k=i-1;j<k;j++,k--) if(j<=K&&k<=K) ++p;

		o=K-2*p;

		ll ans=0;

		if(i&1) ans=calc(n,p,o);

		else --o,ans=(calc(n,p,o)+calc(n-1,p,o))%D;

		printf("%lld\n",(ans+D)%D);

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<cstdlib>

#define min(a,b) (a<b?a:b)

const int clz=998244353;

#define mod clz

long long matm(long long val,long long k){

	long long ret=1;

	while(k){

		if(k&1) ret=ret*val%mod;

		k>>=1; val=val*val%mod;

	}

	return ret;

}

int n,k;

long long pw[100005],pu[100005],inv[100005];

inline long long C(int n,int m){if(m<0||m>n) return 0;return (pu[n]*inv[m]%mod)*inv[n-m]%mod;}

long long getans(int val){

	if(val&1){

		long long ans=0;

		int gro=min(k-val/2,val/2);

		int p=k-gro*2;

		//if(p==0) exit(0);

		for(int i=(p==0)?1:0;i<=gro;i++) {ans+=(C(n+p-1,i+p-1)*pw[i]%mod)*C(gro,i)%mod; ans%=mod;}

		return ans;

	}

	else{

		long long ans=0;

		int gro=min(k-val/2+1,val/2);

		int p=k-gro*2+1;

		//if(p==0) exit(0);

		for(int i=(p==0)?1:0;i<gro;i++) {ans+=(C(n+p-1,i+p-1)*pw[i]%mod)*C(gro-1,i)%mod; ans%=mod;}

		for(int i=(p==0)?1:0;i<gro;i++) {ans+=(C(n+p-2,i+p-1)*pw[i]%mod)*C(gro-1,i)%mod; ans%=mod;}

		return ans;

	}

}

int main(){

	pu[0]=pw[0]=1;

	for(int i=1;i<=100000;i++) pu[i]=pu[i-1]*i%mod;

	for(int i=1;i<=100000;i++) pw[i]=pw[i-1]*2%mod;

	inv[100000]=matm(pu[100000],mod-2);

	for(int i=99999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;

	scanf("%d%d",&k,&n);

	for(int i=2;i<=2*k;i++) printf("%lld\n",getans(i));

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define mod 998244353

#define MN 4000

using namespace std;

inline int in(){

    int x=0;bool f=0;char c;

    for (;(c=getchar())<'0'||c>'9';f=c=='-');

    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');

    return f?-x:x;

}

int fac[MN+5],pw[MN+5],inv[MN+5];

int n,k,res,num;

inline int qpow(int x,int k){

	int res=1;

	while (k){

		if (k&1) res=(1ll*res*x)%mod;

		x=(1ll*x*x)%mod;k>>=1;

	}return res;

}

inline int C(int x,int y){

	if (x<y||y<0) return 0;

	return (1ll*fac[x]*inv[y]%mod*inv[x-y]%mod);

}

inline int calc(int x,int p,int n){

	int res=0;

	for (int i=0;i<=x;++i)

	res=(1ll*res+(1ll*pw[i]*C(x,i)%mod*C(n+p-1,p+i-1)%mod))%mod;

	return res;

}

int main()

{

	fac[0]=pw[0]=1;

	for (int i=1;i<=MN;++i)

	fac[i]=(1ll*fac[i-1]*i)%mod,pw[i]=(pw[i-1]*2)%mod;

	inv[MN]=qpow(fac[MN],mod-2);

	for (int i=MN-1;i>=0;--i)

	inv[i]=(1ll*inv[i+1]*(i+1))%mod;

	k=in();n=in();

	for (int i=2;i<=(k<<1);++i){

		num=min(i-1,k)-max(i-k-1,0);

		if (i&1) printf("%d\n",calc((num>>1),k-num,n));

		else printf("%d\n",(calc(((num-1)>>1),k-num,n)+calc(((num-1)>>1),k-num,n-1))%mod);

	}return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

string s[2005];

int val[2005][2005];

int main()

{

	int n,m;

	cin>>n>>m;

	for(int i=0;i<n;i++)

		cin>>s[i];

	for(int i=0;i<n;i++)

	{

		int cur=0;

		for(int j=0;j<m;j++)

		{

			val[i][j]+=cur;

			if(s[i][j]=='.')

				cur++;

			else

				cur=0;

		}

		cur=0;

		for(int j=m-1;j>=0;j--)

		{

			val[i][j]+=cur;

			if(s[i][j]=='.')

				cur++;

			else

				cur=0;

		}

	}

	for(int j=0;j<m;j++)

	{

		int cur=0;

		for(int i=0;i<n;i++)

		{

			val[i][j]+=cur;

			if(s[i][j]=='.')

				cur++;

			else

				cur=0;

		}

		cur=0;

		for(int i=n-1;i>=0;i--)

		{

			val[i][j]+=cur;

			if(s[i][j]=='.')

				cur++;

			else

				cur=0;

		}

	}

	int ans=0;

	for(int i=0;i<n;i++)

	{

		for(int j=0;j<m;j++)

		{

			if(s[i][j]=='.')

				ans=max(ans,val[i][j]);

		}

	}

	cout<<ans+1<<"\n";

	return 0;

}




// Optimized solution to the same problem (faster):
#include<stdio.h>



char g[2001][2001];

int n,m,maxc[2001][2001],maxr[2001][2001],lst=-1,res,max;



int main(){

	scanf("%d%d",&n,&m);

	for(int i=0;i<n;i++)scanf("%s",g[i]);

	for(int i=0;i<n;i++,lst=-1,res=0)for(int j=0;j<=m;j++)

		if(j==m||g[i][j]!='.'){

			for(int k=lst+1;k<j;k++)maxc[i][k]=res;

			res=0,lst=j;

		}

		else res++;

	lst=-1,res=0;

	for(int j=0;j<m;j++,lst=-1,res=0)for(int i=0;i<=n;i++)

		if(i==n||g[i][j]!='.'){

			for(int k=lst+1;k<i;k++)maxr[k][j]=res;

			res=0,lst=i;

		}

		else res++;

	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(maxc[i][j]+maxr[i][j]>max)max=maxc[i][j]+maxr[i][j];

	printf("%d\n",max-1);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

#include<algorithm>

#include<string>

#include<stdio.h>

#include<math.h>



#define ELIF else if

#define FOR(iterator, limit, adder) for(int iterator=0; iterator<limit; iterator+=adder)

#define PI 3.1415926535897932384626433832795

#define PB push_back



typedef long int int32;

typedef unsigned long int uint32;

typedef long long int int64;

typedef unsigned long long int  uint64;

typedef long long ll;



using namespace std;



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    

    string s;



    cin>> s;

    s[3]= '8';

    cout<< s<< "\n";

}

// Optimized solution to the same problem (faster):
#include <stdio.h>



int main()

{

	char str[12];

	scanf("%s", str);

	

	str[3]='8';

	

	puts(str);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<string>



using namespace std;



int main()

{

string in;

cin>>in;

in[3] = '8';

cout<<in;

return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>



int main()

{

	char str[12];

	scanf("%s", str);

	

	str[3]='8';

	

	puts(str);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;



//Compiler version g++ 6.3.0



int main()

{

    string s;

    

    cin >> s;

    

    s[0]='2';

    s[1]='0';

    s[2]='1';

    s[3]='8';

    

    cout << s << endl;

    

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

	char s[11];

	scanf("%s",s);

	s[3]='8';

	printf("%s",s);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



int main()

{

    char s[20];

    cin >> s;

    s[3]='8';

    cout << s;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

	char s[11];

	scanf("%s",s);

	s[3]='8';

	printf("%s",s);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main(void)

{

    char S[12];

    cin>>S;

    cout<<"2018";

    for(int i=4;S[i];i++)

        cout<<S[i];

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

	char s[11];

	scanf("%s",s);

	s[3]='8';

	printf("%s",s);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

	string s;

 cin>>s;

	s[3]='8';

	cout<<s;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

int main(){

	char string[20];

	scanf("%[^\n]", string);

	string[3] = '8';

	printf("%s", string);

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main(){

string s;

cin >> s;

s[3] = '8';

cout << s;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

int main(){

	char string[20];

	scanf("%[^\n]", string);

	string[3] = '8';

	printf("%s", string);

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<string>

using namespace std;

int main()

{

	ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    string a;

    cin>>a;

    a[3]='8';

    cout<<a;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

int main(){

	char string[20];

	scanf("%[^\n]", string);

	string[3] = '8';

	printf("%s", string);

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

 

 using namespace std;

  int main() {

       string s;

       while(cin>>s){

       int l=s.length();

       for(int i=0;i<l;i++){

       if(i==0) cout<<'2';

       else if(i==1) cout<<'0';

       else if(i==2) cout<<'1';

       else if(i==3) cout<<'8';

       else cout<<s[i];

                }

           cout<<endl;

		        }

    

	 return 0;

	  }

// Optimized solution to the same problem (faster):
#include <stdio.h>

int main(){

	char string[20];

	scanf("%[^\n]", string);

	string[3] = '8';

	printf("%s", string);

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

using namespace std;

int main(){

    string S;

    cin >> S;

    S[3] = '8';

    cout << S << endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

main(){char S[10];scanf("%s",S);S[3]=56;printf("%s\n",S);}

// Fastest known solution for this problem: