#line 1 "a.cpp" #line 1 "a.cpp" #include using namespace std; using std::cout; using std::cin; using std::endl; using ll=long long; using ld=long double; const ll ILL=2167167167167167167; const int INF=2100000000; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template using _pq = priority_queue, greater>; template ll LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template ll UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;} template bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} bool yneos(bool a,bool upp=0){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} template void vec_out(vector &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;} template bool inside(T l,T x,T r){return l<=x&&x using mint = atcoder::modint998244353; #line 2 "/Users/Shared/po167_library/fps/FPS_pow.hpp" #line 4 "/Users/Shared/po167_library/fps/FPS_pow.hpp" #include #line 4 "/Users/Shared/po167_library/fps/FPS_cyclic_convolution.hpp" namespace po167{ // |f| = |g| = 2 ^ n template std::vector FPS_cyclic_convolution(std::vector f, std::vector g){ atcoder::internal::butterfly(f); atcoder::internal::butterfly(g); for (int i = 0; i < (int)f.size(); i++) f[i] *= g[i]; atcoder::internal::butterfly_inv(f); T iz = (T)(1) / (T)(f.size()); for (int i = 0; i < (int)f.size(); i++) f[i] *= iz; return f; } } #line 3 "/Users/Shared/po167_library/fps/FPS_differetial.hpp" namespace po167{ // return f' template std::vector FPS_differential(std::vector f){ if (f.empty()) return f; for (int i = 0; i < (int)f.size() - 1; i++){ f[i] = f[i + 1] * (T)(i + 1); } f.pop_back(); return f; } } #line 3 "/Users/Shared/po167_library/fps/FPS_integral.hpp" namespace po167{ template std::vector FPS_integral(std::vector f){ if (f.empty()) return f; std::vector num_inv((int)f.size() + 1); num_inv[0] = 1; num_inv[1] = 1; auto m = T::mod(); for (int i = 2; i <= (int)f.size(); i++){ num_inv[i] = (0 - num_inv[m % i]) * (T)(m / i); } f.reserve((int)f.size() + 1); f.push_back(0); for (int i = (int)f.size() - 1; i > 0; i--){ f[i] = f[i - 1] * num_inv[i]; } f[0] = 0; return f; } } #line 4 "/Users/Shared/po167_library/fps/FPS_inv.hpp" namespace po167{ // return 1 / f template std::vector FPS_inv(std::vector f, int len = -1){ if (len == -1) len = f.size(); assert(f[0] != 0); std::vector g = {1 / f[0]}; int s = 1; while(s < len){ // g = 2g_s - f(g_s)^2 (mod x ^ (2 * s)) // g = g - (fg - 1)g // (fg - 1) = 0 (mod x ^ (s)) std::vector n_g(s * 2, 0); std::vector f_s(s * 2, 0); g.resize(s * 2); for (int i = 0; i < s * 2; i++){ if (int(f.size()) > i) f_s[i] = f[i]; n_g[i] = g[i]; } atcoder::internal::butterfly(g); atcoder::internal::butterfly(f_s); for (int i = 0; i < s * 2; i++){ f_s[i] *= g[i]; } atcoder::internal::butterfly_inv(f_s); T iz = 1 / (T)(s * 2); for (int i = s; i < s * 2; i++){ f_s[i] *= iz; } for (int i = 0; i < s; i++){ f_s[i] = 0; } atcoder::internal::butterfly(f_s); for (int i = 0; i < s * 2; i++){ f_s[i] *= g[i]; } atcoder::internal::butterfly_inv(f_s); for (int i = s; i < s * 2; i++){ n_g[i] -= f_s[i] * iz; } std::swap(n_g, g); s *= 2; } g.resize(len); return g; } } #line 8 "/Users/Shared/po167_library/fps/FPS_exp.hpp" namespace po167{ template std::vector FPS_exp(std::vector f, int len = -1){ if (len == -1) len = f.size(); if (len == 0) return {}; if (len == 1) return {T(1)}; assert(!f.empty() && f[0] == 0); int s = 1; // simple std::vector g = {T(1)}; g.reserve(len * 2); while (s < len){ // g' / g // A * B std::vector A = g, B = g; A = FPS_differential(A); B = FPS_inv(B, 2 * s); A.resize(2 * s); A = FPS_cyclic_convolution(A, B); A.pop_back(); A = FPS_integral(A); for (int i = 0; i < s; i++) A[i] = 0; for (int i = s; i < s * 2; i++) A[i] = (i < (int)f.size() ? f[i] : 0) - A[i]; // g_hat = g (1 - g + f) // g += B = g * A g.resize(2 * s); B = FPS_cyclic_convolution(A, g); for (int i = s; i < s * 2; i++) g[i] = B[i]; s *= 2; } g.resize(len); return g; } } #line 5 "/Users/Shared/po167_library/fps/FPS_log.hpp" namespace po167{ template std::vector FPS_log(std::vector f, int len = -1){ if (len == -1) len = f.size(); if (len == 0) return {}; if (len == 1) return {T(0)}; assert(!f.empty() && f[0] == 1); std::vector res = atcoder::convolution(FPS_differential(f), FPS_inv(f, len)); res.resize(len - 1); return FPS_integral(res); } } #line 8 "/Users/Shared/po167_library/fps/FPS_pow.hpp" namespace po167{ template std::vector FPS_pow(std::vector f,long long M, int len = -1){ if (len == -1) len = f.size(); std::vector res(len, 0); if (M == 0){ res[0] = 1; return res; } for (int i = 0; i < (int)f.size(); i++){ if (f[i] == 0) continue; if (i > (len - 1) / M) break; std::vector g((int)f.size() - i); T v = (T)(1) / (T)(f[i]); for (int j = i; j < (int)f.size(); j++){ g[j - i] = f[j] * v; } long long zero = i * M; if (i) len -= i * M; g = FPS_log(g, len); for (T &x : g) x *= M; g = FPS_exp(g, len); v = (T)(1) / v; T c = 1; while (M){ if (M & 1) c = c * v; v = v * v; M >>= 1; } for (int i = 0; i < len; i++) res[i + zero] = g[i] * c; return res; } return res; } } #line 33 "a.cpp" void solve(); // CYAN / FREDERIC int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; rep(i, 0, t) solve(); } void solve(){ int N, H; cin >> N >> H; vector base(2, vector(N)); vector inv(6); rep(i, 1, 6) inv[i] = (mint)(1) / (mint)(i); vector to(3, vector(3)); to[0][0] = inv[2]; to[0][1] = inv[2]; to[1][0] = inv[3]; to[1][1] = inv[3]; to[1][2] = inv[3]; to[2][1] = inv[3] * 2; to[2][2] = inv[3]; rep(i, 0, 2){ vector dp(3); if (i == 0) dp[0] = 1; else dp[1] = 2, dp[2] = 1; rep(j, 0, N - 1){ vector n_dp(3); rep(n, 0, 3) rep(m, 0, 3) n_dp[m] += dp[n] * to[n][m]; swap(n_dp, dp); for (int k = 0; k < 3; k += 3){ base[i][j + 1] += dp[k]; dp[k] = 0; } } } vector f(N), g = base[0]; rep(i, 0, 2){ if (i == 0) f[0] += inv[5] * 2; else rep(j, 0, N) f[j] += base[i][j] * inv[5]; } auto gp = po167::FPS_pow(g, N - H); mint ans = 1, sum = 0; rep(i, 0, N){ sum += gp[i]; ans -= sum * f[N - 1 - i]; } cout << ans.val() << "\n"; }