#include <bits/stdc++.h>
using namespace std;
long long mod=998244353;
struct matr{
	long long a[3][3];
	friend matr operator*(matr a,matr b){
		int i,j,k;
		matr c;
		for(i=0;i<3;i++)
		{
			for(j=0;j<3;j++)c.a[i][j]=0;
		}
		for(i=0;i<3;i++)
		{
			for(j=0;j<3;j++)
			{
				for(k=0;k<3;k++)c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
			}
		}
		return c;
	}
};
matr qtim(matr a,int b){
	matr ans;
	int i,j;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(i==j)ans.a[i][j]=1;
			else ans.a[i][j]=0;
		}
	}
	while(b>0)
	{
		if(b&1)ans=ans*a;
		a=a*a;
		b>>=1;
	}
	return ans;
}
bool ntprime[1000001]={};
int prime[100000],pricnt=0,N=1000000,val[1000000];
void gen(){
	int i,j;
	ntprime[1]=1;
	val[1]=1;
	for(i=2;i<=N;i++)
	{
		if(!ntprime[i])
		{
			prime[pricnt]=i;
			val[i]=i-1;
			pricnt++;
		}
		for(j=0;j<pricnt&&i*prime[j]<=N;j++)
		{
			ntprime[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				val[i*prime[j]]=val[i]*prime[j];
				break;
			}
			else val[i*prime[j]]=val[i]*val[prime[j]];
		}
	}
}
int main(int argc, char** argv) {
	ios::sync_with_stdio(false),cin.tie(0);
	int m,k,i,j;
	gen();
	matr m1;
	cin>>m>>k;
	m1.a[0][0]=1;
	m1.a[0][1]=2;
	m1.a[0][2]=0;
	m1.a[1][0]=0;
	m1.a[1][1]=1;
	m1.a[1][2]=0;
	m1.a[2][0]=0;
	m1.a[2][1]=0;
	m1.a[2][2]=k*2+1;
	for(i=1;i<=k;i++)m1.a[1][2]=(m1.a[1][2]+val[i])%mod;
	m1.a[1][2]=(m1.a[1][2]*2+mod-1)*2%mod;
	m1=qtim(m1,m);
	cout<<(m1.a[0][0]+m1.a[0][1]+m1.a[0][2])%mod<<'\n';
	return 0;
}