#include #include #include #include using num = std::uint_least32_t; constexpr num M = 1e9 + 7; int main() { int n; std::cin >> n; std::vector obstacle; for (int i = 0; i < n; i++) { char c; std::cin >> c; obstacle.push_back(c == '#'); } std::vector count(n+1); std::vector jump(n+1); // bad: we assume a single jump length per cell count[0] = 1; jump[0] = 2; for (int x = 0; x < n; x++) { if (!obstacle[x]) { // no jump count[x+1] += count[x]; count[x+1] %= M; jump[x+1] = std::max(jump[x+1], jump[x]); // yes jump const int y = std::min(x + jump[x], n); count[y] += count[x]; count[y] %= M; jump[y] = std::max(jump[y], jump[x] + 1); } } std::cout << count.back() << std::endl; }