#include #include #include #include using mint = atcoder::modint998244353; int main() { std::string N; std::cin >> N; // dp[0] = number of occurrences without 8 // dp[1] = number of occurrences with 8 std::pair dp; bool seen_eight = false; for (int i = 0; i < N.size(); i++) { std::pair ndp{dp.first * 9, dp.first + dp.second * 10}; mint num_wo = 0, num_with = 0; if (N[i] == '9') { num_wo = 8; num_with = 1; } else { num_wo = N[i] - '0'; } if (seen_eight) { ndp.second += num_wo + num_with; } else { ndp.first += num_wo; ndp.second += num_with; } seen_eight |= N[i] == '8'; dp = std::move(ndp); } if (seen_eight) dp.second++; std::cout << dp.second.val() << std::endl; }