---
# System prepended metadata

title: NYCU 2024 Team Selection Programming Contest

---

NYCU 2024 Team Selection Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/105381

比賽影片
---
No

記分板
---
![image](https://hackmd.io/_uploads/rkbGfu8AC.png)


題解
---
### A. Trip Counting I
---
#### 題目摘要
一個$n$點完全圖給你刪掉的邊找三環
#### 想法

:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n);
    vector<pii> edge;
    rep (i, 0, m) {
        int a, b; cin >> a >> b;
        a--, b--;
        if (a > b) swap(a, b);
        edge.pb({a, b});
        adj[a].pb(b);
        adj[b].pb(a);
    }
    ll ans = 1LL * n * (n - 1) * (n - 2) / 6;
    ans -= 1LL * m * (n - 2);
    rep (i, 0, n) {
        int sz = adj[i].size();
        ans += 1LL * sz * (sz - 1) / 2;
    }
    vector<vector<int>> big(n);
    for (auto [a, b] : edge) {
        if (adj[a].size() < adj[b].size()) swap(a, b);
        big[a].pb(b);
    }
    ll cyc = 0;
    vector<int> cur(n, -1);
    rep (i, 0, n) if (big[i].size()) {
        for (int x : adj[i]) cur[x] = i;
        for (int sm : big[i]) {
            for (int x : adj[sm]) if (x != i) cyc += cur[x] == i;
        }
    }
    ans -= cyc / 3;
    cout << ans * 6 << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}    
```
:::

### B. Trip Counting II
---
#### 題目摘要
找四環

#### 想法


:::spoiler 實作

```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second

#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif

void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n);
    vector<int> ord(n), rk(n);
    rep (i, 0, m) {
        int a, b; cin >> a >> b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    iota(all(ord), 0);
    sort(all(ord), [&](int a, int b) {
        return adj[a].size() > adj[b].size();
    });
    rep (i, 0, n) rk[ord[i]] = i;
    vector<vector<int>> D(n);
    rep (u, 0, n) {
        for (int v : adj[u]) if (rk[u] < rk[v]) {
            D[u].pb(v);
        }
    }
    // ord = sort by deg decreasing, rk[ord[i]] = i
    // D: undirected to directed edge from rk small to rk big
    vector<int> vis(n);
    ll c3 = 0, c4 = 0;
    for (int x : ord) { // c3
        for (int y : D[x]) vis[y] = 1;
        for (int y : D[x]) for (int z : D[y]) c3 += vis[z];
        for (int y : D[x]) vis[y] = 0;
    }
    for (int x : ord) { // c4
        for (int y : D[x]) for (int z : adj[y])
        if (rk[z] > rk[x]) c4 += vis[z]++;
        for (int y : D[x]) for (int z : adj[y])
            if (rk[z] > rk[x]) --vis[z];
    }
    cout << c4 * 8 << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::


### C. Trip Counting III
---
#### 題目摘要
找五環

#### 想法
枚舉所有點當起點，若有一條邊兩端點的距離都是2則它有可能是5環，然而有可能兩點走的路徑有重複邊，將它們扣掉就是答案

:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ORENOOSHIKYOUMOKAWAIII ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second

const int N=1005;
vector<int> v[N];
pii p[N];
ll dp[3][N][N];

void _solve(){
    int n, m;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> p[i].F >> p[i].S;
        v[p[i].F].push_back(p[i].S);
        v[p[i].S].push_back(p[i].F);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) dp[0][i][j]=dp[1][i][j]=dp[2][i][j]=0;
        dp[0][i][i]=1;
        for(int j=1;j<=2;j++){
            for(int k=0;k<m;k++){
                auto [x, y]=p[k];
                dp[j][i][x]+=dp[j-1][i][y];
                dp[j][i][y]+=dp[j-1][i][x];
            }
        }
        for(int j=1;j<=n;j++) if (dp[0][i][j]) dp[2][i][j]=0;
    }
    ll cnt=0;
    for(int k=0;k<m;k++){
        auto [x, y]=p[k];
        if (x==y) continue;
        for(int j=1;j<=n;j++){
            ll tmp=(dp[2][j][x]-dp[1][j][y])*(dp[2][j][y]-dp[1][j][x]);
            tmp=max(0LL, tmp);
            cnt+=tmp;
        }
        for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) if (i!=j){
            if (dp[2][j][x]&&dp[2][j][y]&&dp[1][j][i]){
                cnt-=dp[1][i][x]*dp[1][i][y];
            }
        }
    }
    cnt<<=1;
    cout << cnt << '\n';
}

