← 返回题目列表

AtCoder · awc0070_c

C. 爬楼梯的方法

中文机器翻译题面 查看原题

分数: 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