結果

問題 No.2164 Equal Balls
ユーザー 👑 NachiaNachia
提出日時 2024-04-26 18:14:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,110 ms / 5,000 ms
コード長 22,788 bytes
コンパイル時間 2,557 ms
コンパイル使用メモリ 123,624 KB
実行使用メモリ 12,560 KB
最終ジャッジ日時 2024-04-26 18:15:30
合計ジャッジ時間 50,734 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 46 ms
6,940 KB
testcase_09 AC 37 ms
6,944 KB
testcase_10 AC 20 ms
6,940 KB
testcase_11 AC 95 ms
6,940 KB
testcase_12 AC 49 ms
6,940 KB
testcase_13 AC 37 ms
6,944 KB
testcase_14 AC 44 ms
6,940 KB
testcase_15 AC 90 ms
6,976 KB
testcase_16 AC 47 ms
6,940 KB
testcase_17 AC 11 ms
6,940 KB
testcase_18 AC 59 ms
6,940 KB
testcase_19 AC 103 ms
7,052 KB
testcase_20 AC 52 ms
6,940 KB
testcase_21 AC 10 ms
6,940 KB
testcase_22 AC 10 ms
6,944 KB
testcase_23 AC 1,092 ms
6,940 KB
testcase_24 AC 644 ms
7,452 KB
testcase_25 AC 1,000 ms
6,944 KB
testcase_26 AC 255 ms
6,944 KB
testcase_27 AC 756 ms
8,376 KB
testcase_28 AC 789 ms
8,548 KB
testcase_29 AC 361 ms
6,940 KB
testcase_30 AC 763 ms
7,524 KB
testcase_31 AC 1,400 ms
6,944 KB
testcase_32 AC 857 ms
8,360 KB
testcase_33 AC 722 ms
6,940 KB
testcase_34 AC 926 ms
6,944 KB
testcase_35 AC 193 ms
6,944 KB
testcase_36 AC 1,733 ms
9,472 KB
testcase_37 AC 1,622 ms
6,944 KB
testcase_38 AC 2,065 ms
12,304 KB
testcase_39 AC 2,082 ms
12,304 KB
testcase_40 AC 2,095 ms
12,560 KB
testcase_41 AC 2,086 ms
12,432 KB
testcase_42 AC 2,071 ms
12,300 KB
testcase_43 AC 2,049 ms
12,432 KB
testcase_44 AC 2,064 ms
12,292 KB
testcase_45 AC 2,056 ms
12,432 KB
testcase_46 AC 2,072 ms
12,304 KB
testcase_47 AC 2,068 ms
12,308 KB
testcase_48 AC 2,110 ms
12,304 KB
testcase_49 AC 1,881 ms
6,944 KB
testcase_50 AC 1,914 ms
6,940 KB
testcase_51 AC 1,940 ms
6,940 KB
testcase_52 AC 1,939 ms
6,940 KB
testcase_53 AC 1,922 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "Main.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#line 1 "nachia\\atcoder\\convolution.hpp"


#line 4 "nachia\\atcoder\\convolution.hpp"
#include <array>
#include <cassert>
#include <type_traits>
#line 1 "nachia\\atcoder\\internal_bit.hpp"



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

namespace atcoder {

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
}

}  // namespace internal

}  // namespace atcoder


#line 1 "nachia\\atcoder\\static_modint.hpp"



#line 1 "nachia\\atcoder\\internal_modint_base.hpp"



#line 1 "nachia\\atcoder\\internal_type_traits.hpp"



#line 5 "nachia\\atcoder\\internal_type_traits.hpp"
#include <numeric>
#line 7 "nachia\\atcoder\\internal_type_traits.hpp"

namespace atcoder {

namespace internal {

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

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

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

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

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

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

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

#else

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

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

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

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

#endif

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

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

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

}  // namespace internal

}  // namespace atcoder


#line 7 "nachia\\atcoder\\internal_modint_base.hpp"

