Giganotosaurus Game

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 점프가 이전보다 한 칸씩 더 건너뛰는 규칙으로 1칸 이동 또는 점프를 하며 선인장을 피해 n개 칸을 통과하는 경로의 수를 세는 문제이다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

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, but 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 quickly master this simple game, so you pose a more interesting challenge: count how many ways there are to win the game. As an example, consider the second sample case, visualized in Figure G.1.

Figure G.1: Visualization of the second sample input, for which there are three ways to win the game.

입력

The input consists of:

One line with an integer $n$ ( $1 \le n \le 10^5$ ), the length of the world.
One line with $n$ characters, each character being either '#' or '.', indicating a cactus or an empty cell, respectively.

출력

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

예제4

예제 1
입력
```
4
....
```
예상 출력
```
8
```
예제 2
입력
```
4
.#..
```
예상 출력
```
3
```
예제 3
입력
```
7
.#...##
```
예상 출력
```
1
```
예제 4
입력
```
7
..#.#.#
```
예상 출력
```
0
```