// last update: 2024/09/19

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define fq(i,a,b) for (int i = (a); i <= (b); i++)
#define fnq(i,a,b) for (int i = (a); i < (b); i++)
#define nfq(i,a,b) for (int i = (a); i >= (b); i--)
#define nfnq(i,a,b) for (int i = (a); i > (b); i--)
#define fqs(i,a,b,c) for (int i = (a); i <= (b); i += (c))
#define fnqs(i,a,b,c) for (int i = (a); i < (b); i += (c))
#define nfqs(i,a,b,c) for (int i = (a); i >= (b); i -= (c))
#define nfnqs(i,a,b,c) for (int i = (a); i > (b); i -= (c))
#define elif else if
#define LAY
//#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define EBUG
#endif
#ifdef EBUG
//#undef EBUG
#endif
#ifdef EBUG
#define DEBUG if (1)
#define NDEBUG if (0)
#else
#define DEBUG if (0)
#define NDEBUG if (1)
#endif
#define McasesT int T = d; while (T--)
#define Mcases(T) int T = d; while (T--)
#define fi first
#define se second
#define pb push_back
#define pii pair <int, int>
#define db double
#define all(v) v.begin (), v.end ()
#define vi vector <int>
using namespace std;

#define int ll
typedef long long ll;
typedef unsigned uint;

//#define FileIO

#if !defined(LAY) || defined(FileIO)
const string FileIOName = "1";
int FILEIO (string IN, string OUT) {
    try {
        freopen ((FileIOName + IN).c_str (), "r", stdin);
        freopen ((FileIOName + OUT).c_str (), "w", stdout);
        return 0;
    } catch (int) {
        return -1;
    }
}
int freFILEIO = FILEIO (".in", ".out");
#endif

inline int rd () {
	int f = 1;
	char ch = getchar ();
	while (!isdigit (ch)) (ch == '-' ? (f = -1) : 0), ch = getchar ();
	int num = 0;
	while (isdigit (ch)) num = num * 10 + ch - '0', ch = getchar ();
	return num * f;
}
#define d rd ()

inline int rd (const int modp) {
	int f = 1;
	char ch = getchar ();
	while (!isdigit (ch)) (ch == '-' ? (f = -1) : 0), ch = getchar ();
	int num = 0;
	while (isdigit (ch)) num = (num * 10 + ch - '0') % modp, ch = getchar ();
	return (num * f % modp + modp) % modp;
}

