#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3000050;
const int mod=998244353;
int mul(int x, int y){ return (ll)x*y%mod;}
int add(int x, int y){ x+=y;return x>=mod?x-mod:x;}
int pow(int x, int k){ int ans=1;for(;k;k>>=1,x=mul(x,x)) if(k&1) ans=mul(ans,x);return ans;}
int F[N],I[N];
void Calc()
{
	F[0]=1;
	for(int i=1;i<N;i++) F[i]=mul(F[i-1],i);
	I[N-1]=pow(F[N-1],mod-2);
	for(int i=N-2;~i;i--) I[i]=mul(I[i+1],i+1);
}
int Binom(int n, int k){ return mul(F[n],mul(I[k],I[n-k]));}
int Count(int n, int z){ return Binom(n+z-1,z);}
int main()
{
	Calc();
	int n,m;
	scanf("%i %i",&n,&m);
	int sum=0;
	for(int odd=0;odd<=min(m,n);odd++) if((odd%2)==(m%2))
	{
		int ways=Binom(n,odd);
		int ans=mul(ways,Count(n,(3*m-odd)/2)),tmp;
		//printf("%i ",ans);
		tmp=mul(ways,mul(n,Count(n,(m-odd)/2)));
		ans-=tmp;
		if(ans<0) ans+=mod;
		//printf("%i ",tmp);
		tmp=mul(mul(n,Binom(n-1,odd)),Count(n-1,(m-odd)/2));
		ans=add(ans,tmp);
		//printf("%i ",tmp);
		//printf("odd:%i ans:%i\n",odd,ans);
		sum=add(sum,ans);
	}
	printf("%i\n",sum);
	return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

We have a sequence of N integers: x=(x_0,x_1,\cdots,x_{N-1}). Initially, x_i=0 for each i (0 \leq i \leq N-1).

Snuke will perform the following operation exactly M times:

* Choose two distinct indices i, j (0 \leq i,j \leq N-1,\ i \neq j). Then, replace x_i with x_i+2 and x_j with x_j+1.



Find the number of different sequences that can result after M operations. Since it can be enormous, compute the count modulo 998244353.

Constraints

* 2 \leq N \leq 10^6
* 1 \leq M \leq 5 \times 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M


Output

Print the number of different sequences that can result after M operations, modulo 998244353.

Examples

Input

2 2


Output

3


Input

3 2


Output

19


Input

10 10


Output

211428932


Input

100000 50000


Output

3463133

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3000050;
const int mod=998244353;
int mul(int x, int y){ return (ll)x*y%mod;}
int add(int x, int y){ x+=y;return x>=mod?x-mod:x;}
int pow(int x, int k){ int ans=1;for(;k;k>>=1,x=mul(x,x)) if(k&1) ans=mul(ans,x);return ans;}
int F[N],I[N];
void Calc()
{
	F[0]=1;
	for(int i=1;i<N;i++) F[i]=mul(F[i-1],i);
	I[N-1]=pow(F[N-1],mod-2);
	for(int i=N-2;~i;i--) I[i]=mul(I[i+1],i+1);
}
int Binom(int n, int k){ return mul(F[n],mul(I[k],I[n-k]));}
int Count(int n, int z){ return Binom(n+z-1,z);}
int main()
{
	Calc();
	int n,m;
	scanf("%i %i",&n,&m);
	int sum=0;
	for(int odd=0;odd<=min(m,n);odd++) if((odd%2)==(m%2))
	{
		int ways=Binom(n,odd);
		int ans=mul(ways,Count(n,(3*m-odd)/2)),tmp;
		//printf("%i ",ans);
		tmp=mul(ways,mul(n,Count(n,(m-odd)/2)));
		ans-=tmp;
		if(ans<0) ans+=mod;
		//printf("%i ",tmp);
		tmp=mul(mul(n,Binom(n-1,odd)),Count(n-1,(m-odd)/2));
		ans=add(ans,tmp);
		//printf("%i ",tmp);
		//printf("odd:%i ans:%i\n",odd,ans);
		sum=add(sum,ans);
	}
	printf("%i\n",sum);
	return 0;
}
```