Xenia likes puzzles very much. She is especially fond of the puzzles that consist of domino pieces. Look at the picture that shows one of such puzzles.

<image>

A puzzle is a 3 × n table with forbidden cells (black squares) containing dominoes (colored rectangles on the picture). A puzzle is called correct if it meets the following conditions:

  * each domino occupies exactly two non-forbidden cells of the table; 
  * no two dominoes occupy the same table cell; 
  * exactly one non-forbidden cell of the table is unoccupied by any domino (it is marked by a circle in the picture). 



To solve the puzzle, you need multiple steps to transport an empty cell from the starting position to some specified position. A move is transporting a domino to the empty cell, provided that the puzzle stays correct. The horizontal dominoes can be moved only horizontally, and vertical dominoes can be moved only vertically. You can't rotate dominoes. The picture shows a probable move.

Xenia has a 3 × n table with forbidden cells and a cell marked with a circle. Also, Xenia has very many identical dominoes. Now Xenia is wondering, how many distinct correct puzzles she can make if she puts dominoes on the existing table. Also, Xenia wants the circle-marked cell to be empty in the resulting puzzle. The puzzle must contain at least one move.

Help Xenia, count the described number of puzzles. As the described number can be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

Input

The first line contains integer n (3 ≤ n ≤ 104) — the puzzle's size. Each of the following three lines contains n characters — the description of the table. The j-th character of the i-th line equals "X" if the corresponding cell is forbidden; it equals ".", if the corresponding cell is non-forbidden and "O", if the corresponding cell is marked with a circle.

It is guaranteed that exactly one cell in the table is marked with a circle. It is guaranteed that all cells of a given table having at least one common point with the marked cell is non-forbidden.

Output

Print a single number — the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

5
....X
.O...
...X.


Output

1


Input

5
.....
.O...
.....


Output

2


Input

3
...
...
..O


Output

4

Note

Two puzzles are considered distinct if there is a pair of cells that contain one domino in one puzzle and do not contain it in the other one.
// Don't place your source in a package
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*; 
 
 
 
// Please name your class Main
public class Main {
	
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    
 
    static int read() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
    static String readString() throws IOException {
        in.nextToken();
        return in.sval;
	}
	
	
	public static void main (String[] args) throws java.lang.Exception {
	    Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		//InputReader in = new InputReader(System.in);
 
		int T=1;
		
		for(int t=0;t<T;t++){
			int n=in.nextInt();
			char A[][]=new char[3][n];
			for(int i=0;i<3;i++){
				String s=in.next();
				A[i]=s.toCharArray();
			}
			
			Solution sol=new Solution();
			sol.solution(A);
		}

		out.flush();
	}
 
}
 
class Solution{
	//constant variable
	final int MAX=Integer.MAX_VALUE;
	final int MIN=Integer.MIN_VALUE;
	//Set<Integer>adjecent[];
	//////////////////////////////

	
	