namespace atcoder {

namespace internal {

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

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

}  // namespace internal

}  // namespace atcoder


#line 1 "nachia\\atcoder\\internal_math.hpp"



#line 5 "nachia\\atcoder\\internal_math.hpp"

namespace atcoder {

namespace internal {

// @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;
}

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

    // @param m `1 <= m`
    barrett(unsigned int m) : _m(m), im((u64)(-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 {
        u64 z = a;
        z *= b;
#ifdef _MSC_VER
        u64 x;
        _umul128(z, im, &x);
#else
        u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
#endif
        unsigned int v = (unsigned int)(z - x * _m);
        if(_m <= v) v += _m;
        return v;
    }
};

// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
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, 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;
    for(long long a : {2, 7, 61}){
        long long t = d, 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 std::pair<long long, long long> inv_gcd(long long a, long long b){
    a = safe_mod(a, b);
    if(a == 0) return {b, 0};

    long long s = b, t = a, m0 = 0, m1 = 1;

    while(t){
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}

// @param m must be prime
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(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);

}  // namespace internal

}  // namespace atcoder


#line 10 "nachia\\atcoder\\static_modint.hpp"

namespace atcoder {

template <int m, std::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.w = v;
        return x;
    }

    static_modint() : w(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();
        w = (unsigned int)(x);
    }
    template <class T, internal::is_unsigned_int_t<T>* = nullptr>
    static_modint(T v){
        w = (unsigned int)(v % umod());
    }
    static_modint(bool v){ w = ((unsigned int)(v) % umod()); }

    unsigned int val() const { return w; }

    mint& operator++(){
        w++;
        if(w == umod()) w = 0;
        return *this;
    }
    mint& operator--(){
        if(w == 0) w = umod();
        w--;
        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){
        w += rhs.w;
        if(w >= umod()) w -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs){
        w -= rhs.w;
        if(w >= umod()) w += umod();
        return *this;
    }
    mint& operator*=(const mint& rhs){
        unsigned long long z = w;
        z *= rhs.w;
        w = (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(w);
            return pow(umod() - 2);
        } else {
            auto eg = internal::inv_gcd(w, 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.w == rhs.w; }
    friend bool operator!=(const mint& lhs, const mint& rhs){ return lhs.w != rhs.w; }

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

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;

namespace internal {

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

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

}  // namespace internal

}  // namespace atcoder


#line 11 "nachia\\atcoder\\convolution.hpp"

namespace atcoder {

namespace internal {

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

    std::array<mint, std::max(0, rank2-1)> rate2;
    std::array<mint, std::max(0, rank2-1)> irate2;

    std::array<mint, std::max(0, rank2-2)> rate3;
    std::array<mint, std::max(0, rank2-2)> 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];
        }
        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, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a){
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static const fft_info<mint> info;

    int len = 0;
    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 {
            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, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a){
    int n = int(a.size());
    int h = internal::ceil_pow2(n);

    static const fft_info<mint> info;
    constexpr int MOD = mint::mod();

    int len = h;
    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)(MOD + l.val() - r.val()) * irot.val();
                }
                if(s+1 != (1<<(len-1))) irot *= info.irate2[bsf(~(unsigned int)(s))];
            }
            len--;
        } else {
            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((MOD + a2 - a3) * iimag.val()).val();

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

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

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

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

    using mint = static_modint<mod>;
    std::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(std::move(a2), std::move(b2));
    std::vector<T> c(n+m-1);
    for(int i=0; i<n+m-1; i++) c[i] = c2[i].val();
    return c;
}

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

    static constexpr u64 MOD1 = 754974721, MOD2 = 167772161, MOD3 = 469762049;
    static constexpr u64 M2M3 = MOD2 * MOD3, M1M3 = MOD1 * MOD3, M1M2 = MOD1 * MOD2;
    static constexpr u64 M1M2M3 = MOD1 * MOD2 * MOD3;

    static constexpr u64 i1 = internal::inv_gcd(M2M3, MOD1).second;
    static constexpr u64 i2 = internal::inv_gcd(M1M3, MOD2).second;
    static constexpr u64 i3 = internal::inv_gcd(M1M2, MOD3).second;

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

    std::vector<long long> c(n+m-1);
    for(int i=0; i<n+m-1; i++){
        u64 x = 0;
        x += (c1[i] * i1) % MOD1 * M2M3;
        x += (c2[i] * i2) % MOD2 * M1M3;
        x += (c3[i] * i3) % MOD3 * M1M2;
        long long diff = c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
        if(diff < 0) diff += MOD1;
        static constexpr u64 offset[5] = { 0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
        x -= offset[diff % 5];
        c[i] = x;
    }

    return c;
}

}  // namespace atcoder


