# 雅礼集训 小c的线段树

## 伪第三题DP

Posted by yjjr's blog on January 18, 2018

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=356,mod=998244353;
int t=0,m,n,k,f[2][maxn][maxn],ans[2][maxn][maxn];
ll g[maxn];
ll qpow(ll x,ll y){ll re=1;while(y){if(y&1)re=(re*x)%mod;x=(x*x)%mod,y>>=1;}return re;}

int main()
{
if(m>n){puts("0");return 0;}
rep(i,1,m)g[i]=qpow(i,k);
f[0][0][0]=1;
rep(i,1,n){
rep(r,0,m)
rep(l,0,r){
int &val=f[t][r][l],&s=ans[t][r][l];
if(!val&&!s)continue;
s=(s+1LL*g[r-l]*val)%mod;
rep(j,0,1)rep(k,0,1)
if(r+j>=l+k){
f[t^1][r+j][l+k]=(f[t^1][r+j][l+k]+val)%mod;
ans[t^1][r+j][l+k]=(ans[t^1][r+j][l+k]+s)%mod;
}
val=s=0;
}
t^=1;
}
cout<<ans[t][m][m]<<endl;
return 0;
}