namespace lay {
	struct Edge {
		int v, nxt;
		Edge () {}
		Edge (int _v, int _nxt) {v = _v, nxt = _nxt;}
	};
	template <int VERTEXES, int EDGES, int initecnt = 0>
	struct Graph {
		Edge edge[EDGES];
		int head[VERTEXES], ecnt;
		void addedge (int u, int v) {edge[++ecnt] = Edge (v, head[u]); head[u] = ecnt;}
		void addEdge (int u, int v) {addedge (u, v), addedge (v, u);}
		void init () {memset (head, 0, sizeof head); ecnt = initecnt;}
		Graph () {init ();}
	};
	template <typename WT>
	struct EdgeW {
		int v, nxt; WT w;
		EdgeW () {}
		EdgeW (int _v, WT _w, int _nxt) {v = _v, w = _w, nxt = _nxt;}
	};
	template <int VERTEXES, int EDGES, typename WT = int, int initecnt = 0>
	struct GraphW {
		EdgeW <WT> edge[EDGES];
		int head[VERTEXES], ecnt;
		void addedge (int u, int v, WT w) {edge[++ecnt] = EdgeW <WT> (v, w, head[u]); head[u] = ecnt;}
		void addEdge (int u, int v, WT w) {addedge (u, v, w), addedge (v, u, w);}
		void init () {memset (head, 0, sizeof head); ecnt = initecnt;}
		GraphW () {init ();}
	};
	template <int VERTEXES, int EDGES, typename WT = int>
	struct GraphFW : public GraphW <VERTEXES, EDGES, WT, 1> {
		void addEdge (int u, int v, WT w) {this -> addedge (u, v, w), this -> addedge (v, u, 0);}
	};
	template <typename WT1, typename WT2>
	struct EdgeWC {
		int v, nxt; WT1 w; WT2 c;
		EdgeWC () {}
		EdgeWC (int _v, WT1 _w, WT2 _c, int _nxt) {v = _v, w = _w, c = _c, nxt = _nxt;}
	};
	template <int VERTEXES, int EDGES, typename WT1 = int, typename WT2 = int, int initecnt = 0>
	struct GraphWC {
		EdgeWC <WT1, WT2> edge[EDGES];
		int head[VERTEXES], ecnt;
		void addedge (int u, int v, WT1 w, WT2 c) {edge[++ecnt] = EdgeWC <WT1, WT2> (v, w, c, head[u]); head[u] = ecnt;}
		void addEdge (int u, int v, WT1 w, WT2 c) {addedge (u, v, w, c), addedge (v, u, w, c);}
		void init () {memset (head, 0, sizeof head); ecnt = initecnt;}
		GraphWC () {init ();}
	};
	template <int VERTEXES, int EDGES, typename WT1 = int, typename WT2 = int>
	struct GraphFWC : public GraphWC <VERTEXES, EDGES, WT1, WT2, 1> {
		void addEdge (int u, int v, WT1 w, WT2 c) {this -> addedge (u, v, w, c), this -> addedge (v, u, 0, -c);}
	};
	#define fe(G,u) for (int i = G.head[u], v; v = G.edge[i].v, i; i = G.edge[i].nxt)
	#define feh(G,u,h) for (int i = h[u], v; v = G.edge[i].v, i; i = G.edge[i].nxt)
	#define few(G,u) for (auto [i, v, w] = make_tuple (G.head[u], int(), int()); v = G.edge[i].v, w = G.edge[i].w, i; i = G.edge[i].nxt)
	#define fewt(G,u,T) for (auto [i, v, w] = make_tuple (G.head[u], int(), T()); v = G.edge[i].v, w = G.edge[i].w, i; i = G.edge[i].nxt)
	#define fewh(G,u,h) for (auto [i, v, w] = make_tuple (h[u], int(), int()); v = G.edge[i].v, w = G.edge[i].w, i; i = G.edge[i].nxt)
	#define fewht(G,u,h,T) for (auto [i, v, w] = make_tuple (h[u], int(), T()); v = G.edge[i].v, w = G.edge[i].w, i; i = G.edge[i].nxt)
	#define fewc(G,u) for (auto [i, v, w, c] = make_tuple (G.head[u], int(), int(), int()); v = G.edge[i].v, w = G.edge[i].w, c = G.edge[i].c, i; i = G.edge[i].nxt)
	#define fewct(G,u,T1,T2) for (auto [i, v, w, c] = make_tuple (G.head[u], int(), T1(), T2()); v = G.edge[i].v, w = G.edge[i].w, c = G.edge[i].c, i; i = G.edge[i].nxt)
	#define fewch(G,u,h) for (auto [i, v, w, c] = make_tuple (h[u], int(), int(), int()); v = G.edge[i].v, w = G.edge[i].w, c = G.edge[i].c, i; i = G.edge[i].nxt)
	#define fewcht(G,u,h,T1,T2) for (auto [i, v, w, c] = make_tuple (h[u], int(), T1(), T2()); v = G.edge[i].v, w = G.edge[i].w, c = G.edge[i].c, i; i = G.edge[i].nxt)
}

namespace lay {
    class cpx {
        public:
            double a, b;
            cpx () {a = 0, b = 0;}
            cpx (double _a) {a = _a, b = 0;}
            cpx (double _a, double _b) {a = _a, b = _b;}
            friend cpx operator + (cpx a, cpx b) {return cpx (a.a + b.a, a.b + b.b);}
            friend cpx operator - (cpx a, cpx b) {return cpx (a.a - b.a, a.b - b.b);}
            friend cpx operator * (cpx a, cpx b) {return cpx (a.a * b.a - a.b * b.b, a.b * b.a + a.a * b.b);}
            friend cpx operator / (cpx a, cpx b) {return cpx ((a.a * b.a + a.b * b.b) / (b.b * b.b + b.a * b.a), (a.b * b.a - a.a * b.b) / (b.b * b.b + b.a * b.a));}
            friend cpx& operator += (cpx &a, cpx b) {return a = a + b;}
            friend cpx& operator -= (cpx &a, cpx b) {return a = a - b;}
            friend cpx& operator *= (cpx &a, cpx b) {return a = a * b;}
            friend cpx& operator /= (cpx &a, cpx b) {return a = a / b;}
    };
}