int main(){
    ORENOOSHIKYOUMOKAWAIII;
    int _t=1;
    //cin >> _t;
    while(_t--) _solve();
}
```
:::

### D. Rearrangement
---
#### 題目摘要
#### 想法


:::spoiler 實作
```cpp=

```
:::

### E. Elimination Game
---
#### 題目摘要

#### 想法

:::spoiler 實作
```cpp=

```
:::

### F. Destroying Monsters
---
#### 題目摘要
#### 想法

:::spoiler 實作
```cpp=

```
:::

### G. Graph Coloring Problem
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=

```
:::


### H. Points Separation
---
#### 題目摘要

#### 想法
建凸包，先判是不是在多邊形外，是的話花 $O(N)$ 把所有點到點跟點到線段的距離取min再/2。
總複雜度$O(NQ)$
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second

#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif

void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

struct point{
    ll x, y;
    
    point operator + (point p1) { return {x + p1.x, y + p1.y}; }
    point operator - (point p1) { return {x - p1.x, y - p1.y}; }
    ll    operator ^ (point p1) { return x * p1.y - p1.x * y; }
    ll    operator * (point p1) { return x * p1.x + y * p1.y; }
    bool operator < (const point &p1) const {
        if (x != p1.x) return x < p1.x;
        return y < p1.y;
    };
};

ostream& operator << (ostream &os, const point &p) { return os << '(' << p.x << "," << p.y << ')'; }

double abs2(point o) { return o * o; }
double abs(point o) { return sqrtl(abs2(o)); }

int sign(ll num){
    if (fabs(num) <= eps) return 0;
    return num > 0 ? 1 : -1;
}

int ori(point o, point a, point b) {
    return sign((a - o) ^ (b - o));
}
 
bool onseg(point p1, point p2, point p3) { // {online, online, other}
    point va = p1 - p3, vb = p2 - p3;
    return (va ^ vb) == 0 && (va * vb) <= 0;
}
 
bool banana(point p1, point p2, point q1, point q2) {
    if (onseg(p1, p2, q1) || onseg(p1, p2, q2) ||
       onseg(q1, q2, p1) || onseg(q1, q2, p2)) return 1;
    if (ori(p1, p2, q1) * ori(p1, p2, q2) < 0 &&
       ori(q1, q2, p1) * ori(q1, q2, p2) < 0) return 1;
    return 0;
}

double PointSegDist(point q0, point q1, point p) {
    if (sign(abs(q0 - q1)) == 0) return abs(q0 - p);
    if (sign((q1 - q0) * (p - q0)) >= 0 && sign((q0 - q1) * (p - q1)) >= 0)
        return fabs(((q1 - q0) ^ (p - q0)) / abs(q0 - q1));
    return min(abs(p - q0), abs(p - q1));
}

bool PointInConvex(const vector<point> &C, point p, bool strict = true) {
    // no three points are collinear
    int a = 1, b = C.size() - 1, r = !strict;
    if (C.size() == 0) return false;
    if (C.size() < 3) return r && onseg(C[0], C.back(), p);
    if (ori(C[0], C[a], C[b]) > 0) swap(a, b);
    if (ori(C[0], C[a], p) >= r || ori(C[0], C[b], p) <= -r) return false;
    while (abs(a - b) > 1) {
        int c = a + b >> 1;
        (ori(C[0], C[c], p) > 0 ? b : a) = c;
    }
    return ori(C[a], C[b], p) < r;
}