	long mod=1000000007;
	char A[][];
	public void solution(char A[][]){
		this.A=A;
		int r=-1;int c=-1;
		long res=0;
		//f(1)+f(2)+f(3)+f(4)−f(1,2)−f(1,3)−f(1,4)−f(2,3)−f(2,4)−f(3,4)+f(1,2,3)+f(1,2,4)+f(1,3,4)+f(2,3,4)−f(1,2,3,4)
		
		for(int i=0;i<A.length;i++){
			for(int j=0;j<A[0].length;j++){
				if(A[i][j]=='O'){
					r=i;
					c=j;
					A[i][j]='X';
					break;
				}
			}
		}
		
		char A1[][]=copy(A);
		char A2[][]=copy(A);
		char A3[][]=copy(A);
		char A4[][]=copy(A);
		char A5[][]=copy(A);
		char A6[][]=copy(A);
		char A7[][]=copy(A);
		char A8[][]=copy(A);
		char A9[][]=copy(A);
		char A10[][]=copy(A);
		char A11[][]=copy(A);
		char A12[][]=copy(A);
		char A13[][]=copy(A);
		char A14[][]=copy(A);
		char A15[][]=copy(A);
		char A16[][]=copy(A);
		
		//f(1)
		if(check(r,c-1)&&check(r,c-2)){
			A1[r][c-1]='X';
			A1[r][c-2]='X';
			res+=solve(A1);
			//msg(res+"");
		}
		//f(2)
		if(check(r,c+1)&&check(r,c+2)){
			A2[r][c+1]='X';
			A2[r][c+2]='X';
			res+=solve(A2);
		}
		//f(3)
		if(check(r-1,c)&&check(r-2,c)){
			A3[r-1][c]='X';
			A3[r-2][c]='X';
			res+=solve(A3);
		}
		//f(4)
		if(check(r+1,c)&&check(r+2,c)){
			A4[r+1][c]='X';
			A4[r+2][c]='X';
			res+=solve(A4);
		}
		
		//f(1,2)
		if(check(r,c-1)&&check(r,c-2)&&check(r,c+1)&&check(r,c+2)){
			A5[r][c-1]='X';
			A5[r][c-2]='X';
			A5[r][c+1]='X';
			A5[r][c+2]='X';
			res-=solve(A5);
		}
		
		//f(1,3)
		if(check(r,c-1)&&check(r,c-2)&&check(r-1,c)&&check(r-2,c)){
			A6[r][c-1]='X';
			A6[r][c-2]='X';
			A6[r-1][c]='X';
			A6[r-2][c]='X';
			res-=solve(A6);
		}
		
		//f(1,4)
		if(check(r,c-1)&&check(r,c-2)&&check(r+1,c)&&check(r+2,c)){
			A10[r][c-1]='X';
			A10[r][c-2]='X';
			A10[r+1][c]='X';
			A10[r+2][c]='X';
			res-=solve(A10);
		}
		
		
		//f(2,3)
		if(check(r,c+1)&&check(r,c+2)&&check(r-1,c)&&check(r-2,c)){
			A7[r][c+1]='X';
			A7[r][c+2]='X';
			A7[r-1][c]='X';
			A7[r-2][c]='X';
			res-=solve(A7);
		}
		
		//f(2,4)
		if(check(r,c+1)&&check(r,c+2)&&check(r+1,c)&&check(r+2,c)){
			A8[r][c+1]='X';
			A8[r][c+2]='X';
			A8[r+1][c]='X';
			A8[r+2][c]='X';
			res-=solve(A8);
		}
		
		//f(3,4)
		if(check(r-1,c)&&check(r-2,c)&&check(r+1,c)&&check(r+2,c)){
			A9[r-1][c]='X';
			A9[r-1][c]='X';
			A9[r+1][c]='X';
			A9[r+2][c]='X';
			res-=solve(A9);
		}
		
		//f(1,2,3)
		if(check(r,c-1)&&check(r,c-2)&&check(r,c+1)&&check(r,c+2)&&check(r-1,c)&&check(r-2,c)){
			A11[r][c-1]='X';
			A11[r][c-2]='X';
			A11[r][c+1]='X';
			A11[r][c+2]='X';
			A11[r-1][c]='X';
			A11[r-2][c]='X';
			res+=solve(A11);
		}
		
		//f(1,2,4)
		if(check(r,c-1)&&check(r,c-2)&&check(r,c+1)&&check(r,c+2)&&check(r+1,c)&&check(r+2,c)){
			A12[r][c-1]='X';
			A12[r][c-2]='X';
			A12[r][c+1]='X';
			A12[r][c+2]='X';
			A12[r+1][c]='X';
			A12[r+2][c]='X';
			res+=solve(A12);
		}
		
		//f(1,3,4)
		if(check(r,c-1)&&check(r,c-2)&&check(r-1,c)&&check(r-2,c)&&check(r+1,c)&&check(r+2,c)){
			A13[r][c-1]='X';
			A13[r][c-2]='X';
			A13[r-1][c]='X';
			A13[r-2][c]='X';
			A13[r+1][c]='X';
			A13[r+2][c]='X';
			res+=solve(A13);
		}
		
		//f(2,3,4)
		if(check(r,c+1)&&check(r,c+2)&&check(r-1,c)&&check(r-2,c)&&check(r+1,c)&&check(r+2,c)){
			A14[r][c+1]='X';
			A14[r][c+2]='X';
			A14[r-1][c]='X';
			A14[r-2][c]='X';
			A14[r+1][c]='X';
			A14[r+2][c]='X';
			res+=solve(A14);
		}
		
		//f(1,2,3,4)
		if(check(r,c-1)&&check(r,c-2)&&check(r,c+1)&&check(r,c+2)&&check(r-1,c)&&check(r-2,c)&&check(r+1,c)&&check(r+2,c)){
			A15[r][c-1]='X';
			A15[r][c-2]='X';
			A15[r][c+1]='X';
			A15[r][c+2]='X';
			A15[r-1][c]='X';
			A15[r-2][c]='X';
			A15[r+1][c]='X';
			A15[r+2][c]='X';
			res-=solve(A15);
		}
		res%=mod;
		if(res<0)res+=mod;
		msg(res+"");

	}
	
	
	