template <typename T>
inline void Write (T x) {
	if (x < 0) putchar ('-'), x *= -1;
	if (x >= 10) Write (x / 10);
	putchar (x % 10 + '0');
}
template <typename T> void write (char sep, char end, T x) {Write (x); putchar (end);}
template <typename T, typename... Ts> void write (char sep, char end, T x, Ts... xs) {Write (x); putchar (sep); write (sep, end, xs...);}
template <typename... Ts> void output (Ts... xs) {write (' ', '\n', xs...);}


namespace lay {
    template <typename T = int>
    class _Math {
    public:
        static T exmax (T x) {return x;}
        template <typename... Ts> static T exmax (T x, Ts... xs) {return max (x, exmax (xs...));}
        static T exmin (T x) {return x;}
        template <typename... Ts> static T exmin (T x, Ts... xs) {return min (x, exmin (xs...));}
        template <typename... Ts> static T exgmax (T &x, Ts... xs) {return x = exmax (x, xs...);}
        template <typename... Ts> static T exgmin (T &x, Ts... xs) {return x = exmin (x, xs...);}

        static T gcd (T a, T b) {return !b ? a : gcd (b, a % b);}
        static T lcm (T a, T b) {return a / gcd (a, b) * b;}
        static T exgcd (T a, T b, T& x, T& y) {
            if (!b) {x = 1; y = 0; return a;}
            T ans = exgcd (b, a % b, y, x);
            y -= a / b * x;
            return ans;
        }
        static T crt (size_t n, T *a, T *p) {
            T M = 1, ans = 0;
            fq (i, 1, n) M *= p[i];
            fq (i, 1, n) {
                T m = M / p[i];
                T x, y;
                exgcd (m, p[i], x, y);
                ans += (x < 0 ? x + p[i] : x) * a[i] * m;
            } return ans % M;
        }
        static T excrt (size_t n, T *a, T *b) {
            T M = b[1], ans = a[1];
            fq (i, 2, n) {
                T aa = M, c = (a[i] - ans % b[i] + b[i]) % b[i];
                T x, y;
                T gcd = exgcd (aa, b[i], x, y);
                if (c % gcd) return -1;
                T bg = b[i] / gcd;
                x = c / gcd * x % bg;
                ans += x * M;
                M *= bg;
                ans = (ans % M + M) % M;

            }
            return (ans % M + M) % M;
        }
        static T power (T a, T b, T p) {
            T c = 1;
            while (b) {
                if (b & 1) c = c * a % p;
                a = a * a % p;
                b >>= 1;
            } return c;
        }
    private:
        static T C (T n, T m, T p) {
            T ans = 1;
            fq (i, n - m + 1, n) ans = ans * i % p;
            fq (i, 2, m) ans = ans * power (i, p - 2, p) % p;
            return ans;
        }
    public:
        static T lucas (T n, T m, T p) {
            if (!m || !n) return 1;
            return lucas (n / p, m / p, p) * C (n % p, m % p, p) % p;
        }
        static T bsgs (T a, T b, T p) {
            T mul = 1, t = sqrt (p) + 1;
            static map <T, T> mp;
            mp.clear ();
            fq (i, 1, t) {
                mul = mul * a % p;
                mp[b * mul % p] = i;
            }
            T mull = mul;
            fq (i, 1, t) {
                if (mp[mull]) return i * t - mp[mull];
                mull = mull * mul % p;
            } return -1;
        }
    };
    const _Math <> iMath;
    auto Math = iMath;
}

namespace lay {
    template <typename T = int>
    class _ExMath {
    private:
        static void expr_skpop (stack <char> &sk1, stack <T> &sk2, T fun (T, T, char)) {
            T r = sk2.top (); sk2.pop ();
            T l = sk2.top (); sk2.pop ();
            char op = sk1.top (); sk1.pop ();
            sk2.push (fun (l, r, op));
        }
    public:
        static T expr (string s, map <char, short> mp, T fun (T, T, char)) {
            static stack <char> sk1;
            static stack <T> sk2;
            while (!sk1.empty ()) sk1.pop ();
            while (!sk2.empty ()) sk2.pop ();
            s = '(' + s + ')';
            int len = s.size ();
            fnq (i, 0, len) {
                if (isdigit (s[i])) {
                    T num = 0;
                    while (isdigit (s[i])) num = num * 10 + s[i] - '0', ++i;
                    --i;
                    sk2.push (num);
                } elif (s[i] == '(') {
                    sk1.push ('(');
                } elif (s[i] == ')') {
                    while (sk1.top () != '(')
                        expr_skpop (sk1, sk2, fun);
                    sk1.pop ();
                } else {
                    while (!sk1.empty () && sk1.top () != '(' && mp[sk1.top ()] >= mp[s[i]])
                        expr_skpop (sk1, sk2, fun);
                    sk1.push (s[i]);
                }
            }
            return sk2.top ();
        }
    };
    const _ExMath <> iExMath;
    auto ExMath = iExMath;
}

