// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-11;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	inline long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
char in[1600][1600];
vector<char> v[1600][1600];
vector<int>g[1600];
int D[1600];
int E[1600];
int w[1600];
int dfs(int a){
	w[a]=1;
	int ret=0;
	for(int i=0;i<g[a].size();i++){
		int to=g[a][i];
		if(w[to]){
			ret++;
			continue;
		}
		ret+=dfs(to)+1;
	}
	// printf("%d: %d\n",a,ret);
	return ret;
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		scanf("%s",in[i]);
	}
	for(int i=0;i<a-1;i++){
		for(int j=0;j<a-1;j++){
			int x=i+j-(a-2);
			int y=i-j;
			v[ABS(x)][ABS(y)].push_back(in[i][j]);
			// if(in[i][j]!='?')printf("%d %d: %c\n",ABS(x),ABS(y),in[i][j]);
		}
	}
	int n=a-1;
	long long ret=1;
	for(int i=0;i<2;i++){
		int s=0;
		int N=(a-i)/2+1;
		for(int j=0;j<N;j++){
			g[j].clear();
			D[j]=E[j]=0;
			w[j]=0;
		}
		for(int j=i;j<n;j+=2){
			for(int k=(i+a)%2;j+k<n;k+=2){
				int t=-1;
				for(int l=0;l<v[j][k].size();l++){
					if(v[j][k][l]=='o'){
						if(t==1)ret=0;
						else t=0;	
					}
					if(v[j][k][l]=='x'){
						if(t==0)ret=0;
						else t=1;
					}

				}
				if(t==-1){
					s++;
					g[j/2].push_back(N-1-k/2);
					g[N-1-k/2].push_back(j/2);
					// printf("%d %d\n",j/2,N-1-k/2);
					D[j/2]++;
					D[N-1-k/2]++;
				}
				if(t==0){
					E[j/2]++;
					E[N-1-k/2]++;
				}
			}
		}
		if(N%2==0){
			ret=ret*pw(2,s)%mod;
			continue;
		}

		int F=0;
		for(int j=0;j<N;j++){
			if(D[j]==0&&E[j]%2){
				ret=0;
			}
			if(D[j])F--;
		}
		for(int j=0;j<N;j++){
			if(D[j]==0)continue;
			if(w[j])continue;
			int f=dfs(j)/2;
			F+=f+1;
		}
		ret=ret*pw(2,F)%mod;

	}
	printf("%lld\n",ret);
}
### Prompt

Generate a CPP solution to the following problem:

In a two-dimensional plane, there is a square frame whose vertices are at coordinates (0,0), (N,0), (0,N), and (N,N). The frame is made of mirror glass. A ray of light striking an edge of the frame (but not a vertex) will be reflected so that the angle of incidence is equal to the angle of reflection. A ray of light striking a vertex of the frame will be reflected in the direction opposite to the direction it is coming from.

We will define the path for a grid point (a point with integer coordinates) (i,j) (0<i,j<N) strictly within the frame, as follows:

* The path for (i,j) is the union of the trajectories of four rays of light emitted from (i,j) to (i-1,j-1), (i-1,j+1), (i+1,j-1), and (i+1,j+1).



<image>

Figure: an example of a path for a grid point

There is a light bulb at each grid point strictly within the frame. We will assign a state - ON or OFF - to each bulb. The state of the whole set of bulbs are called beautiful if it is possible to turn OFF all the bulbs by repeating the following operation:

* Choose a grid point strictly within the frame, and switch the states of all the bulbs on its path.



Takahashi has set the states of some of the bulbs, but not for the remaining bulbs. Find the number of ways to set the states of the remaining bulbs so that the state of the whole set of bulbs is beautiful, modulo 998244353. The state of the bulb at the grid point (i,j) is set to be ON if A_{i,j}=`o`, OFF if A_{i,j}=`x`, and unset if A_{i,j}=`?`.

Constraints

* 2 \leq N \leq 1500
* A_{ij} is `o`, `x`, or `?`.

Input

Input is given from Standard Input in the following format:


N
A_{1,1}...A_{1,N-1}
:
A_{N-1,1}...A_{N-1,N-1}


Output

Print the answer.

Examples

Input

4
o?o
???
?x?


Output

1


Input

5
o?o?
????
o?x?
????


Output

0


Input

6
?o???
????o
??x??
o????
???o?


Output

32


Input

9
????o??x
?????x??
??o?o???
?o?x????
???????x
x?o?o???
????????
x?????x?


Output

4

### Response

```cpp
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-11;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	inline long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
char in[1600][1600];
vector<char> v[1600][1600];
vector<int>g[1600];
int D[1600];
int E[1600];
int w[1600];
int dfs(int a){
	w[a]=1;
	int ret=0;
	for(int i=0;i<g[a].size();i++){
		int to=g[a][i];
		if(w[to]){
			ret++;
			continue;
		}
		ret+=dfs(to)+1;
	}
	// printf("%d: %d\n",a,ret);
	return ret;
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		scanf("%s",in[i]);
	}
	for(int i=0;i<a-1;i++){
		for(int j=0;j<a-1;j++){
			int x=i+j-(a-2);
			int y=i-j;
			v[ABS(x)][ABS(y)].push_back(in[i][j]);
			// if(in[i][j]!='?')printf("%d %d: %c\n",ABS(x),ABS(y),in[i][j]);
		}
	}
	int n=a-1;
	long long ret=1;
	for(int i=0;i<2;i++){
		int s=0;
		int N=(a-i)/2+1;
		for(int j=0;j<N;j++){
			g[j].clear();
			D[j]=E[j]=0;
			w[j]=0;
		}
		for(int j=i;j<n;j+=2){
			for(int k=(i+a)%2;j+k<n;k+=2){
				int t=-1;
				for(int l=0;l<v[j][k].size();l++){
					if(v[j][k][l]=='o'){
						if(t==1)ret=0;
						else t=0;	
					}
					if(v[j][k][l]=='x'){
						if(t==0)ret=0;
						else t=1;
					}

				}
				if(t==-1){
					s++;
					g[j/2].push_back(N-1-k/2);
					g[N-1-k/2].push_back(j/2);
					// printf("%d %d\n",j/2,N-1-k/2);
					D[j/2]++;
					D[N-1-k/2]++;
				}
				if(t==0){
					E[j/2]++;
					E[N-1-k/2]++;
				}
			}
		}
		if(N%2==0){
			ret=ret*pw(2,s)%mod;
			continue;
		}

		int F=0;
		for(int j=0;j<N;j++){
			if(D[j]==0&&E[j]%2){
				ret=0;
			}
			if(D[j])F--;
		}
		for(int j=0;j<N;j++){
			if(D[j]==0)continue;
			if(w[j])continue;
			int f=dfs(j)/2;
			F+=f+1;
		}
		ret=ret*pw(2,F)%mod;

	}
	printf("%lld\n",ret);
}
```