# 6 - Le sprint final

Ca y est, vous êtes le dernier survivant !!

Pour définitivement survivre et remporter la Bataille, il faut vous mettre à l'abri, et la **zone sécurisée** rétrécit dangereusement.

La carte est représentée en 1 dimension, et se compose de zones sécurisées (`.`) et de zones dangereuses (`#`).

Chaque minute, une zone sécurisée de la carte devient dangereuse. Seule une zone sécurisée touchant une zone dangereuse peut devenir dangereuse.

Par exemple, la carte `.#..` peut devenir à la minute suivante `##..` ou `.##.`, mais pas `.#.#`.

Afin de survivre et enfin remporter la Bataille, écrivez une fonction qui à partir de la carte actuelle, retourne le nombre de façons qu'il y a de complètement remplir la carte de zones dangereuses.


## Entrée

La carte est représentée en 1 dimension, et est découpée en zones : `#` est une zone dangereuse, `.` est une zone sécurisée. Il y a moins de 1000 zones par carte.

L'entrée est constituée de 20 testcases (tout en bas de ce fichier), chaque testcase comporte un entier en première ligne qui représente la taille de la carte, et en deuxième ligne la carte.

## Sortie

Vous devez retourner un entier par test case représentant le nombre de façons qu'il y a de complètement remplir la carte de zones dangereuses.

Cet entier doit être retourné **modulo 10^9 + 7**

Envoyez par email à contact@h25.io les résultats des tests cases qui sont affichés plus bas, un entier par ligne, ainsi que votre code en pièce jointe.

## Tests d'exemple

### **1**
**Entrée**
```python
.#..
```
**Sortie**
`3`
Explication :
```
.#.. - ##.. - ###. - ####
     \
	   .##. - ###. - ####
			\
			  .### - ####
```

### **2**
**Entrée**
```python
#...
```
**Sortie**
`1`


### **3**
**Entrée**
```python
#...##...
```
**Sortie**
`80`





# 6 - The final sprint

That's it, you're the last survivor!!

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**.

Send your answers and source code by email at contact@h25.io, one integer per line.

## Sample tests

### **1**
**Input**
```python
.#..
```
**Output**
`3`
Explanation:
```
.#.. - ##.. - ###. - ####
     \
	   .##. - ###. - ####
			\
			  .### - ####
```

### **2**
**Input**
```python
#...
```
**Output**
`1`


### **3**
**Input**
```python
#...##...
```
**Output**
`80`




=================================================================

# TESTCASES

