#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long #define mp make_pair #define pii pair #define fi first #define se second #define pb push_back const int MOD = 998244353;// const int FACTMAX = 2000005;// const int CATALANMAX = 1000005;// int fact[FACTMAX], invfact[FACTMAX], cat[CATALANMAX]; int expo(int a, int b){ int res=1; a%=MOD; while (b){ if (b&1)res=(res*a)%MOD; a=(a*a)%MOD; b>>=1; } return res; } int inv(int num){ return expo(num, MOD-2); } void initfact(){ fact[0]=1; for (int i=1; i=0; --i)invfact[i]=(invfact[i+1]*(i+1))%MOD; } int ncr(int n, int r){ if (n>t; while (t--){ int n, ans=1; string s; cin>>n>>s; vector > vect; for (auto c:s){ if (vect.empty()||vect.back().fi!=c)vect.pb(mp(c, 1)); else ++vect[vect.size()-1].se; } for (int i=1; i