Giganotosaurus Game

Interview

Time limit1sMemory limit1024 MB

Summary

Count the ways to cross a row of n cells with cactus obstacles, moving one cell right or jumping over k cells on the kth jump, modulo 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, Array, String
Solved: No attempts yet

Statement

Suffering from a poor internet connection, you are playing a casual game in your web browser to pass the time. You, the player, control a Giganotosaurus that is running through a linear world with obstacles (cactuses). You win the game if you reach the end of the world without hitting any cactuses.

The world consists of $n$ cells, which can either be empty or contain a cactus. You start at the leftmost cell (which is always empty) and the goal is to get past the rightmost cell. At each cell, the Giganotosaurus can either move one position to the right, or jump over some fixed number of cells. For the first jump, you skip one cell. With each subsequent jump, you skip one additional cell compared to the previous jump. That is, the $k$ th jump skips exactly $k$ cells.

You master this simple game quickly, so we pose a harder challenge: count how many ways there are to win the game. Consider the second sample case, shown in Figure G.1. There are three ways to win it.

Figure G.1: Visualization of the second sample input.

Input

The first line contains an integer $n$ ( $1 \le n \le 10^5$ ), the length of the world.

The second line contains $n$ characters, each one either '#' (a cactus) or '.' (an empty cell).

Output

Output the number of ways to win the game, modulo $10^9 + 7$ .

Examples4

Example 1
Input
```
4
....
```
Expected output
```
8
```
Example 2
Input
```
4
.#..
```
Expected output
```
3
```
Example 3
Input
```
7
.#...##
```
Expected output
```
1
```
Example 4
Input
```
7
..#.#.#
```
Expected output
```
0
```