分数: 366 分
问题陈述
高桥正在尝试爬楼梯 N 步骤。
每个步骤的编号从 1 to N 从底部开始。高桥从地上开始(步 0)并旨在准确达到步骤 N.
高桥一招就能爬 1 步骤, 2 步骤,或 3 向上迈出一步。也就是说,如果他现在在台阶上 k,他可以直接移动到步骤 k+1,步骤 k+2,或步骤 k+3 (但是,他无法超越步骤 N)。移动时,他只停在目标台阶上,不会停在中间的任何台阶上。
一些台阶正在被涂漆,高桥无法选择涂漆的台阶作为目的地(他无法在其上停留)。然而,可以跳过中间的彩绘台阶。步骤 0 (地面)没有被涂漆,并且可以随时停在上面。
每个步骤是否正在绘制由字符串给出 S 长度 N。如果 i- 第一个字符 (1 \leq i \leq N) 的 S is .,然后步骤 i 尚未绘制,可以停止;如果是的话 #,然后步骤 i 正在涂漆,无法停止。
求高桥从台阶向上爬的方式数 0 准确一步 N,模数 10^9 + 7.
这里,如果台阶顺序停止(包括台阶),则两种攀登方式被认为是不同的 N)是不同的。
约束
- 1 \leq N \leq 10^5
- N 是一个整数
- S 是一个长度为的字符串 N 仅包含
.和# - 的 N- 第一个字符 S is
.(保证该步骤 N 未绘制)
输入
N S
- 第一行包含一个整数 N 代表步数。
- 第二行包含一个字符串 S 长度 N 代表每个步骤的状态。的 i- 第一个字符 S 对应步骤的状态 i:
.表示它没有被涂漆并且可以停止,#表示正在涂漆且无法停止。请注意有关步骤的信息 0 (地面)不包含在 S,以及步骤 0 始终可以停止。
输出
一行输出高桥从台阶可以爬升的总方式 0 到步骤 N,模数 10^9 + 7。如果没有办法到达步骤 N,输出 0.
示例输入 1
5 ..#..
示例输出 1
5
示例输入 2
10 ..#...#...
示例输出 2
34
示例输入 3
20 #.#.............#...
示例输出 3
5849