Farmer John에게는 $N$행 $N$열 격자 모양의 작은 밭이 있다($1 \le N \le 2000$). 모든 $1 \le i,j \le N$에 대해, 위에서 $i$번째 행의 왼쪽에서 $j$번째 칸을 $(i,j)$로 나타낸다. 그는 밭에 단옥수수와 알팔파를 심고 싶어 한다. 이를 위해 특별한 스프링클러를 몇 개 설치해야 한다.

$(I,J)$ 칸의 단옥수수 스프링클러는 왼쪽 아래에 있는 모든 칸, 즉 $I \le i$이고 $j \le J$인 $(i,j)$ 칸에 물을 뿌린다.

$(I,J)$ 칸의 알팔파 스프링클러는 오른쪽 위에 있는 모든 칸, 즉 $i \le I$이고 $J \le j$인 $(i,j)$ 칸에 물을 뿌린다.

하나 이상의 단옥수수 스프링클러로부터 물을 받는 칸에서는 단옥수수를 기를 수 있다. 하나 이상의 알팔파 스프링클러로부터 물을 받는 칸에서는 알팔파를 기를 수 있다. 하지만 두 종류 모두로부터 물을 받는 칸이나 어느 종류로부터도 물을 받지 않는 칸에서는 아무것도 기를 수 없다.

모든 칸이 비옥하도록(즉, 정확히 한 종류의 스프링클러로부터 물을 받도록) 밭에 스프링클러를 설치하는 방법의 수를 $10^9 + 7$로 나눈 나머지를 구하여 FJ를 도와라. 각 칸에는 스프링클러를 최대 하나 설치할 수 있다.

일부 칸에는 이미 털이 많은 소가 있다. 이러한 칸도 비옥할 수 있지만, 이러한 칸에는 스프링클러를 설치할 수 없다.

입력

첫 번째 줄에는 정수 $N.$ 하나가 주어진다.

각 $1\le i\le N,$에 대해, $i+1$번째 줄에는 격자의 $i$번째 행을 나타내는 길이 $N$의 문자열이 주어진다. 문자열의 각 문자는 털이 많은 소가 있는 칸을 나타내는 'W' 또는 비어 있는 칸을 나타내는 '.'이다.

출력

스프링클러를 설치하는 방법의 수를 $10^9+7.$로 나눈 나머지를 출력한다.

예제

입력 1

2
..
..

출력 1

28

참고

$(1,1)$에서 단옥수수를 기를 수 있을 때의 열네 가지 경우는 다음과 같다.

CC  .C  CA  CC  .C  CA  CA  C.  CA  C.  CC  .C  CC  .C  
CC, CC, CC, .C, .C, .C, CA, CA, .A, .A, C., C., .., ..

입력 2

4
..W.
..WW
WW..
...W

출력 2

2304

참고

이 예제는 아래에 설명된 첫 번째 서브태스크의 제한을 만족한다.

서브태스크

• 테스트 케이스 3-4에서는 $N\le 10$이며 비어 있는 칸이 최대 열 개이다.
• 테스트 케이스 5-9에서는 $N\le 200$이다.
• 테스트 케이스 10-16에는 추가 제한이 없다.

문제 작성자: Benjamin Qi