	public long solve(char A[][]){
		//000 001 010 011 100 101 110 111
		int n=A[0].length;
		long dp[][]=new long[A[0].length][8]; 
		int first=encode(A,0);
		if(first==0){
			dp[0][0]=1;
			dp[0][3]=1;
			dp[0][6]=1;
		}
		if(first==1){
			dp[0][1]=1;
			dp[0][7]=1;
		}
		if(first==2){
			dp[0][2]=1;
		}
		if(first==3){
			dp[0][3]=1;
		}
		if(first==4){
			dp[0][4]=1;
			dp[0][7]=1;
		}
		if(first==5){
			dp[0][5]=1;
		}
		if(first==6){
			dp[0][6]=1;
		}
		if(first==7){
			dp[0][7]=1;
		}
		//msg("code "+first);
		
		for(int i=1;i<A[0].length;i++){
			int code=encode(A,i);
			if(code==0){
				dp[i][0]=dp[i-1][7];
				dp[i][1]=dp[i-1][6];
				dp[i][2]=dp[i-1][5];
				dp[i][3]=(dp[i-1][7]+dp[i-1][4])%mod;
				dp[i][4]=dp[i-1][3];
				dp[i][5]=dp[i-1][2];
				dp[i][6]=(dp[i-1][7]+dp[i-1][1])%mod;
				dp[i][7]=(dp[i-1][0]+dp[i-1][3]+dp[i-1][6])%mod;
			}
			if(code==1){
				dp[i][1]=dp[i-1][7];
				dp[i][3]=dp[i-1][5];
				dp[i][5]=dp[i-1][3];
				dp[i][7]=(dp[i-1][7]+dp[i-1][1])%mod;
				
			}
			if(code==2){//010
				dp[i][2]=dp[i-1][7];
				dp[i][3]=dp[i-1][6];
				dp[i][6]=dp[i-1][3];
				dp[i][7]=dp[i-1][2];
			}
			if(code==3){//011
				dp[i][3]=dp[i-1][7];
				dp[i][7]=dp[i-1][3];
			}
			if(code==4){//100  =>(100 101 110 111)
				dp[i][4]=dp[i-1][7];
				dp[i][5]=dp[i-1][6];
				dp[i][6]=dp[i-1][5];
				dp[i][7]=(dp[i-1][7]+dp[i-1][4])%mod;
			}
			if(code==5){//101
				dp[i][5]=dp[i-1][7];
				dp[i][7]=dp[i-1][5];
			}
			if(code==6){//110
				dp[i][6]=dp[i-1][7];
				dp[i][7]=dp[i-1][6];
			}
			if(code==7){//111
				dp[i][7]=dp[i-1][7];
			}
			
		}
		
		return (dp[n-1][7])%mod;
	}
	
	
	public int encode(char A[][],int col){
		int res=0;
		for(int i=0;i<3;i++){
			if(A[i][col]=='X'){
				res=res|(1<<i);
			}
		}
		return res;
	}

	public char[][] copy(char A[][]){
		char res[][]=new char[A.length][A[0].length];
		for(int i=0;i<A.length;i++){
			for(int j=0;j<A[0].length;j++){
				res[i][j]=A[i][j];
			}
		}
		return res;
	}

	public boolean check(int i,int j){
		if(i<0||j<0||i>=A.length||j>=A[0].length)return false;
		if(A[i][j]=='X')return false;
		return true;
	}

	
	
	
	
	
	

		
	

	
	

	
	
	

	
	public void swap(int A[],int l,int r){
		int t=A[l];
		A[l]=A[r];
		A[r]=t;
	}
	
	
	public long C(long fact[],int i,int j){ // C(20,3)=20!/(17!*3!)
		// take   a/b     where a=20!  b=17!*3!
		if(j>i)return 0;
		if(j==0)return 1;
		long mod=998244353;
		long a=fact[i];
		long b=((fact[i-j]%mod)*(fact[j]%mod))%mod;
		BigInteger B= BigInteger.valueOf(b);
		long binverse=B.modInverse(BigInteger.valueOf(mod)).longValue();
		return ((a)*(binverse%mod))%mod;
	}
	
	 
	
	//map operation
	public void put(Map<Integer,Integer>map,int i){
		if(!map.containsKey(i))map.put(i,0);
		map.put(i,map.get(i)+1);
	}
	