44
#########################...................
12
....##......
38
#.......##########....#########..###..
44
#.....####.........................#........
24
################...##...
43
##........##########....#######......######
37
#.#.##.#.#.##.##.....#.#.####.#.#....
10
####..#.#.
37
####......###...........#####......##
28
......########..##.....###..
847
##...#....#.#.##.#.....##.###....#.#.#.#.#..##.####.#..#.#......#####...##.#####..##.###....####.###....#.#...#.####..####.#.#.#.#.#..##.......#..####..#.#......#.####..###..#.#####.####.##....#######.##...#.###..##...#.#.#...#.#.#...#.##......###.#.###.#.#.#...#.....##......##.....####...###..###...##...###....#.###.####....#..##.#.##...#.#.##...##...#######.####.......###....#...#.#.#####...###.#.#..#####.##.###.###....##.#.##.##.#..#.##..#.#....###.#...#.##.....#.##..##.##.##......#.#.#..#.##.###.#####....###.#####..#.#.#.....#...#.#.###..##..##..######..#.###.#.#.#....#......#..###..##....#.##...##.##..##..##.#....##.##........#####.##.#.#.#####.##.....##.#...#...#.##.##..##..#.#..#.###.####..##.####..###.#.###..##....##.#..#.##.#.####.#.#.#.#..#.#..###.#..#..###....#...#.....#.#..#.#..###.#.#..#..##.....#..#..###.#..##..####.##..#
667
..#.########################.#....#############...........#...........####################....############..###.........##......#..#######.......###..#..............###......###....#...........###........##################.###......###########.###..###..##...###.....#####..#.............#.........#########..........####...##.########.....##..####.....###....####..#######.###......###...#....................###....................##.######..........##.##################....#..#..##########..###################.#.............##########..#######....#....#########..####........#..#.......#...#..###..........###.......###########....#####..........#.##......######
990
#.#####..#.##.##..##.#######..##....#.#....#######..#.#.###...#...#...######.##..........#..##.....#..###.#..#....###.....#######..#..#..#......#............######.###.####.##.##.#######...###.###..#..######.######......##.###.##....#.##..#######..###......###.##.###..###..###...#########.############....####..###..####.....###......####..##...#..###......#########...#..#................#....####..####..##.###...##......##...#...............#....########......##.##.##.#..###...#...#...####.#.....####......#########.........###......##...###...#..##............###..#####.####..#.###..####.####.#.#..##...###.##....#....#........#..#.#.#......#.#.###...##.#...............#...#.............##......##...#...###.####....##.#.###..##......##...###..........######........######...###.....#...#...#..######..##.#.#.....#...###..#...##.######.###.###.####.#..###.#######.....##....####....#.####...#......#####.....#.##....#.#...####...#.....#......####.###...#.......####........#.#.####.
745
...#.#.###......#######....##.......####..###..###.....##...#....#....#........#####..##########.#.#######....#.........##############.####....##..........#....#####.....##...###.........#....#############.......########...######.###.....##########....#####....................##....####..####........######..............##...........####.#....###########............#............#####################...##.....#.....#........##..........###.#....###########.####....######.#####...#######...#...#######..############.....########......####.#.#.#...####...##.#.....#######.......####.......##..########.###....#####.......#####.......###..##.#######....#.#.......##.............##......###....###..........##..........########.#..#####.##.....##
827
#############....######................######....###.....#..######....##..........##.....###########...##############....#..#.........##...........#########.........#####..............###############..................######.#..##...####..#.#.....#########...######..################.....###................###........#####........################################......###.######..######....###..........######..####..#####.##############........###.########..###...#.######...#####.######.##................#...##..#####.################...####.......##########................#####......#############.#######...................#########.........###....#############...########.#.#########..########....###.########...#.....#...........#...##..#######.....#........##.....#...##..#####.#########..###...###########...........##
761
#######...###.......####.............##################.......................###############.######...............###...##############...###..........###############...#########.#######..###........#####.......####################.............#####....####...#######.....#######.....######.....##.........#####..###########.......#.####......##########............########........###################........######........................################...........#..###...........#...................#####...###..........#################.....######.########........##############################............###..######........#######............######.....###########......#..............................###################...#######..#............##......##
598
#.#.#.#######.......#.###......########.....#......##################...#.....########...........##.....###########.............#####...###.##############.......##########..####.....####......###..#........###...####...#####....##########...........##..######..............##........############.....###.......#...#########.#########......##.########...#....##########.....####........########......#########............##........##########....##########...###.........##.........#............######..#####.......#....###..#########...##################...................###..........##.##........
823
###........########.#.........###############....#..##......#######..########...######...##########...#.##.###.#...######....#.....##....#...########.....################...##......####..############...###....####.#.......#########.#.................#####...#####...######.##.#.######..#####.#..#...................#...########.#####...##..#####.########...###...###...##...#........###..#.#######.###.....................#.####..#........#..#..#####..#.####...###..#...#.....#.........#######..#.......#######....##......##............######........................#.##..###.....####.....#########.....#########....................##..####.......########.###########.......#####..####......######...##.#..########.....####.............#########.#...####...###.........####.............########......##..####.....##########
700
...#####.......##########..###########....#..#####.............#########..#######....###############.................###...#####################.......######...#####.....#....############........#######...............###................#########....######################..##############......................................................###..............####..######......###########.####...######...........###########.###################........####...................##########################....########.........#################################.######.............###..#############################...#####...........######......#################.###############.........######.......#....#
567
#.....##.#################........##.......#....##.#####.##..##................##############.###...#.###########.##.....##....#....#.######..###...........##.#######...#########.######...###.......##....######..............##.##########....#..#################.##..................#########.###.............####....#...##.....#....###.###...........###.#######.....#...#..##..............##..###.#....##..##...#...####..########...#......##.....#####.##########....#######.......#....#..#..........#####...............#.#..#.....#####.##.#######....##.........###...