기가노토사우루스 게임

면접 대비

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

요약

길이 n의 칸에서 선인장을 피해 오른쪽으로 한 칸 이동하거나, k번째 점프에서 k칸을 건너뛰는 방법의 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 배열, 문자열
정답자: 아직 제출이 없습니다

문제

나쁜 인터넷 연결 때문에 심심풀이로 웹 브라우저에서 간단한 게임을 하고 있다. 플레이어는 장애물(선인장)이 일렬로 놓인 세계를 달리는 기가노토사우루스를 조종한다. 선인장에 부딪히지 않고 세계의 끝까지 도달하면 게임에서 이긴다.

세계는 $n$ 개의 칸으로 이루어져 있으며, 각 칸은 비어 있거나 선인장을 담고 있다. 기가노토사우루스는 가장 왼쪽 칸(이 칸은 항상 비어 있다)에서 출발하여 가장 오른쪽 칸을 지나는 것이 목표다. 각 칸에서 기가노토사우루스는 오른쪽으로 한 칸 이동하거나, 일정한 수의 칸을 건너뛰며 점프할 수 있다. 첫 번째 점프는 한 칸을 건너뛴다. 이후 점프마다 직전 점프보다 한 칸씩 더 건너뛴다. 즉 $k$ 번째 점프는 정확히 $k$ 칸을 건너뛴다.

이 단순한 게임은 금방 익혔으니, 더 어려운 과제를 내겠다. 게임에서 이기는 방법이 몇 가지인지 세어 보자. 그림 G.1에 나타난 두 번째 예제를 보자. 이 경우 이기는 방법은 세 가지다.

그림 G.1: 두 번째 예제 입력의 시각화.

입력

첫째 줄에 세계의 길이를 나타내는 정수 $n$ ( $1 \le n \le 10^5$ )이 주어진다.

둘째 줄에는 $n$ 개의 문자가 주어진다. 각 문자는 선인장을 뜻하는 '#' 또는 빈 칸을 뜻하는 '.' 중 하나다.

출력

게임에서 이기는 방법의 수를 $10^9 + 7$ 로 나눈 나머지를 출력한다.

예제4

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