	public void delete(Map<Integer,Integer>map,int i){
		map.put(i,map.get(i)-1);
		if(map.get(i)==0)map.remove(i);
	}
 
 


 
	
 
 
	/*public void tarjan(int p,int r){
		if(cut)return;
		List<Integer>childs=adjecent[r];
		dis[r]=low[r]=time;
		time++;
		
		//core for tarjan
		int son=0;
		for(int c:childs){
			if(ban==c||c==p)continue;
			if(dis[c]==-1){
				son++;
				tarjan(r,c);
				low[r]=Math.min(low[r],low[c]);
				if((r==root&&son>1)||(low[c]>=dis[r]&&r!=root)){
					cut=true;
					return;
				}
			}else{
				if(c!=p){
					low[r]=Math.min(low[r],dis[c]);
				}
			}
		}
		
	}*/
	
	

	
	//helper function I would use
	public void remove(Map<Integer,Integer>map,int i){
		map.put(i,map.get(i)-1);
		if(map.get(i)==0)map.remove(i);
	}
	
	
	
	public void ascii(String s){
		for(char c:s.toCharArray()){
			System.out.print((c-'a')+" ");
		}
		msg("");
	}
	
	public int flip(int i){
		if(i==0)return 1;
		else return 0;
	}
	
	public boolean[] primes(int n){
		boolean A[]=new boolean[n+1];
		for(int i=2;i<=n;i++){
			if(A[i]==false){
				for(int j=i+i;j<=n;j+=i){
					A[j]=true;
				}
			}
		}
		return A;
	}
	
	public void msg(String s){
		System.out.println(s);
	}
	
	public void msg1(String s){
		System.out.print(s);
	}
	
	public int[] kmpPre(String p){
		int pre[]=new int[p.length()];
		int l=0,r=1;
		while(r<p.length()){
			if(p.charAt(l)==p.charAt(r)){
				pre[r]=l+1;
				l++;r++;
			}else{
				if(l==0)r++;
				else l=pre[l-1];
			}
		}
		return pre;
	}
	
	public boolean isP(String s){
		int l=0,r=s.length()-1;
		while(l<r){
			if(s.charAt(l)!=s.charAt(r))return false;
			l++;r--;
		}
		return true;
	}
	
	public int find(int nums[],int x){//union find => find method
		if(nums[x]==x)return x;
		int root=find(nums,nums[x]);
		nums[x]=root;
		return root;
	}
	

	
	public int get(int A[],int i){
		if(i<0||i>=A.length)return 0;
		return A[i];
	}
	public int[] copy1(int A[]){
		int a[]=new int[A.length];
		for(int i=0;i<a.length;i++)a[i]=A[i];
		return a;
	}
	
	
	public void print1(int A[]){
		for(long i:A)System.out.print(i+" ");
		System.out.println();
	}
	public void print2(long A[][]){
		for(int i=0;i<A.length;i++){
			for(int j=0;j<A[0].length;j++){
				System.out.print(A[i][j]+" ");
			}System.out.println();
		}
	}
	
	public int min(int a,int b){
		return Math.min(a,b);
	}
	
	
	public int[][] matrixdp(int[][] grid) {
        if(grid.length==0)return new int[][]{};
        int res[][]=new int[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                res[i][j]=grid[i][j]+get(res,i-1,j)+get(res,i,j-1)-get(res,i-1,j-1);
            }
        }
        return res;
    }
    
    public int get(int grid[][],int i,int j){
        if(i<0||j<0||i>=grid.length||j>=grid[0].length)return 0;
        return grid[i][j];
    }
	
	public int[] suffixArray(String s){
		int n=s.length();
		Suffix A[]=new Suffix[n];
		
		for(int i=0;i<n;i++){
			A[i]=new Suffix(i,s.charAt(i)-'a',0);
		}
		
		for(int i=0;i<n;i++){
			if(i==n-1){
				A[i].next=-1;
			}else{
				A[i].next=A[i+1].rank;
			}
		}
		Arrays.sort(A);
		
		for(int len=4;len<A.length*2;len<<=1){
			int in[]=new int[A.length];
			int rank=0;
			int pre=A[0].rank;
			A[0].rank=rank;
			in[A[0].index]=0;
			for(int i=1;i<A.length;i++){//rank for the first two letter
				if(A[i].rank==pre&&A[i].next==A[i-1].next){
					pre=A[i].rank;
					A[i].rank=rank;
				}else{
					pre=A[i].rank;
					A[i].rank=++rank;
				}
				in[A[i].index]=i;
			}
			
			for(int i=0;i<A.length;i++){
				int next=A[i].index+len/2;
				if(next>=A.length){
					A[i].next=-1;
				}else{
					A[i].next=A[in[next]].rank;
				}
			}
			
			
			Arrays.sort(A);
		}
		
		
		int su[]=new int[A.length];
		for(int i=0;i<su.length;i++){
			su[i]=A[i].index;
		}
		return su;
	}
	
}
 
