A982.Sprinklers 2 Return of the Alfalfa

普及/提高-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Farmer John has a small field in the shape of an NN by NN grid (1N20001 \le N \le 2000) where the jj-th square from the left of the ii-th row from the top is
denoted by (i,j)(i,j) for all 1i,jN1 \le i,j \le N. He is interested in planting
sweet corn and alfalfa in his field. To do so, he needs to install some
special sprinklers.
A sweet corn sprinkler in square (I,J)(I,J) will sprinkle all squares to the
bottom-left: i.e. (i,j)(i,j) with IiI \le i and jJj \le J.
An alfalfa sprinkler in square (I,J)(I,J) will sprinkle all squares to the top-
right: i.e. (i,j)(i,j) with iIi \le I and JjJ \le j.
A square sprinkled by one or multiple sweet corn sprinklers can grow sweet
corn; a square sprinkled by one or multiple alfalfa sprinklers can grow
alfalfa. But a square sprinkled by both types of sprinklers (or neither type)
can grow nothing.
Help FJ determine the number of ways (modulo 109+710^9 + 7) to install sprinklers
in his field, at most one per square, so that every square is fertile (i.e.,
sprinkled by exactly one type of sprinkler).
Some of the squares are already occupied by woolly cows; this doesn't prevent
these squares from being fertile, but no sprinklers can be installed in such
squares.

输入格式

The first line contains a single integer N.N.
For each 1iN,1\le i\le N, the i+1i+1-st line contains a string of length NN
denoting the ii-th row of the grid. Each character of the string is one of
'W' (indicating a square occupied by a woolly cow), or '.' (unoccupied).

输出格式

Output the remainder when the number of ways to install sprinklers is divided
by 109+7.10^9+7.

输入输出样例

  • 输入#1

    2
    ..
    ..
    

    输出#1

    28
    

说明/提示

Here are all fourteen possibilities when sweet corn can grow at (1,1)(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., .., ..

首页