/
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は N 段の階段を登ろうとしています。
各段には下から順に 1 から N の番号が付けられています。高橋君は地面(0 段目)からスタートし、ちょうど N 段目に到達することを目指します。
高橋君は1回の移動で 1 段、2 段、または 3 段上に登ることができます。すなわち、現在 k 段目にいるとき、k+1 段目、k+2 段目、k+3 段目のいずれかへ直接移動できます(ただし N 段目を超える移動はできません)。このとき、移動先の段にのみ止まり、間にある段には止まりません。
一部の段は塗装中であり、塗装中の段を移動先に選ぶことはできません(止まることができません)。ただし、塗装中の段を間に挟んで飛び越える移動は可能です。0 段目(地面)は塗装中ではなく、常に止まることができます。
各段が塗装中かどうかは長さ N の文字列 S で与えられます。S の i 文字目(1 \leq i \leq N)が . のとき i 段目は塗装中でなく止まることができ、# のとき i 段目は塗装中で止まることができません。
高橋君が 0 段目からちょうど N 段目に到達するまでの登り方が何通りあるか、10^9 + 7 で割った余りを求めてください。
ここで、2つの登り方が異なるとは、移動先として止まった段の列(N 段目を含む)が異なることを指します。
制約
- 1 \leq N \leq 10^5
- N は整数
- S は
.と#のみからなる長さ N の文字列 - S の N 文字目は
.である(N 段目は塗装中でないことが保証される)
入力
N S
- 1 行目には、階段の段数を表す整数 N が与えられる。
- 2 行目には、各段の状態を表す長さ N の文字列 S が与えられる。S の i 文字目は i 段目の状態に対応し、
.なら塗装中でなく止まることができ、#なら塗装中で止まることができない。なお、0 段目(地面)の情報は S に含まれず、0 段目は常に止まることができる。
出力
高橋君が 0 段目から N 段目に到達するための登り方の総数を 10^9 + 7 で割った余りを 1 行で出力せよ。到達する方法が存在しない場合は 0 を出力せよ。
入力例 1
5 ..#..
出力例 1
5
入力例 2
10 ..#...#...
出力例 2
34
入力例 3
20 #.#.............#...
出力例 3
5849
Score : 366 pts
Problem Statement
Takahashi is trying to climb a staircase with N steps.
Each step is numbered from 1 to N from the bottom. Takahashi starts from the ground (step 0) and aims to reach exactly step N.
In one move, Takahashi can climb 1 step, 2 steps, or 3 steps upward. That is, if he is currently on step k, he can move directly to step k+1, step k+2, or step k+3 (however, he cannot move beyond step N). When moving, he only stops on the destination step and does not stop on any steps in between.
Some steps are being painted, and Takahashi cannot choose a painted step as a destination (he cannot stop on it). However, it is possible to jump over a painted step that lies in between. Step 0 (the ground) is not being painted and can always be stopped on.
Whether each step is being painted is given by a string S of length N. If the i-th character (1 \leq i \leq N) of S is ., then step i is not being painted and can be stopped on; if it is #, then step i is being painted and cannot be stopped on.
Find the number of ways Takahashi can climb from step 0 to exactly step N, modulo 10^9 + 7.
Here, two ways of climbing are considered different if the sequences of steps stopped on (including step N) are different.
Constraints
- 1 \leq N \leq 10^5
- N is an integer
- S is a string of length N consisting only of
.and# - The N-th character of S is
.(it is guaranteed that step N is not being painted)
Input
N S
- The first line contains an integer N representing the number of steps.
- The second line contains a string S of length N representing the state of each step. The i-th character of S corresponds to the state of step i:
.means it is not being painted and can be stopped on,#means it is being painted and cannot be stopped on. Note that the information about step 0 (the ground) is not included in S, and step 0 can always be stopped on.
Output
Output in one line the total number of ways Takahashi can climb from step 0 to step N, modulo 10^9 + 7. If there is no way to reach step N, output 0.
Sample Input 1
5 ..#..
Sample Output 1
5
Sample Input 2
10 ..#...#...
Sample Output 2
34
Sample Input 3
20 #.#.............#...
Sample Output 3
5849