#include #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 == '#'); } const int maxJumpCount = std::sqrt(n*2); // proof by Desmos (you can also simply use e.g. 500) std::vector> dp(n+1, std::vector(maxJumpCount + 1)); dp[0][0] = 1; for (int x = 0; x < n; x++) { if (!obstacle[x]) { for (int j = 0; j < maxJumpCount; j++) { // no jump dp[x+1][j] += dp[x][j]; dp[x+1][j] %= M; // yes jump const int y = std::min(x+j+2, n); dp[y][j+1] += dp[x][j]; dp[y][j+1] %= M; } } } num total = 0; for (const num a : dp.back()) total = (total + a) % M; std::cout << total << std::endl; }