#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, std::vector(maxJumpCount + 1)); dp[0][0] = 1; num total = 0; for (int x = 1; x <= n*2; x++) { if (x >= n || !obstacle[x]) { for (int j = 0; j <= maxJumpCount; j++) { num v = 0; // no jump if (x-1 < n) v += dp[x-1][j]; // yes jump const int y = x - j - 1; if (j && 0 <= y && y < n) v += dp[y][j-1]; if (x < n) dp[x][j] = v % M; else total = (total + v) % M; } } } std::cout << total << std::endl; }