#line 3 "nachia\\fps\\many-polynomial-product.hpp"

namespace nachia{

template<class Modint>
std::vector<Modint> ProductOfManyPolynomials(std::vector<std::vector<Modint>> poly){
    if(poly.empty()) return {Modint(1)};
    for(auto& p : poly) while(!p.empty() && p.back().val() == 0) p.pop_back();
    for(auto& p : poly) if(p.size() == 0) return {Modint(0)};
    for(size_t K=16; poly.size() != 1; K*=2){
        size_t pos = poly.size();
        for(size_t i=0; i<poly.size(); i++){
            if(pos == poly.size() || poly[pos].size() + poly[i].size() - 1 > K){ pos = i; continue; }
            poly[pos] = atcoder::convolution(poly[pos], poly[i]);
            std::swap(poly[i--], poly.back());
            poly.pop_back();
        }
    }
    return std::move(poly[0]);
}

} // namespace nachia
#line 3 "nachia\\math\\combination.hpp"

namespace nachia{

template<class Modint>
class Comb{
private:
    std::vector<Modint> F;
    std::vector<Modint> iF;
public:
    void extend(int newN){
        int prevN = (int)F.size() - 1;
        if(prevN >= newN) return;
        F.resize(newN+1);
        iF.resize(newN+1);
        for(int i=prevN+1; i<=newN; i++) F[i] = F[i-1] * Modint::raw(i);
        iF[newN] = F[newN].inv();
        for(int i=newN; i>prevN; i--) iF[i-1] = iF[i] * Modint::raw(i);
    }
    Comb(int n = 1){
        F.assign(2, Modint(1));
        iF.assign(2, Modint(1));
        extend(n);
    }
    Modint factorial(int n) const { return F[n]; }
    Modint invFactorial(int n) const { return iF[n]; }
    Modint invOf(int n) const { return iF[n] * F[n-1]; }
    Modint comb(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return F[n] * iF[r] * iF[n-r];
    }
    Modint invComb(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return iF[n] * F[r] * F[n-r];
    }
    Modint perm(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return F[n] * iF[n-r];
    }
    Modint invPerm(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return iF[n] * F[n-r];
    }
    Modint operator()(int n, int r) const { return comb(n,r); }
};

} // namespace nachia
#line 8 "Main.cpp"

using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using Modint = atcoder::static_modint<998244353>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int Z = 700;
    nachia::Comb<Modint> comb(Z);
    int n, m; cin >> n >> m;
    vector<int> A(n), B(n);
    rep(i,n) cin >> A[i];
    rep(i,n) cin >> B[i];
    vector<vector<Modint>> Comb(m, vector<Modint>(2*Z+1, 1));
    auto Diff = [&](int a, int b, int d) -> Modint { return comb.comb(a+b, a+d); };
    rep(i,n) rep(d,2*Z+1) Comb[i%m][d] *= Diff(A[i], B[i], d-Z);
    auto anss = nachia::ProductOfManyPolynomials(std::move(Comb));
    auto ans = anss[Z * m];
    cout << ans.val() << '\n';
    return 0;
}
0