void solve() {
    int n, q; cin >> n >> q;
    vector<point> pt(n);
    for (auto &[x, y] : pt) cin >> x >> y;
    // need vector<pll> pt
    sort(all(pt));
    auto cross = [&](point a, point b) -> ll {
        return (a ^ b);
    };
    vector<point> hull;
    rep (i, 0, n) {
        while (hull.size() >= 2 && cross(pt[i] - hull.end()[-2], hull.back() - hull.end()[-2]) >= 0) {
            hull.pop_back();
        }
        hull.pb(pt[i]);
    }
    int sz = hull.size();
    for(int i = n - 2; i >= 0; --i){
        while(hull.size() > sz && cross(pt[i] - hull.end()[-2], hull.back() - hull.end()[-2]) >= 0) hull.pop_back();
        hull.pb(pt[i]);
    }
    hull.pop_back();
    sz = hull.size();
    // cout << hull;
    cout << fixed << setprecision(15);
    while (q--) {
        point p; cin >> p.x >> p.y;
        if (PointInConvex(hull, p, 0)) {
            cout << -1 << '\n';
        } else {
            double ans = 9e18;
            rep (i, 0, sz) {
                chmin(ans, abs(p - hull[i]));
                chmin(ans, PointSegDist(hull[i], hull[(i + 1) % sz], p));
            }
            if (sz == 0) ans = abs(p - pt[0]);
            ans /= 2;
            cout << ans << '\n';
        }
    }
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::

### I. LIS Decrement
---
#### 題目摘要
#### 想法
做個$O(N^2)$LIS的DP，考慮建flow模型，先把點拆成入點跟出點中間連權重流量，將dp[i] == 1的點連到源點，dp[i] == lis的點連到匯點，然後中間的邊就看dp的轉移關係建邊，最後答案就是最小割。
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

struct Dinic {
    
    struct edge {
        int v, r; ll rc;
    };

    vector<vector<edge>> adj;
    vector<int> dis, it;
    Dinic(int n) : adj(n), dis(n), it(n) {}

    void add_edge(int u, int v, ll c) {
        adj[u].pb({v, adj[v].size(), c});
        adj[v].pb({u, adj[u].size() - 1, 0});
    }

    bool bfs(int s, int t) {
        fill(all(dis), IINF);
        queue<int> q;
        q.push(s);
        dis[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const auto& [v, r, rc] : adj[u]) {
                if (dis[v] < IINF || rc == 0) continue;
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
        return dis[t] < IINF;
    }

    ll dfs(int u, int t, ll cap) {
        if (u == t || cap == 0) return cap;
        for (int &i = it[u]; i < (int)adj[u].size(); ++i) {
            auto &[v, r, rc] = adj[u][i];
            if (dis[v] != dis[u] + 1) continue;
            ll tmp = dfs(v, t, min(cap, rc));
            if (tmp > 0) {
                rc -= tmp;
                adj[v][r].rc += tmp;
                return tmp;
            }
        }
        return 0;
    }

    ll flow(int s, int t) {
        ll ans = 0, tmp;
        while (bfs(s, t)) {
            fill(all(it), 0);
            while ((tmp = dfs(s, t, IINF)) > 0) {
                ans += tmp;
            }
        }
        return ans;
    }

    bool inScut(int u) { return dis[u] < IINF; }
};

void solve() {
    int n; cin >> n;
    vector<int> a(n), w(n);
    rep (i, 0, n) cin >> a[i];
    rep (i, 0, n) cin >> w[i];
    Dinic G(2 * n + 2);
    int s = 2 * n, t = s + 1;
    int lis = 1;
    vector<int> dp(n);
    dp[0] = 1;
    rep (i, 1, n) {
        dp[i] = 1;
        rep (j, 0, i) if (a[i] > a[j]) chmax(dp[i], dp[j] + 1);
        chmax(lis, dp[i]);
    }
    rep (i, 0, n) {
        G.add_edge(i, i + n, w[i]);
        if (dp[i] == 1) G.add_edge(s, i, IINF);
        if (dp[i] == lis) G.add_edge(i + n, t, IINF);
        rep (j, 0, i) if (a[i] > a[j] && dp[i] == dp[j] + 1) G.add_edge(j + n, i, IINF);
    }
    cout << accumulate(all(w), 0) - G.flow(s, t) << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::


### J. Randomized String Matching Algorithm
---
#### 題目摘要
拿字串t去匹配每個s的子字串，方法是做k次隨機抽一個位置匹配，求正確匹配的機率。
#### 想法

會發現對於原本就是好的匹配的怎麼抽都是好的，因此題目要求的是$P[每一個匹配不起來的子字串都不被正確匹配]$，若是一個子字串有$m_i$個位置一樣，那麼答案是$\prod \limits _{i = 0} ^{s - t + 1} (1 - (\frac{m_i}{|t|})^k)$。
變成要如何快速求出$m_i$，可以發現這就是字元匹配，因此可以考慮對每個字母$c$拆開來做，將這個位置是不是$c$當成0/1陣列，然後就是很經典的一邊反過來做捲積。
總複雜度$O(8*\text |S|\log \text |S|)$


:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second

#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif

void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder_modint {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename conditional<is_same<T, __int128_t>::value ||
                                  is_same<T, __int128>::value,
                              true_type,
                              false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename conditional<is_same<T, __uint128_t>::value ||
                                  is_same<T, unsigned __int128>::value,
                              true_type,
                              false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename conditional<is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              true_type,
                                              false_type>::type;

template <class T>
using is_signed_int = typename conditional<(is_integral<T>::value &&
                                                 is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                true_type,
                                                false_type>::type;

template <class T>
using is_unsigned_int =
    typename conditional<(is_integral<T>::value &&
                               is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              true_type,
                              false_type>::type;

template <class T>
using to_unsigned = typename conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename conditional<is_signed<T>::value,
                              make_unsigned<T>,
                              common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename is_integral<T>;

template <class T>
using is_signed_int =
    typename conditional<is_integral<T>::value && is_signed<T>::value,
                              true_type,
                              false_type>::type;

template <class T>
using is_unsigned_int =
    typename conditional<is_integral<T>::value &&
                                  is_unsigned<T>::value,
                              true_type,
                              false_type>::type;

template <class T>
using to_unsigned = typename conditional<is_signed_int<T>::value,
                                              make_unsigned<T>,
                                              common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);

// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};

    // Contracts:
    // [1] s - m0 * a = 0 (mod b)
    // [2] t - m1 * a = 0 (mod b)
    // [3] s * |m1| + t * |m0| <= b
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;

    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b

        // [3]:
        // (s - t * u) * |m1| + t * |m0 - m1 * u|
        // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        // = s * |m1| + t * |m0| <= b

        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    // by [3]: |m0| <= b/g
    // by g != b: |m0| < b/g
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
    unsigned int _m;
    unsigned long long im;

    // @param m `1 <= m < 2^31`
    explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}

    // @return m
    unsigned int umod() const { return _m; }

    // @param a `0 <= a < m`
    // @param b `0 <= b < m`
    // @return `a * b % m`
    unsigned int mul(unsigned int a, unsigned int b) const {
        // [1] m = 1
        // a = b = im = 0, so okay

        // [2] m >= 2
        // im = ceil(2^64 / m)
        // -> im * m = 2^64 + r (0 <= r < m)
        // let z = a*b = c*m + d (0 <= c, d < m)
        // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
        // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
        // ((ab * im) >> 64) == c or c + 1
        unsigned long long z = a;
        z *= b;
#ifdef _MSC_VER
        unsigned long long x;
        _umul128(z, im, &x);
#else
        unsigned long long x =
            (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
        unsigned int v = (unsigned int)(z - x * _m);
        if (_m <= v) v += _m;
        return v;
    }
};

struct modint_base {};
struct static_modint_base : modint_base {};

template <class T> using is_modint = is_base_of<modint_base, T>;
template <class T> using is_modint_t = enable_if_t<is_modint<T>::value>;

}  // namespace internal

template <int m, enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
    using mint = static_modint;

  public:
    static constexpr int mod() { return m; }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    static_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    static_modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    static_modint(T v) {
        _v = (unsigned int)(v % umod());
    }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = internal::inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = internal::is_prime<m>;
};

template <int id> struct dynamic_modint : internal::modint_base {
    using mint = dynamic_modint;

  public:
    static int mod() { return (int)(bt.umod()); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = internal::barrett(m);
    }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    dynamic_modint() : _v(0) {}
    template <class T, internal::is_signed_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        long long x = (long long)(v % (long long)(mod()));
        if (x < 0) x += mod();
        _v = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    dynamic_modint(T v) {
        _v = (unsigned int)(v % mod());
    }

    unsigned int val() const { return _v; }

    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += mod() - rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        auto eg = internal::inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    unsigned int _v;
    static internal::barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;


namespace internal {

template <class T>
using is_static_modint = is_base_of<internal::static_modint_base, T>;

template <class T>
using is_static_modint_t = enable_if_t<is_static_modint<T>::value>;

template <class> struct is_dynamic_modint : public false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public true_type {};

template <class T>
using is_dynamic_modint_t = enable_if_t<is_dynamic_modint<T>::value>;

}  // namespace internal

}  // namespace atcoder_modint

// need atcoder_modint
namespace atcoder_convolution {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        divs[cnt++] = x;
    }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (atcoder_modint::internal::pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);

template <class mint,
          int g = internal::primitive_root<mint::mod()>,
          atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
struct fft_info {
    static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);
    array<mint, rank2 + 1> root;   // root[i]^(2^i) == 1
    array<mint, rank2 + 1> iroot;  // root[i] * iroot[i] == 1

    array<mint, max(0, rank2 - 2 + 1)> rate2;
    array<mint, max(0, rank2 - 2 + 1)> irate2;

    array<mint, max(0, rank2 - 3 + 1)> rate3;
    array<mint, max(0, rank2 - 3 + 1)> irate3;

    fft_info() {
        root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
        iroot[rank2] = root[rank2].inv();
        for (int i = rank2 - 1; i >= 0; i--) {
            root[i] = root[i + 1] * root[i + 1];
            iroot[i] = iroot[i + 1] * iroot[i + 1];
        }

        {
            mint prod = 1, iprod = 1;
            for (int i = 0; i <= rank2 - 2; i++) {
                rate2[i] = root[i + 2] * prod;
                irate2[i] = iroot[i + 2] * iprod;
                prod *= iroot[i + 2];
                iprod *= root[i + 2];
            }
        }
        {
            mint prod = 1, iprod = 1;
            for (int i = 0; i <= rank2 - 3; i++) {
                rate3[i] = root[i + 3] * prod;
                irate3[i] = iroot[i + 3] * iprod;
                prod *= iroot[i + 3];
                iprod *= root[i + 3];
            }
        }
    }
};

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
void butterfly(vector<mint>& a) {
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static const fft_info<mint> info;

    int len = 0;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
    while (len < h) {
        if (h - len == 1) {
            int p = 1 << (h - len - 1);
            mint rot = 1;
            for (int s = 0; s < (1 << len); s++) {
                int offset = s << (h - len);
                for (int i = 0; i < p; i++) {
                    auto l = a[i + offset];
                    auto r = a[i + offset + p] * rot;
                    a[i + offset] = l + r;
                    a[i + offset + p] = l - r;
                }
                if (s + 1 != (1 << len))
                    rot *= info.rate2[bsf(~(unsigned int)(s))];
            }
            len++;
        } else {
            // 4-base
            int p = 1 << (h - len - 2);
            mint rot = 1, imag = info.root[2];
            for (int s = 0; s < (1 << len); s++) {
                mint rot2 = rot * rot;
                mint rot3 = rot2 * rot;
                int offset = s << (h - len);
                for (int i = 0; i < p; i++) {
                    auto mod2 = 1ULL * mint::mod() * mint::mod();
                    auto a0 = 1ULL * a[i + offset].val();
                    auto a1 = 1ULL * a[i + offset + p].val() * rot.val();
                    auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();
                    auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();
                    auto a1na3imag =
                        1ULL * mint(a1 + mod2 - a3).val() * imag.val();
                    auto na2 = mod2 - a2;
                    a[i + offset] = a0 + a2 + a1 + a3;
                    a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
                    a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
                    a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
                }
                if (s + 1 != (1 << len))
                    rot *= info.rate3[bsf(~(unsigned int)(s))];
            }
            len += 2;
        }
    }
}

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(vector<mint>& a) {
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static const fft_info<mint> info;

    int len = h;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
    while (len) {
        if (len == 1) {
            int p = 1 << (h - len);
            mint irot = 1;
            for (int s = 0; s < (1 << (len - 1)); s++) {
                int offset = s << (h - len + 1);
                for (int i = 0; i < p; i++) {
                    auto l = a[i + offset];
                    auto r = a[i + offset + p];
                    a[i + offset] = l + r;
                    a[i + offset + p] =
                        (unsigned long long)(mint::mod() + l.val() - r.val()) *
                        irot.val();
                    ;
                }
                if (s + 1 != (1 << (len - 1)))
                    irot *= info.irate2[bsf(~(unsigned int)(s))];
            }
            len--;
        } else {
            // 4-base
            int p = 1 << (h - len);
            mint irot = 1, iimag = info.iroot[2];
            for (int s = 0; s < (1 << (len - 2)); s++) {
                mint irot2 = irot * irot;
                mint irot3 = irot2 * irot;
                int offset = s << (h - len + 2);
                for (int i = 0; i < p; i++) {
                    auto a0 = 1ULL * a[i + offset + 0 * p].val();
                    auto a1 = 1ULL * a[i + offset + 1 * p].val();
                    auto a2 = 1ULL * a[i + offset + 2 * p].val();
                    auto a3 = 1ULL * a[i + offset + 3 * p].val();

                    auto a2na3iimag =
                        1ULL *
                        mint((mint::mod() + a2 - a3) * iimag.val()).val();

                    a[i + offset] = a0 + a1 + a2 + a3;
                    a[i + offset + 1 * p] =
                        (a0 + (mint::mod() - a1) + a2na3iimag) * irot.val();
                    a[i + offset + 2 * p] =
                        (a0 + a1 + (mint::mod() - a2) + (mint::mod() - a3)) *
                        irot2.val();
                    a[i + offset + 3 * p] =
                        (a0 + (mint::mod() - a1) + (mint::mod() - a2na3iimag)) *
                        irot3.val();
                }
                if (s + 1 != (1 << (len - 2)))
                    irot *= info.irate3[bsf(~(unsigned int)(s))];
            }
            len -= 2;
        }
    }
}

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution_naive(const vector<mint>& a,
                                    const vector<mint>& b) {
    int n = int(a.size()), m = int(b.size());
    vector<mint> ans(n + m - 1);
    if (n < m) {
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                ans[i + j] += a[i] * b[j];
            }
        }
    } else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i + j] += a[i] * b[j];
            }
        }
    }
    return ans;
}

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution_fft(vector<mint> a, vector<mint> b) {
    int n = int(a.size()), m = int(b.size());
    int z = 1 << internal::ceil_pow2(n + m - 1);
    a.resize(z);
    internal::butterfly(a);
    b.resize(z);
    internal::butterfly(b);
    for (int i = 0; i < z; i++) {
        a[i] *= b[i];
    }
    internal::butterfly_inv(a);
    a.resize(n + m - 1);
    mint iz = mint(z).inv();
    for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
    return a;
}

}  // namespace internal

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution(vector<mint>&& a, vector<mint>&& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};
    if (min(n, m) <= 60) return atcoder_convolution::internal::convolution_naive(a, b);
    return internal::convolution_fft(a, b);
}