namespace lay {
    int Eular (int x) {
        int sqrtx = sqrt (x);
        int ans = x;
        fq (i, 2, sqrtx) if (x % i == 0) {
            ans = ans / i * (i - 1);
            while (x % i == 0) x /= i;
        } if (x > 1) ans = ans / x * (x - 1);
        return ans;
    }
    template <int p>
    class Modint {
        private:
            const static int eular = Eular (p);
            int num;
            static int unsave_constructor (int x) {return (x % p + p) % p;}
        public:
            int toInt () {return num;}
            Modint () {}
            Modint (int x) {num = unsave_constructor (x);}
            friend Modint operator + (Modint a, Modint b) {int c = a.num + b.num; if (c >= p) c -= p; return Modint (c);}
            friend Modint operator - (Modint a, Modint b) {int c = a.num - b.num; if (c < 0) c += p; return Modint (c);}
            friend Modint operator * (Modint a, Modint b) {return Modint <p> :: unsave_constructor (a.num * b.num);}
            friend Modint operator / (Modint a, Modint b) {return Modint <p> :: unsave_constructor (a.num * Math.power (b.num, p - 2, p));}
            friend Modint operator ^ (Modint a, Modint b) {return Math.power (a.num, b.num % Modint <p> :: eular, p);}
            friend Modint& operator += (Modint &a, Modint b) {return a = a + b;}
            friend Modint& operator -= (Modint &a, Modint b) {return a = a - b;}
            friend Modint& operator *= (Modint &a, Modint b) {return a = a * b;}
            friend Modint& operator /= (Modint &a, Modint b) {return a = a / b;}
            friend Modint& operator ^= (Modint &a, Modint b) {return a = a ^ b;}
            Modint& operator ++ () {*this += 1; return *this;}
            Modint operator ++ (signed) {Modint cpy = *this; ++(*this); return cpy;}
            Modint& operator -- () {*this -= 1; return *this;}
            Modint operator -- (signed) {Modint cpy = *this; --(*this); return cpy;}
            friend istream& operator >> (istream& in, Modint x) {x = rd (p); return in;}
            friend ostream& operator << (ostream&out, Modint x) {out << x.toInt (); return out;}
    };
}

namespace lay {
	inline int lowbit (int i) {return i & -i;}
	template <int SZ>
	class BIT {
		int c[SZ];
		int n;
		public:
		BIT () {}
		void set (int x) {n = x;}
		void clear () {fq (i, 0, n) c[i] = 0;}
		BIT (int x) {set (x);}
		void add (int i, int x) {while (i <= n) c[i] += x, i += lowbit (i);}
		int ask (int i) {int s = 0; while (i) s += c[i], i -= lowbit (i); return s;}
		int query (int l, int r) {return ask (r) - ask (l - 1);}
	};
}

namespace lay {
	template <int p>
	struct _Cipolla {
		int i;
		struct comp {
			int a, b;
		};
		comp mul (comp a, comp b) {
			return {(a.a * b.a + a.b * b.b % p * i) % p, (a.b * b.a + a.a * b.b) % p};
		}
		int power (comp a, int b) {
			comp c = {1, 0};
			while (b) {
				if (b & 1) c = mul (c, a);
				a = mul (a, a);
				b >>= 1;
			} return c.a;
		}
		
		pair <int, int> solve (int n) {
			if (n == 0) return {0, -1};
			if (Math.power (n, (p - 1) >> 1, p) == p - 1) return {-1, -1};
			mt19937 rnd(random_device {} ());
			int c = -1;
			while (1) {
				c = rnd () % (p - 1) + 1; i = (c * c - n + p) % p;
				if (power ({i, 0}, (p - 1) >> 1) == p - 1) break;
			} int s = power ({c, 1}, (p + 1) >> 1); return {s, p - s};
		}
		
