#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int mod=1e9+7,N=3050;
ll Plus(ll a,ll b){while(a<0)a+=mod;while(b<0)b+=mod;a%=mod;b%=mod;return (a+b)%mod;}
ll Puta(ll a,ll b){while(a<0)a+=mod;while(b<0)b+=mod;a%=mod;b%=mod;return (a*b)%mod;}
ll dp[N+50][N+50];
string S="-NESW";
ll Bruteforce(int n,int m){
int a[n+1][m+1];
int e=1;for(int i=1;i<=n*m;i++) e*=5;
ll res=0;
for(int mask=0;mask<e;mask++){
int temp=mask;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++,temp/=5){
a[i][j]=temp%5;
}
}
bool moze=true;
for(int i=1;i<=n;i++){
vector<int>ind;
for(int j=1;j<=m;j++){
if(a[i][j]) ind.pb(j);
}
if(ind.size()>2) moze=false;
else if(ind.size()==2){
if(!(a[i][ind[0]]==2&&a[i][ind[1]]==4)) moze=false;
}
}
for(int j=1;j<=m;j++){
vector<int>ind;
for(int i=1;i<=n;i++){
if(a[i][j]) ind.pb(i);
}
if(ind.size()>2) moze=false;
else if(ind.size()==2){
if(!(a[ind[0]][j]==1&&a[ind[1]][j]==3)) moze=false;
}
}
if(moze){
res++;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<S[a[i][j]];
}
cout<<endl;
}
cout<<endl;
}
}
return res;
}
int main(){
int n,m;scanf("%i%i",&n,&m);
for(int i=0;i<=N;i++) dp[i][0]=dp[0][i]=1;
/*for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
dp[i][j]+=4*dp[i-1][j-1];
if(i>=2)dp[i][j]+=(i-1)*dp[i-2][j-1];
if(j>=2)dp[i][j]+=(j-1)*dp[i-1][j-2];
if(i>=2&&j>=2)dp[i][j]+=4*(i-1)*4*(j-1)*dp[i-2][j-2];
if(i>=2&&j>=3)dp[i][j]+=4*(i-1)*(((j-1)*(j-2))/2)*dp[i-2][j-3];
if(i>=3&&j>=2)dp[i][j]+=(((i-1)*(i-2))/2)*4*(j-1)*dp[i-3][j-2];
if(i>=3&&j>=3)dp[i][j]+=((((i-1)*(i-2))/2)*(((j-1)*(j-2))/2))*dp[i-3][j-3];
if(i>=2&&j>=3)dp[i][j]+=(i-1)*(j-2)*4*(j-1)*dp[i-2][j-3];
if(i>=3&&j>=2)dp[i][j]+=4*(i-1)*(j-1)*(i-2)*dp[i-3][j-2];
if(i>=3&&j>=3)dp[i][j]+=(i-1)*(j-2)*(j-1)*(i-2)*dp[i-3][j-3];
if(i>=2&&j>=4)dp[i][j]+=(i-1)*(j-1)*((j-2)*(j-3))/2*dp[i-2][j-4];
if(i>=4&&j>=2)dp[i][j]+=(i-1)*(j-1)*((i-2)*(i-3))/2*dp[i-4][j-2];
dp[i][j]%=mod;
}
}*/
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
dp[i][j]=Plus(Plus(dp[i-1][j],dp[i][j-1]),3*dp[i-1][j-1]);
if(i>=2)dp[i][j]+=Puta(i-1,dp[i-2][j-1]);
if(j>=2)dp[i][j]+=Puta(j-1,dp[i-1][j-2]);
if(i>=2&&j>=2)dp[i][j]+=Puta(Puta(4*(i-1),4*(j-1)),dp[i-2][j-2]);
if(i>=2&&j>=3)dp[i][j]+=Puta(Puta(4*(i-1),((j-1)*(j-2))/2),dp[i-2][j-3]);
if(i>=3&&j>=2)dp[i][j]+=Puta(Puta(((i-1)*(i-2))/2,4*(j-1)),dp[i-3][j-2]);
if(i>=3&&j>=3)dp[i][j]+=Puta(Puta(((i-1)*(i-2))/2,((j-1)*(j-2))/2),dp[i-3][j-3]);
if(i>=2&&j>=3)dp[i][j]+=Puta(Puta((i-1)*(j-2),4*(j-1)),dp[i-2][j-3]);
if(i>=3&&j>=2)dp[i][j]+=Puta(Puta(4*(i-1),(j-1)*(i-2)),dp[i-3][j-2]);
if(i>=3&&j>=3)dp[i][j]+=Puta(Puta((i-1)*(j-2),(j-1)*(i-2)),dp[i-3][j-3]);
if(i>=2&&j>=4)dp[i][j]+=Puta(Puta((i-1)*(j-1),((j-2)*(j-3))/2),dp[i-2][j-4]);
if(i>=4&&j>=2)dp[i][j]+=Puta(Puta((i-1)*(j-1),((i-2)*(i-3))/2),dp[i-4][j-2]);
dp[i][j]%=mod;
}
}
//cout<<Bruteforce(n,m)<<endl;
/*for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
printf("%i %i: %lld\n",i,j,dp[i][j]);
}
}*/
printf("%lld\n",dp[n][m]-1);
return 0;
}
Compilation message (stderr)
tents.cpp: In function 'int main()':
tents.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | int n,m;scanf("%i%i",&n,&m);
| ~~~~~^~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