template <class mint, atcoder_modint::internal::is_static_modint_t<mint>* = nullptr>
vector<mint> convolution(const vector<mint>& a,
                              const vector<mint>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};
    if (min(n, m) <= 60) return atcoder_convolution::internal::convolution_naive(a, b);
    return internal::convolution_fft(a, b);
}

template <unsigned int mod = 998244353,
          class T,
          enable_if_t<atcoder_modint::internal::is_integral<T>::value>* = nullptr>
vector<T> convolution(const vector<T>& a, const vector<T>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    using mint = atcoder_modint::static_modint<mod>;
    vector<mint> a2(n), b2(m);
    for (int i = 0; i < n; i++) {
        a2[i] = mint(a[i]);
    }
    for (int i = 0; i < m; i++) {
        b2[i] = mint(b[i]);
    }
    auto c2 = convolution(move(a2), move(b2));
    vector<T> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        c[i] = c2[i].val();
    }
    return c;
}

vector<long long> convolution_ll(const vector<long long>& a,
                                      const vector<long long>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};

    static constexpr unsigned long long MOD1 = 754974721;  // 2^24
    static constexpr unsigned long long MOD2 = 167772161;  // 2^25
    static constexpr unsigned long long MOD3 = 469762049;  // 2^26
    static constexpr unsigned long long M2M3 = MOD2 * MOD3;
    static constexpr unsigned long long M1M3 = MOD1 * MOD3;
    static constexpr unsigned long long M1M2 = MOD1 * MOD2;
    static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;

    static constexpr unsigned long long i1 =
        atcoder_modint::internal::inv_gcd(MOD2 * MOD3, MOD1).second;
    static constexpr unsigned long long i2 =
        atcoder_modint::internal::inv_gcd(MOD1 * MOD3, MOD2).second;
    static constexpr unsigned long long i3 =
        atcoder_modint::internal::inv_gcd(MOD1 * MOD2, MOD3).second;

    auto c1 = convolution<MOD1>(a, b);
    auto c2 = convolution<MOD2>(a, b);
    auto c3 = convolution<MOD3>(a, b);

    vector<long long> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        unsigned long long x = 0;
        x += (c1[i] * i1) % MOD1 * M2M3;
        x += (c2[i] * i2) % MOD2 * M1M3;
        x += (c3[i] * i3) % MOD3 * M1M2;
        // B = 2^63, -B <= x, r(real value) < B
        // (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
        // r = c1[i] (mod MOD1)
        // focus on MOD1
        // r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
        // r = x,
        //     x - M' + (0 or 2B),
        //     x - 2M' + (0, 2B or 4B),
        //     x - 3M' + (0, 2B, 4B or 6B) (without mod!)
        // (r - x) = 0, (0)
        //           - M' + (0 or 2B), (1)
        //           -2M' + (0 or 2B or 4B), (2)
        //           -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
        // we checked that
        //   ((1) mod MOD1) mod 5 = 2
        //   ((2) mod MOD1) mod 5 = 3
        //   ((3) mod MOD1) mod 5 = 4
        long long diff =
            c1[i] - atcoder_modint::internal::safe_mod((long long)(x), (long long)(MOD1));
        if (diff < 0) diff += MOD1;
        static constexpr unsigned long long offset[5] = {
            0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
        x -= offset[diff % 5];
        c[i] = x;
    }

    return c;
}

}  // namespace atcoder_convolution