		pair <int, int> operator () (int n) {
			return solve (n);
		}
	};
	
	namespace poly {
		const int p = 998244353;
		const int g = 3, gi = Math.power (g, p - 2, p);
		struct _NTT {
		  private:
			vi Turn;
			vi gs, gis;
			int cnt;
		  public:
			int size () {return Turn.size ();}
			void init (int len) {
				int n = 1; while (n < len) n <<= 1;
				Turn.resize (n);
				Turn[0] = 0;
				fnq (i, 1, n) Turn[i] = (Turn[i >> 1] | (i & 1 ? n : 1)) >> 1;
			}
			void ntt (vi &x, bool op) {
				int n = size ();
				if ((int)x.size () < n) x.resize (n);
				fnq (i, 0, n) if (i < Turn[i]) swap (x[i], x[Turn[i]]);
				int cc = 1;
				for (int h = 2; h <= n; h <<= 1, ++cc) {
					int Wn = (op ? gis[cc] : gs[cc]);
					for (int i = 0; i < n; i += h) {
						int w = 1;
						fnq (j, 0, h >> 1) {
							int a = x[i + j], b = 1ll * x[i + j + (h >> 1)] * w % p;
							x[i + j] = (a + b) % p;
							x[i + j + (h >> 1)] = (a - b + p) % p;
							w = 1ll * w * Wn % p;
						}
					}
				}
				if (op) {
					int inv = Math.power (n, p - 2, p);
					fnq (i, 0, n) x[i] = 1ll * x[i] * inv % p;
				}
			}
			_NTT () {
				gs.resize (25);
				fq (i, 1, 23) gs[i] = Math.power (g, (p-1) / (1<<i), p);
				gis.resize (25);
				fq (i, 1, 23) gis[i]= Math.power(gi, (p-1) / (1<<i), p);
			}
		} NTT;
		
		vi poly_mul (vi a, vi b) {
			NTT.init (a.size () + b.size () - 1);
			NTT.ntt (a, 0);
			NTT.ntt (b, 0);
			fnq (i, 0, NTT.size ()) a[i] = 1ll * a[i] * b[i] % p;
			NTT.ntt (a, 1);
			return a;
		}
		
		vi poly_inv (vi a, int n) {
			if ((int)a.size () > n) a.resize (n);
			if (n == 1) return {Math.power (a[0], p - 2, p)};
			auto b = poly_inv (a, (n + 1) >> 1);
			auto c = poly_mul (a, b);
			fnq (i, 0, (int)c.size ()) c[i] = (p - c[i]) % p;
			c[0] = (c[0] + 2) % p;
			c = poly_mul (c, b);
			c.resize (n);
			return c;
		}
		
		vi poly_int (vi a, int c = 0) {
			vi b;
			b.pb (c);
			fnq (i, 0, (int)a.size ())
				b.pb (1ll * Math.power (i+1, p-2, p) * a[i] % p);
			return b;
		}
		
		vi poly_diff (vi a) {
			vi b;
			fnq (i, 1, (int)a.size ())
				b.pb (1ll * i * a[i] % p);
			return b;
		}
		
		vi poly_ln (vi a, int n) {
			if ((int)a.size () > n) a.resize (n);
			auto b = poly_diff (a);
			auto c = poly_mul (b, poly_inv (a, n));
			auto e = poly_int (c, 0);
			e.resize (n);
			return e;
		}
		
		vi poly_add (vi a, vi b) {
			vi c;
			c.resize (max (a.size (), b.size ()));
			fnq (i, 0, (int)c.size ()) c[i] = 0;
			fnq (i, 0, (int)a.size ()) c[i] = a[i];
			fnq (i, 0, (int)b.size ()) c[i] = (c[i] + b[i]) % p;
			return c;
		}
		
		vi poly_sub (vi a, vi b) {
			vi c;
			c.resize (max (a.size (), b.size ()));
			fnq (i, 0, (int)c.size ()) c[i] = 0;
			fnq (i, 0, (int)a.size ()) c[i] = a[i];
			fnq (i, 0, (int)b.size ()) c[i] = (c[i] + p - b[i]) % p;
			return c;
		}
		
