dada

To definitely survive and win the Battle, you have to take cover, and the **safe zone** is shrinking dangerously.

The map is represented in 1 dimension, and is composed of safe areas (`.`) and dangerous areas (`#`).

Every minute, a secure area of the map becomes dangerous. Only a safe area touching a danger zone can become dangerous.

For example, the `.#..` map may become `##..` or `.##.` one minute later, but not `.#.#`.

In order to survive and finally win the Battle, write a function that, starting with the current map, returns the number of ways to completely turn the map dangerous.


## Input

The map `grid` is represented in 1 dimension, and is divided into zones: `#` is a dangerous zone, `.` is a secure zone. There are less than 1000 zones per map.

The input is a made of 20 testcases (at the bottom of this file), each testcase has the size of the map as its first line and the map as its second line.

## Output

You must print one integer per test case representing the number of ways there are to completely turn the map dangerous.

This integer must be returned **modulo 10^9 + 7**.