using mint = atcoder_modint::modint998244353;
using namespace atcoder_convolution;

ostream& operator << (ostream &os, const mint &p) { os << p.val(); return os; }

void solve() {
    string s, t; cin >> s >> t;
    int k; cin >> k;
    reverse(all(t));
    int n = s.size(), m = t.size();
    vector<mint> cnt(n + m - 1, 0);
    rep (ch, 0, 8) {
        vector<mint> a(n, 0), b(m, 0);
        rep (i, 0, n) if (s[i] - 'a' == ch) a[i] = 1;
        rep (i, 0, m) if (t[i] - 'a' == ch) b[i] = 1;
        auto c = convolution(a, b);
        rep (i, 0, n + m - 1) cnt[i] += c[i];
    }
    // rep (i, m - 1, n + m - 2) cout << cnt[i] << ' ';
    mint ans = 1, inv = mint(m).inv();
    rep (i, m - 1, m - 1 + n - m + 1) if (cnt[i] != m) {
        ans *= 1 - (cnt[i] * inv).pow(k);
    }
    cout << ans << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}
```
:::


### K. King's Challenge
---
#### 題目摘要
求$\frac{n!}{(n-k)!}$去掉後綴0的後5位數

#### 想法
$設\text {fact}(n)=n!去掉後綴0後\bmod 10^5，F(n)=\prod_{i=1, i\not\mid 2, i\not\mid 5}^{n}i$，則能寫出遞迴式$\text {fact}(n)=\frac{\text {fact}(\lfloor\frac{n}{2}\rfloor)\times \text {fact}(\lfloor\frac{n}{5}\rfloor)}{\text {fact}(\lfloor\frac{n}{10}\rfloor)}\times 2^{\lfloor\frac{n}{2}\rfloor-\lfloor\frac{n}{5}\rfloor}\times F(n)$
首先，先處理$F(n)$，而$F(n)$有循環節，所以可以先預處理完。
再來看$\text {fact}(n)$，最棘手的就是除法，若$\text {fact}(n)$不是2或5的倍數，就能用歐拉定理解決，因此在處理$\text {fact}(n)$時不要把二的冪次方乘進去，而是計算冪次方個數並最後再來處理。
最後，求出來的是$\bmod 10^5$的答案，但答案是能有前綴0的，所以只要在$k$夠小時暴力做就好

:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long loli;
typedef pair<int, int> pii;
typedef pair<loli, loli> pll;
#define F first
#define S second

const loli mod=100000, phi=40000;
loli f[100005];
map<loli, pll> dp;

loli fpow(loli x, loli k){
    loli res=1;
    while(k){
        if (k&1) res=res*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return res;
}

pll solve(loli n){
    if (dp.find(n)!=dp.end()) return dp[n];
    loli cnt2=n/2, cnt5=n/5, cnt10=n/10;
    auto [res2, two2]=solve(n/2);
    auto [res5, two5]=solve(n/5);
    auto [res10, two10]=solve(n/10);
    loli res=res2*res5%mod*fpow(res10, phi-1)%mod;
    res=res*f[n%mod]%mod;
    loli two=two2+two5-two10+(cnt2-cnt5);
    return dp[n]={res, two};
}

void _solve(){
    loli n, k;
    scanf("%lld%lld", &n, &k);
    if (k<=100){
        loli tmp=1;
        loli cnt2=0, cnt5=0;
        for(loli i=n-k+1;i<=n;i++){
            loli t=i;
            while(t%10==0) t/=10;
            while(t%2==0) cnt2++, t/=2;
            while(t%5==0) cnt5++, t/=5;
            tmp*=t;
            if (tmp>mod) break;
        }
        if (tmp<mod){
            if (cnt2>cnt5){
                cnt2-=cnt5;
                if (cnt2<=16){
                    tmp<<=cnt2;
                    if (tmp<mod){
                        printf("%lld\n", tmp);
                        return;
                    }
                }
            }else{
                cnt5-=cnt2;
                if (cnt5<=7){
                    for(int i=0;i<cnt5;i++) tmp*=5LL;
                    if (tmp<mod){
                        printf("%lld\n", tmp);
                        return;
                    }
                }
            }
        }
        
    }
    pll x=solve(n);
    pll y=solve(n-k);
    loli ans=x.F*fpow(y.F, phi-1)%mod;
    ans=ans*fpow(2LL, x.S-y.S)%mod;
    int d=0;
    int p=1;
    while(p<=ans) d++, p*=10;
    for(int i=0;i<5-d;i++) printf("0");
    printf("%lld\n", ans);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    scanf("%d", &_t);
    f[0]=1;
    for(loli i=1;i<=100000;i++){
        f[i]=f[i-1];
        if ((i%2==0)||(i%5==0)) continue;
        f[i]*=i;
        f[i]%=mod;
    }
    dp[0]={1, 0};
    while(_t--) _solve();
}
```
:::

### L. The Bag of Forgotten Coins
---
#### 題目大綱

#### 想法

:::spoiler 實作
```cpp=

```
:::

### M. The Tale of Professor Alya and the H-Index
---
#### 題目大綱

#### 想法

:::spoiler 實作
```cpp=

```
:::