		vi poly_exp (vi a, int n) {
			if ((int)a.size () > n) a.resize (n);
			if (n == 1) return {1};
			auto b = poly_exp (a, (n + 1) >> 1);
			auto c = a; c[0] = (c[0] + 1) % p;
			auto e = poly_ln (b, n);
			auto f = poly_sub (c, e);
			auto g = poly_mul (b, f);
			g.resize (n);
			return g;
		}
		
		vi poly_R (vi a, int n) {
			a.resize (n+1);
			fnq (i, 0, (n+1) >> 1) swap (a[i], a[n-i]);
			return a;
		}
		
		void poly_print(vi a, int n) {
			int lim = min ((int)a.size()-1, n);
			fq (i, 0, lim) cout << a[i] << " ";
			fq (i, lim+1, n) cout << "0 ";
			puts (""); 
		}
		
		void poly_print(vi a) {
			int n = a.size () - 1;
			while (n && a[n] == 0) --n;
			poly_print (a, n);
		}
		
		void poly_seize (vi &a) {
			int n = a.size () - 1;
			while (n && a[n] == 0) --n;
			a.resize (n+1);
		}
		
		pair <vi, vi> poly_div (vi a, vi b) {
			poly_seize (a); poly_seize (b);
			int n = a.size()-1, m = b.size()-1;
			if (n < m) return {{0}, a};
			auto ar = poly_R (a, n);
			auto br = poly_R (b, m);
			auto qr = poly_mul (ar, poly_inv (br, n-m+1));
			auto q = poly_R (qr, n-m);
			auto r = poly_sub (a, poly_mul (b, q));
			q.resize (n-m+1); r.resize (m);
			return {q, r};
		}
		
		void poly_multi_eval_solve1 (vi &ps, int l, int r, int rt, vector <vi > &h) {
			if (l == r) {
				h[rt] = {(p - ps[l]) % p, 1};
				return;
			}
			int mid = (l + r) >> 1;
			poly_multi_eval_solve1 (ps, l, mid, rt << 1, h);
			poly_multi_eval_solve1 (ps, mid + 1, r, rt << 1 | 1, h);
			h[rt] = poly_mul (h[rt << 1], h[rt << 1 | 1]);
			poly_seize (h[rt]);
		}
		
		void poly_multi_eval_solve2 (vi f, vi &ps, int l, int r, int rt, vector <vi > &h, vi &g) {
			f = poly_div (f, h[rt]).se;
			// if (l == r) {
				// g[l] = f[0];
				// return;
			// }
			if (r - l + 1 <= 1024) {
				int n = f.size () - 1;
				fq (i, l, r) {
					int s = 0, x = ps[i];
					nfq (j, n, 0) s = (1ll * s * x + f[j]) % p;
					g[i] = s;
				}
				return;
			}
			int mid = (l + r) >> 1;
			poly_multi_eval_solve2 (f, ps, l, mid, rt << 1, h, g);
			poly_multi_eval_solve2 (f, ps, mid + 1, r, rt << 1 | 1, h, g);
		}
		
		vi poly_multi_eval (vi &f, vi &ps) {
			int n = ps.size ();
			vector <vi> h; h.resize (n << 2);
			poly_multi_eval_solve1 (ps, 0, n-1, 1, h);
			vi g; g.resize (n);
			poly_multi_eval_solve2 (f, ps, 0, n-1, 1, h, g);
			return g;
		}
		
		void poly_fast_inter_solve1 (vector <pii> &ps, int l, int r, int rt, vector <vi > &h) {
			if (l == r) {
				h[rt] = {(p - ps[l].fi) % p, 1};
				return;
			}
			int mid = (l + r) >> 1;
			poly_fast_inter_solve1 (ps, l, mid, rt << 1, h);
			poly_fast_inter_solve1 (ps, mid + 1, r, rt << 1 | 1, h);
			h[rt] = poly_mul (h[rt << 1], h[rt << 1 | 1]);
			poly_seize (h[rt]);
		}
		
		vi poly_fast_inter_solve2 (vector <pii> &ps, vi &gx, int l, int r, int rt, vector <vi > &h) {
			if (l == r)
				return {1ll * ps[l].se * Math.power (gx[l], p-2, p) % p};
			int mid = (l + r) >> 1;
			auto vl = poly_mul (h[rt << 1 | 1], poly_fast_inter_solve2 (ps, gx, l, mid, rt << 1, h));
			auto vr = poly_mul (h[rt << 1], poly_fast_inter_solve2 (ps, gx, mid + 1, r, rt << 1 | 1, h));
			auto v = poly_add (vl, vr);
			poly_seize (v);
			return v;
		}
		
