# C. Circular Mirror

Đề bài : https://codeforces.com/contest/1725/problem/C

Nhận xét : chỉ nên quan tâm những thằng được cặp lại với nhau, tức là 2 thằng nó là đường kính, sau đó đóng tổ hợp vào là được, khá đơn giản.

Code :
:::spoiler

#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i) 
#define rev(i, a, b) for (int i = (a); i >= (b); --i) 
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

using namespace std; 
const int mxn = 3e5 + 5;
const ll MOD = 998244353;
int n, m;
ll fac[mxn];

ll pow_mod(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if (b&1) (res *= a)%=MOD;
        b >>= 1;
        (a *= a)%=MOD;
    }
    return res;
}

ll C(ll n, ll k)
{
    if (k > n) return 0;
    return fac[n]*pow_mod(fac[n - k], MOD - 2)%MOD*pow_mod(fac[k], MOD - 2)%MOD;
}

ll d[mxn];
int main(){
    //freopen("H:\\file_txt\\input.txt", "r", stdin);
    //freopen("H:\\file_txt\\output.txt", "w", stdout);

    fac[0] = 1;
    rep(i, 1, mxn - 5) fac[i] = fac[i - 1]*(ll)i%MOD;

    scanf("%d%d", &n, &m);

    ll sum = 0;
    set<ll> pos;
    rep(i, 1, n)
    {
        //cin >> as[i];
        scanf("%lli", &d[i]);
        pos.insert(sum);
        sum += d[i];
    }

    ll len = sum;
    if (len&1)
    {
        cout << pow_mod(m, n);
        return 0;
    }

    sum = 0;
    ll total = 0;
    rep(i, 1, n)
    {
        if (pos.find(sum + len/2) != pos.end())
            ++total;   
        sum += d[i];
    }

    ll res = 0;
    rep(i, 0, total)
    {
        ll remain = total - i;
        ll color = m - i;
        ll de = n - total*2;
        res += C((ll)m, i)*fac[i]%MOD*C(total, (ll)i)%MOD*pow_mod(C(color, 2ll), remain)%MOD*pow_mod(2ll, remain)%MOD*pow_mod(color, de)%MOD;
        res %= MOD;
    }
    cout << res;
}

:::