#include<cstdio>
#include<cstring>
const int N=5e6+7,mod=998244353;
typedef long long ll;const ll Mod=mod;
char s[N];int fail[N];
void gfail(char*s)
{
	for(int i=0,j=*fail=-1;s[i];)
		if(j==-1||s[i]==s[j])fail[++i]=++j;
		else j=fail[j];
}
int k,g[N],p[N],zg[N];
inline int cdiv(int a,int b){return (a-1)/b+1;}
int F(int n)
{
//	printf("ans[%d]",n);
	int mn=n/2+1,ans=0;bool flg=1;
	while(flg)
	{
		int d=n-fail[n],lw=n%d;
		if(lw<mn)flg=0,lw+=cdiv(mn-lw,d)*d;
		int t=(n-2*lw%k+k)%k,zz=(d+d)%k;
//		printf("t=%d k=%d zz=%d nt=%d(lw=%d,d=%d)\n",t,k,zz,(n-lw)/d,lw,d);
		if(!(t%g[zz]))
		{
			int ps=((ll)p[zz]*(t/g[zz]))%zg[zz],nt=(n-lw)/d;
			if(nt>=ps)ans+=(nt-ps)/zg[zz]+1;
		}
		n=lw;
	}
//	printf("=%d\n",ans);
	return ans;
}
int exgcd(int a,int b,int&x,int&y)
{
	if(!b){x=1;y=0;return a;}
	int t=exgcd(b,a%b,y,x);y-=a/b*x;
	return t;
}
int main()
{
	scanf("%s%d",s+1,&k);gfail(s+1);int n=strlen(s+1),ans=1;
	for(int i=0,z;i<k;++i)g[i]=exgcd(i,k,p[i],z),zg[i]=k/g[i],p[i]=(p[i]+zg[i])%zg[i];
	for(int i=1;i<=n;++i)ans=ans*(F(i)+1LL)%Mod;printf("%d",ans);
	return 0;
}