		vi poly_fast_inter (vector <pii> &ps) {
			int n = ps.size ();
			vector <vi> h; h.resize (n << 2);
			poly_fast_inter_solve1 (ps, 0, n-1, 1, h);
			auto gg = poly_diff (h[1]);
			vi xs; xs.resize (n);
			fnq (i, 0, n) xs[i] = ps[i].fi;
			auto gx = poly_multi_eval (gg, xs);
			auto f = poly_fast_inter_solve2 (ps, gx, 0, n-1, 1, h);
			return f;
		}
		
		// for a_0=1
		vi poly_pow (vi a, int k, int n) {
			auto b = poly_ln (a, n);
			auto c = poly_mul (b, {k});
			auto e = poly_exp (c, n);
			return e;
		}

		// for all but a_0==0 and k is large and k%p is small
		vi poly_pow (vi a, int n, int k1, int k2) {
			int len = min ((int)a.size (), n);
			int t = 0; while (t < len && a[t] == 0) ++t;
			if (t == len || t * k1 >= n) return vi (n, 0);
			int x = a[t], invx = Math.power (x, p-2, p);
			vi aa;
			fq (i, t, len - 1) aa.pb (a[i] * invx % p);
			int nn = n - t;
			auto b = poly_ln (aa, nn);
			auto c = poly_mul (b, {k1});
			auto e = poly_exp (c, nn);
			auto ee = poly_mul (e, {Math.power (x, k2, p)});
			vi f (t * k1, 0);
			int lim = n - t * k1;
			fnq (i, 0, lim) f.pb (ee[i]);
			return f;
		}

		pair <vi, vi> poly_sqrt (vi a, int n) {
			static _Cipolla <p> Cipolla;
			auto sqs = Cipolla (a[0]);
			int sq1 = sqs.fi, sq2 = sqs.se;
			if (sq1 == -1) return {{}, {}};
			const int inv2 = Math.power (2, p-2, p);
			auto b = poly_mul (a, {Math.power (a[0], p-2, p)});
			auto c = poly_ln (b, n);
			auto e = poly_mul (c, {inv2});
			auto f = poly_exp (e, n);
			auto g1 = poly_mul (f, {sq1});
			vi g2 = {};
			if (sq2 != -1) g2 = poly_mul (f, {sq2});
			return {g1, g2};
		}
	}
}

// #define COUNTING_PROBLEM

#if defined (COUNTING_PROBLEM)
#define padd(x,y) (x = (x + y) % p)
#endif

using namespace lay;

const int p = 998244353;
map <vector <int>, int> mp; int mpcnt;
const int maxn = 300313;
Graph <maxn, maxn * 10> G;

int n, k;
string s;
int in[maxn];
void dfs (vi &f) {
	fq (c, 'A', 'Z') {
		vi g(n+1);
		fq (i, 0, n) g[i] = f[i] + 1;
		fq (i, 1, n)
			if (c!=s[i])
				g[i] = min (g[i], f[i-1] + 1);
			else
				g[i] = min (g[i], f[i-1]);
		fq (i, 1, n)
			g[i] = min (g[i], g[i-1] + 1);
		bool fl = 0;
		fq (i, 0, n) if (g[i] <= k) {fl = 1; break;}
		if (!fl) continue;
		// for (auto x : f) cout << x;
		// cout << ' ' << (char)c << ' ';
		// for (auto x : g) cout << x;
		// cout << endl;
		if (!mp[g]) mp[g] = ++mpcnt, dfs (g);
		G.addedge (mp[f], mp[g]); ++in[mp[g]];
	}
}

int f[maxn];

signed main () {
	cin >> s; n = s.size (); s = " " + s; k = d;
	{vi v; fq (i, 0, n) v.pb (i); mp[v] = ++mpcnt; dfs (v);}
	queue <int> q;
	f[1] = 1;
	q.push (1);
	while (!q.empty ()) {
		int u = q.front (); q.pop ();
		fe (G, u) {
			f[v] = (f[v] + f[u]) % p;
			if (!(--in[v])) q.push (v);
		}
	}
	int ans = 0;
	for (auto [v, i] : mp) if (v[n] == k) ans = (ans + f[i]) % p;
	cout << ans << endl;
	return 0;
}