스프링클러 2: 알팔파의 귀환

농부 존은 \(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\)로 나눈 나머지로 구하여 농부 존을 도와주자.

일부 칸은 이미 털북숭이 소들이 차지하고 있다. 그렇다고 그 칸이 비옥해지지 못하는 것은 아니지만, 그런 칸에는 스프링클러를 설치할 수 없다.

문제 제공: Benjamin Qi

배점

• 테스트 케이스 3-4는 \(N\le 10\)을 만족하며 비어 있는 칸이 많아야 열 개이다.
• 테스트 케이스 5-9는 \(N\le 200\)을 만족한다.
• 테스트 케이스 10-16은 추가 제약이 없다.

문제 제공: Benjamin Qi

첫째 줄에 정수 \(N\)이 하나 주어진다.

각 \(1\le i\le N\)에 대해, \(i+1\)번째 줄에 격자의 \(i\)번째 행을 나타내는 길이 \(N\)의 문자열이 주어진다. 문자열의 각 문자는 'W'(털북숭이 소가 차지한 칸) 또는 '.'(비어 있는 칸) 중 하나이다.

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

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Platinum