//suffix array Struct
class Suffix implements Comparable<Suffix>{
	int index;
	int rank;
	int next;
	public Suffix(int i,int rank,int next){
		this.index=i;
		this.rank=rank;
		this.next=next;
	}
	
	@Override
	public int compareTo(Suffix other) {
		if(this.rank==other.rank){
			return this.next-other.next;
		}
		return this.rank-other.rank;
	}
	
	public String toString(){
		return this.index+"   "+this.rank+"   "+this.next+"  ";
	}
}
 
 
 
class Wrapper implements Comparable<Wrapper>{
	int spf;int cnt;
	public Wrapper(int spf,int cnt){
		this.spf=spf;
		this.cnt=cnt;
	}
		
	@Override
	public int compareTo(Wrapper other) {
		return this.spf-other.spf;
	}
}
 
 
 
    class Node{//what the range would be for that particular node
		boolean state=false;
        int l=0,r=0;
		int ll=0,rr=0;
        public Node(boolean state){
            this.state=state;
        }
    }
	
	
	
	
	class Seg1{
			int A[];
			public Seg1(int A[]){
				this.A=A;
			}
			
			public void update(int left,int right,int val,int s,int e,int id){
				if(left<0||right<0||left>right)return;
				if(left==s&&right==e){
					
					A[id]+=val;
					return;
				}
				int mid=s+(e-s)/2; //[s,mid] [mid+1,e]
				
				if(left>=mid+1){
					update(left,right,val,mid+1,e,id*2+2);
				}else if(right<=mid){
					update(left,right,val,s,mid,id*2+1);
				}else{
					update(left,mid,val,s,mid,id*2+1);
					update(mid+1,right,val,mid+1,e,id*2+2);
				}
			}
			
			public int query(int i,int add,int s,int e,int id){
				
				if(s==e&&i==s){
					return A[id]+add;
				}
				
				int mid=s+(e-s)/2; //[s,mid] [mid+1,e]
				
				if(i>=mid+1){
					return query(i,A[id]+add,mid+1,e,id*2+2);
				}else{
					return query(i,A[id]+add,s,mid,id*2+1);
				}
			}
	}
 
 
	 class MaxFlow{
		

		  public static List<Edge>[] createGraph(int nodes) {
			List<Edge>[] graph = new List[nodes];
			for (int i = 0; i < nodes; i++)
			  graph[i] = new ArrayList<>();
			return graph;
		  }

		  public static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
			graph[s].add(new Edge(t, graph[t].size(), cap));
			graph[t].add(new Edge(s, graph[s].size() - 1, 0));
		  }

		  static boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) {
			Arrays.fill(dist, -1);
			dist[src] = 0;
			int[] Q = new int[graph.length];
			int sizeQ = 0;
			Q[sizeQ++] = src;
			for (int i = 0; i < sizeQ; i++) {
			  int u = Q[i];
			  for (Edge e : graph[u]) {
				if (dist[e.t] < 0 && e.f < e.cap) {
				  dist[e.t] = dist[u] + 1;
				  Q[sizeQ++] = e.t;
				}
			  }
			}
			return dist[dest] >= 0;
		  }

		  static int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
			if (u == dest)
			  return f;
			for (; ptr[u] < graph[u].size(); ++ptr[u]) {
			  Edge e = graph[u].get(ptr[u]);
			  if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
				int df = dinicDfs(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
				if (df > 0) {
				  e.f += df;
				  graph[e.t].get(e.rev).f -= df;
				  return df;
				}
			  }
			}
			return 0;
		  }

		  public static int maxFlow(List<Edge>[] graph, int src, int dest) {
			int flow = 0;
			int[] dist = new int[graph.length];
			while (dinicBfs(graph, src, dest, dist)) {
			  int[] ptr = new int[graph.length];
			  while (true) {
				int df = dinicDfs(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
				if (df == 0)
				  break;
				flow += df;
			  }
			}
			return flow;
		  }
		 
	 }
	 
	 	 class Edge {
			int t, rev, cap, f;

			public Edge(int t, int rev, int cap) {
			  this.t = t;
			  this.rev = rev;
			  this.cap = cap;
			}
		  }
 