#1036056 (C++23) No.3004 ヤング図形

• 問題: No.3004 ヤング図形
• ユーザー: hitonanode
• 提出日時: 2025-01-17 23:06:37
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 53 ms / 4,000 ms
• コード長: 63,063 bytes
• コンパイル時間: 5,080 ms
• コンパイル使用メモリ: 229,588 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2025-01-17 23:06:45
• 合計ジャッジ時間: 4,061 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 25

ソースコード

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); }
template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }
template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }
template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }
template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }
template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }

template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);

template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; }
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl
#define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr)
#else
#define dbg(x) ((void)0)
#define dbgif(cond, x) ((void)0)
#endif


#include <cassert>
#include <iostream>
#include <set>
#include <vector>

template <int md> struct ModInt {
    using lint = long long;
    constexpr static int mod() { return md; }
    static int get_primitive_root() {
        static int primitive_root = 0;
        if (!primitive_root) {
            primitive_root = [&]() {
                std::set<int> fac;
                int v = md - 1;
                for (lint i = 2; i * i <= v; i++)
                    while (v % i == 0) fac.insert(i), v /= i;
                if (v > 1) fac.insert(v);
                for (int g = 1; g < md; g++) {
                    bool ok = true;
                    for (auto i : fac)
                        if (ModInt(g).pow((md - 1) / i) == 1) {
                            ok = false;
                            break;
                        }
                    if (ok) return g;
                }
                return -1;
            }();
        }
        return primitive_root;
    }
    int val_;
    int val() const noexcept { return val_; }
    constexpr ModInt() : val_(0) {}
    constexpr ModInt &_setval(lint v) { return val_ = (v >= md ? v - md : v), *this; }
    constexpr ModInt(lint v) { _setval(v % md + md); }
    constexpr explicit operator bool() const { return val_ != 0; }
    constexpr ModInt operator+(const ModInt &x) const {
        return ModInt()._setval((lint)val_ + x.val_);
    }
    constexpr ModInt operator-(const ModInt &x) const {
        return ModInt()._setval((lint)val_ - x.val_ + md);
    }
    constexpr ModInt operator*(const ModInt &x) const {
        return ModInt()._setval((lint)val_ * x.val_ % md);
    }
    constexpr ModInt operator/(const ModInt &x) const {
        return ModInt()._setval((lint)val_ * x.inv().val() % md);
    }
    constexpr ModInt operator-() const { return ModInt()._setval(md - val_); }
    constexpr ModInt &operator+=(const ModInt &x) { return *this = *this + x; }
    constexpr ModInt &operator-=(const ModInt &x) { return *this = *this - x; }
    constexpr ModInt &operator*=(const ModInt &x) { return *this = *this * x; }
    constexpr ModInt &operator/=(const ModInt &x) { return *this = *this / x; }
    friend constexpr ModInt operator+(lint a, const ModInt &x) { return ModInt(a) + x; }
    friend constexpr ModInt operator-(lint a, const ModInt &x) { return ModInt(a) - x; }
    friend constexpr ModInt operator*(lint a, const ModInt &x) { return ModInt(a) * x; }
    friend constexpr ModInt operator/(lint a, const ModInt &x) { return ModInt(a) / x; }
    constexpr bool operator==(const ModInt &x) const { return val_ == x.val_; }
    constexpr bool operator!=(const ModInt &x) const { return val_ != x.val_; }
    constexpr bool operator<(const ModInt &x) const {
        return val_ < x.val_;
    } // To use std::map<ModInt, T>
    friend std::istream &operator>>(std::istream &is, ModInt &x) {
        lint t;
        return is >> t, x = ModInt(t), is;
    }
    constexpr friend std::ostream &operator<<(std::ostream &os, const ModInt &x) {
        return os << x.val_;
    }

    constexpr ModInt pow(lint n) const {
        ModInt ans = 1, tmp = *this;
        while (n) {
            if (n & 1) ans *= tmp;
            tmp *= tmp, n >>= 1;
        }
        return ans;
    }

    static constexpr int cache_limit = std::min(md, 1 << 21);
    static std::vector<ModInt> facs, facinvs, invs;

    constexpr static void _precalculation(int N) {
        const int l0 = facs.size();
        if (N > md) N = md;
        if (N <= l0) return;
        facs.resize(N), facinvs.resize(N), invs.resize(N);
        for (int i = l0; i < N; i++) facs[i] = facs[i - 1] * i;
        facinvs[N - 1] = facs.back().pow(md - 2);
        for (int i = N - 2; i >= l0; i--) facinvs[i] = facinvs[i + 1] * (i + 1);
        for (int i = N - 1; i >= l0; i--) invs[i] = facinvs[i] * facs[i - 1];
    }

    constexpr ModInt inv() const {
        if (this->val_ < cache_limit) {
            if (facs.empty()) facs = {1}, facinvs = {1}, invs = {0};
            while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2);
            return invs[this->val_];
        } else {
            return this->pow(md - 2);
        }
    }
    constexpr ModInt fac() const {
        while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2);
        return facs[this->val_];
    }
    constexpr ModInt facinv() const {
        while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2);
        return facinvs[this->val_];
    }
};
template <int md> std::vector<ModInt<md>> ModInt<md>::facs = {1};
template <int md> std::vector<ModInt<md>> ModInt<md>::facinvs = {1};
template <int md> std::vector<ModInt<md>> ModInt<md>::invs = {0};

using mint = ModInt<998244353>;


#include <cassert>
#include <fstream>
#include <vector>

// 結合法則が成立する要素の列について連続部分列の積を前計算を利用し高速に求める
template <class S, S (*op)(S, S), S (*e)(), S (*getter)(long long), int Bucket>
struct product_embedding {
    std::vector<S> pre_; // pre_[i] = S[i * Bucket] * ... * S[(i + 1) * Bucket - 1]

    product_embedding(std::vector<S> pre) : pre_(pre) {}

    S prod(long long l, long long r) { // S[l] * ... * S[r - 1]
        assert(0 <= l);
        assert(l <= r);
        assert(r <= (long long)Bucket * (long long)pre_.size());

        if (r - l <= Bucket) {
            S ret = e();
            while (l < r) ret = op(ret, getter(l++));
            return ret;
        }

        long long lb = (l + Bucket - 1) / Bucket, rb = r / Bucket;
        S ret = e();
        for (long long i = l; i < lb * Bucket; ++i) ret = op(ret, getter(i));
        for (int i = lb; i < rb; ++i) ret = op(ret, pre_[i]);
        for (long long i = rb * Bucket; i < r; ++i) ret = op(ret, getter(i));
        return ret;
    }

    static void prerun(std::string filename, long long upper_lim) {
        std::ofstream ofs(filename);

        long long cur = 0;
        long long num_bucket = (upper_lim + Bucket - 1) / Bucket;

        ofs << "({";
        while (num_bucket--) {
            S p = e();
            for (int t = 0; t < Bucket; ++t) { p = op(p, getter(cur++)); }
            ofs << p;
            if (num_bucket) ofs << ",";
        }
        ofs << "});";
    }
};
using S = int;
constexpr S md = 998244353;
S op(S l, S r) { return (long long)l * r % md; }
S getter(long long i) { return i + 1; }
S e() { return 1; }
using PE = product_embedding<S, op, e, getter, 20000>;


int main() {
    // PE::prerun("tmp.txt", 1e8); // -> copy & paste the content of dumped file

    PE pe({766786010,675455087,481678967,855858616,447542002,587362434,422910297,901572009,95284402,848409693,360541519,41926921,503320185,389420383,571815372,707840256,688064559,173755974,108051938,226076856,961534977,704503969,191165135,580778500,132973996,244358760,217769430,40198809,78231632,958127181,185083882,349311000,783607778,920073001,724377896,633957890,554307374,96999616,567837278,673886192,127968770,646961668,119915167,695799969,85502350,350828964,569294710,895672389,276730107,135431778,517029230,644421126,560765662,239673153,868011067,446104284,614858157,973457746,247969500,261549172,252554113,276651138,743540621,252897468,499307243,662400388,762863116,279583823,540397646,536604539,370206099,691546625,589970773,891021004,930322285,415878703,243741443,816699997,785199201,670562121,273637442,603296890,422869557,660136066,300082396,943717924,547093182,884894442,922988005,518104742,755844643,821461286,469471146,15540778,748713961,333840425,700228745,549457802,109864625,155623348,306106124,221853464,447804517,169351238,861292401,965362534,262718538,707719469,497771417,261581285,59055895,667915266,579543002,328877680,302499610,734822978,677685641,736355943,499800402,875257143,488234065,251182300,191284517,756705941,249341253,73216478,898821113,575665518,806776679,382037704,889432230,59483312,223180850,795391801,224555774,382069394,646842239,186159672,33891233,672677738,853230158,604124257,878140729,610696355,314151609,711937990,890776542,197429905,379285454,822372014,525017289,419148795,761793021,13019964,875775529,141792284,769464040,220906683,249645868,921296516,315669118,151089162,724468067,696854085,981859526,628376023,115750119,776368787,961796646,201788370,796747222,296867587,444989342,871498928,548826871,163823818,238001713,560399164,892070297,695309050,143625327,78905406,295176361,54612209,557526909,857475413,850090072,346277862,892267865,125430433,74717591,304487681,578915236,68580147,507770986,729050262,536717184,369633851,885404470,108411355,434692453,54415669,795116927,942381401,870955183,844898481,786691904,309904923,695420982,507781238,539311381,122749048,297996550,649121986,536456383,944311993,791598745,259461850,102722563,469652294,189898687,538613411,164469085,898059577,431695557,390936585,820897147,869813534,958899110,933984027,80464827,888973097,724454227,736821750,175474806,311715016,560617791,711135672,38722253,44373383,265468553,248887895,387450476,306676825,328626205,983324320,471813602,983809974,594386326,603514519,195228237,626381661,530446139,317331428,495761860,88466328,315274046,290248396,76738221,919227779,215549013,760043849,206469150,483009407,539335363,455322541,773583599,332686369,275346407,318346676,620641481,841503652,90935073,280280976,968760365,617757682,711976719,799611420,789408240,363039043,524005,635827095,513413290,806044668,116178649,225227310,246127666,467127088,685525187,689168766,196795923,976973115,68507657,707351156,670784554,984238536,326952108,457020110,582630468,454924230,370222297,68445473,350497808,685413196,717009657,848664882,437583180,853585865,763868302,293800124,294612743,850291340,809262744,27780542,946061500,671372106,512844794,978750784,623536524,616523092,178624764,700414391,376650268,46465009,305266863,352475101,30766969,917365456,693921186,26433069,690149781,825456662,402606444,669998396,337507598,972629246,894613417,675766598,299125819,48214033,446871161,957475867,286242879,157096833,33111805,805718239,592564979,15005194,937473938,668750025,504574540,562960702,471793122,749915046,72023278,112826987,114239667,580727262,804754952,977165049,50537821,677302279,402984392,910243323,313966982,818212062,401789647,906071219,321342435,529608844,184100762,218545181,280325117,928562901,744158024,295879968,70049780,397905731,291694368,636698186,732520821,560425406,288859114,685189946,821998962,679418390,619021926,161555476,527892549,258246570,153212801,277095458,55291421,579937616,545830993,842051776,106416807,268941295,430832284,338271564,454441821,807668644,344652509,460604181,539880738,743358476,975081409,825228621,288770534,843837281,778469509,958116647,930354160,206781721,537928095,319532171,854542135,517234059,503901350,515659360,518345183,584446163,941607524,732957313,63123663,65468357,96782758,193278712,413071002,862050987,205659552,685313560,566433115,653224436,170427956,262409331,961443099,604610310,694161065,450709835,907700923,872445054,978951105,490356534,106508327,777921056,775615745,539756911,234271181,642084222,699360956,333070221,816756310,485625297,630808649,621284840,155960924,808791799,415645126,596413735,618197340,224085319,551214095,910040718,220323000,878685889,412497844,652071960,406359487,666673159,724905369,181027401,866245377,302637797,867679020,206130055,486531934,768228431,939545523,7288069,242086045,637458240,130077776,723401102,207908750,921927982,393219310,994129311,673270193,853268408,357594758,165048963,118691604,498528661,737591331,662854186,786732273,145815817,221922182,99877859,633486445,893006085,844314361,173809460,900390019,489273575,938091959,311927429,127469680,497377803,989422777,857879045,785068508,700565049,227193450,413908417,804361304,834265470,832312546,415507010,802790776,603434398,369487867,37513091,92976531,551384794,736264996,529191168,570546083,720693580,234416321,307612267,775204521,818745385,454293819,68960319,869928906,224519008,795569747,902933516,266642317,43009228,698562797,727699079,424376291,311183993,74965690,373739322,913466064,395958628,841684039,65383884,218569458,752493943,424690368,662290142,364209941,340440453,590127612,641345932,629728303,576110337,218943128,247783754,5226801,576520626,944736063,520649926,11094435,539206928,100211297,325195742,11237908,267720125,25942959,611658612,985981381,750799781,342963262,806020182,715389367,44127224,745894436,84285735,327538230,970186810,454003537,780072086,546594180,471571445,602941704,360134931,208107079,143383125,360127111,274697626,553360391,526856880,15913949,617437860,745272274,402753913,218460831,345100466,431104606,832946867,441030230,655910822,256146531,263416821,854466433,885172188,618566562,919315389,317555234,209107378,846735206,223626187,631835376,216175031,304720494,460594694,496492828,269041713,380663640,937092591,508836019,390470452,863182506,638055391,172082838,547942511,500317534,601253898,858901550,780998173,258532652,826219143,277202858,374081174,432578062,488166428,667362934,194614287,550867390,905547016,136364378,226938830,962860791,320860532,734359984,497208933,602510420,19716849,941628849,670090374,764491833,340901422,180234677,215260104,200154075,741484640,122306750,346010628,597239071,539150882,902334061,578779827,339363103,718860736,57663142,953820245,395770626,517548431,895071364,308156256,610218675,578713738,463596127,69136630,295010176,959388539,167823604,595703473,805547475,272986152,500992375,982036543,93097120,710524432,617222489,180018038,230190835,229775497,326987998,688255856,233894025,911929576,271361025,296196724,451601709,485333449,48513728,247249861,857197954,126352558,21990385,138470763,882178020,746221150,693948059,809086661,511675302,726472517,872511293,21057242,515568763,473616902,324430574,167585078,451480629,516710628,196146170,782315535,621019682,934696775,289265862,684744381,341801835,823118029,782179529,950937349,117779780,646519979,25388416,919304991,284083782,62036916,620693826,293654886,742984567,932765314,686298637,297136745,58218172,723666858,67601046,582185523,443156685,468718594,86670530,472085333,492969815,733358213,923853163,132427798,153455611,75048439,506918620,15004868,352267915,442321211,193735550,883746047,576234991,521334421,190357462,185307794,355189958,597880285,481022339,698232322,403599444,782238492,904872641,638361509,837151031,578379411,490167504,491066581,740685806,182996158,364863500,743602844,429749683,836584675,820480247,511621216,629225643,414527506,648379563,25780754,749870392,922314661,36945308,507497918,529926093,340035337,815306915,874537639,280631970,400519391,959281671,143349177,848757384,142015898,41089328,846789931,411048676,613274994,501034734,197118284,175725529,348276720,85279082,514601059,766328052,861331919,407331615,535979539,531161857,225594504,284275511,327586673,248304023,815042052,353393987,263689045,740660139,509952435,687492950,214355172,55914494,120037238,546638333,384206454,746073093,400863447,637927561,522506513,104633517,520879913,283737171,614804666,750379799,669843206,187868342,62396748,378018532,30093641,725502265,431481231,766985176,17145784,641058320,889243850,889503208,649422533,351050704,852645412,52873243,781514559,501397594,987433365,596629095,931416355,371935861,217391507,136392777,103012672,614780373,496570486,100709689,889427286,138155046,818648333,53830297,53926935,370170160,639623900,41269613,745493786,830654863,706697744,911353279,84237228,47695463,429875441,837755604,303813353,576348774,790900633,863811997,954286293,388703730,223873344,859914488,268008224,96253484,955816479,185023933,261112481,110242712,827578789,72407170,310092236,605615086,919440432,175143661,325175434,129942200,143415014,266186688,95751936,529143975,410590219,958094042,740760650,660173150,800329654,290496972,656144263,179792847,532815132,781403679,231193923,883246205,788627558,465463456,371738542,927670272,55354208,187573526,880625508,479779369,173422814,414056653,472471467,888738823,235431838,967196645,449815340,321313673,622970520,221384002,556028864,47819921,547859050,472419461,525744089,946254236,31256222,319115225,914148294,804834454,897823149,464809909,451399306,928036426,825382439,48203394,569071550,684593046,941144709,390406382,930491691,333715812,188021846,373989013,342545923,155695295,921267740,620760848,36302318,817210295,591616523,443546376,191609078,12396234,193478131,506697162,652987056,666921593,6638494,302337938,964555455,994598375,529082915,554230558,897316522,312951876,520640701,106613914,596492134,276433314,790136567,264630166,194861565,112372646,265307775,6402574,451515308,729173148,780316486,126628512,336905267,416273521,319128892,781856970,918291826,926964310,685186595,224547061,173491623,939032002,182993072,235356977,591012336,634629675,343326573,596055083,838726229,699470194,600801982,631636712,889640301,168742018,799086125,747751271,630639539,199639814,702021289,562207319,343887791,992778667,502722565,973184522,551933518,861352357,449856557,149970668,5025366,45486425,491554192,309744818,696933735,473960222,411116896,241536221,325733589,628125360,87129980,282095315,292221907,441337141,722537250,72431633,207233751,128377153,976617628,896256176,970834315,433862615,536476507,843415480,254271958,238242182,305129744,206376362,285517434,406095898,540577736,243693493,9957052,610558606,754542326,232955553,542645710,618140288,905331586,946153823,419043928,602702419,656393443,370573532,17082704,335990176,952905785,183007059,782380660,915417259,898286900,256398777,469279414,415107917,470079766,839500541,424859600,75671480,271130969,65907529,483697981,542939413,415083669,281851224,893866496,374799924,648298776,960965145,945693221,788226096,609965177,443700938,648895853,854639635,435908203,132114373,884861319,30654051,850831334,930040892,686402254,724769429,460433651,233709581,4465636,832993101,766754765,993435069,91143745,89285730,775421564,101528114,535550235,934630944,467892407,482595878,641381011,834014150,913798768,393024438,61354763,602488358,335704520,88390237,708468432,432141460,9646840,148434555,39751289,970923806,514932881,757242637,243939478,624484236,306781769,455274560,236871898,671269475,161169779,60853608,400111730,822045266,365863937,82158115,885609974,608794358,852199614,963575664,972054200,487876617,347854640,487756853,515244203,312829609,253307460,156790289,792117592,275713425,479519309,497340164,305183360,339062504,500489616,893460575,654294035,130298630,766718293,907235957,426558353,695588993,16435276,938755268,652150676,456840306,277408960,491372731,270911419,480753932,8667701,734665111,342480683,309834107,436348038,513579891,132515528,456213893,139460324,176059066,326079465,558939556,478390069,461526989,946177055,645285765,313210296,578274017,205160980,775047041,781674771,131994211,884010933,621470758,167184910,303833198,362192838,889270251,261666917,266464257,835437189,141308481,305776973,801479889,858088323,742677840,887217,586990621,646040723,376437953,419035147,582593586,613812497,961433348,103454367,134316255,885615638,382586543,649679168,626135551,544577844,592840932,321068145,641833181,934987366,81122224,139071462,966002476,119807120,55859721,917319066,24352740,688371173,747324575,342339490,194367451,990430909,936000870,446999584,958666751,554433713,946217811,612306627,78838644,750644711,322507135,701886168,415942634,331373415,58797947,208091694,156799738,904396261,817074559,492480345,290353102,635918741,550540761,669548782,777692072,117829908,668174211,97618246,444311724,282335657,24252080,316655346,3824668,162927958,521081129,718976372,215565587,385494647,255415864,644665164,663720670,220842286,339339366,274530672,562015277,919009122,698527443,269510450,67752379,631364029,571569,552189622,594122586,152312388,346697307,890314000,295276433,334056975,564822527,979942230,862255595,743466582,965883321,738269830,297997497,35523103,334989165,427257985,534258459,557916825,115701785,1764834,42573993,729849413,607239048,368538543,115575066,826159170,259884843,98055882,990124296,377357211,626080089,805239920,141990165,263351977,193194774,537344836,414752547,413994174,983229467,978227625,96062309,394304772,774820967,656208613,514705851,168059065,279449210,503848806,981223454,515482814,291604029,301987123,524412510,227806245,41236551,250798277,53247890,794450392,333717032,257574535,238243540,356388368,903837593,629570463,534887315,796254380,857713576,29564407,740494579,674716681,236649034,342689642,549703925,488530613,203338299,397980264,624264520,1760210,930548270,34280005,392044960,439767558,920697105,593316069,791664739,133325219,402814571,35280108,276809468,878231335,951795527,627042359,44867902,749046571,35639041,919385461,545355011,272479102,329747674,461494103,416250508,334263480,951120079,139689224,646287784,485722553,922516369,180514741,696111629,373135433,608793049,713646369,142244120,816801532,504017094,987100390,63386710,508414770,504442973,486098626,112087292,726935457,139729698,594136377,330649978,996613163,598074956,423788472,280949315,7275307,698534644,551258369,261010394,964073478,865207466,814831400,551471293,335282265,178749130,170023439,47031986,970392631,719271048,949922931,856563044,401834072,208141061,130449778,687850465,933054609,350322688,801455420,731837842,941286955,389380110,962657808,407785442,750603042,273627522,224063007,262691075,61739872,637692574,351443461,863581201,884255620,26864879,650278052,352026753,742480607,542107019,517645962,471657281,397415808,63715979,66331257,875975917,87351106,831910451,85557910,859408594,697145017,38491081,930108733,609861150,447127848,20339832,273691494,593731330,485885220,145003220,403903404,415832446,835347473,326010521,234351142,962560650,919866300,985442799,877639458,339658891,248665772,432404487,259650432,97867489,305136912,984823947,740948151,348581262,48255290,857073347,935438892,224547124,856624910,564305289,447721116,484553829,371777043,138852923,271369155,78793396,931852175,915927921,48278183,10347139,911490221,230611731,103019993,516709016,407488469,774555673,357957904,735547032,200702015,362059845,639646486,119060090,71659183,442323058,214797424,321656142,613287913,317491450,260524086,321366937,69106600,176188458,342192444,773122894,791983639,468433492,803022821,410878191,815549106,435791119,757997332,486205712,794879096,132973277,356496130,506305270,865461373,557238624,19154971,691108958,653636713,241179842,590582086,630215723,181727215,888033037,488629531,205657243,142600452,934028110,369650490,627573664,930322068,624639762,153915540,934652378,362982170,521440742,794933664,973779595,811167229,846149354,497214013,46757564,636033098,266209165,64927691,10377872,796248102,505421273,520586210,69918508,784098086,521978530,915311832,158119915,397823166,644955641,579207000,968623343,102456109,421174327,15476248,96210962,906925650,457513824,640220466,328247829,352236325,626012365,547567962,621660487,994139869,355607810,789617768,424274453,145061239,828187112,9034643,200429474,851005872,867876546,119457034,509537614,751323106,143357562,684258932,957196447,630750279,767403596,254699754,267020149,234429061,439101995,118333318,39623913,824788351,646125104,992791141,112980381,167030920,504940199,921875415,374857858,937859895,415092661,119423442,360971121,442314451,946133230,232005528,129022124,332889741,638821567,798616105,896821152,911054641,87404704,952061299,398058747,542147311,236773253,737143962,500829000,427609623,249554228,159950422,301588755,32973356,891891916,209345869,156057028,772145874,705386484,307538669,368195364,876043548,662847620,709425805,978641018,314002951,183700252,638154132,856035208,931407096,533544696,711849109,30658204,285288842,849419078,622247369,268016064,344070182,724689739,78771993,568456132,918013745,34694979,277369694,431871486,816817178,778371003,857986113,938393426,715011433,218528368,76852942,221796260,431584363,233694743,430155320,496843147,625417680,682858181,176745133,18738351,584399114,690705667,921858666,370539471,80309376,53976064,444239616,718957603,285723260,498840748,900199800,269142999,953685213,923914949,777871453,159617738,380778200,496984832,946728552,337453459,91884940,837901720,968970527,169720920,198032417,551277639,367013161,443722070,667487696,53478998,85077718,774985026,174870516,676079372,196284101,354378844,824105250,267204384,951491797,681792795,221241508,706005820,477247207,327055200,431773741,816276021,686347652,814443928,891409049,560423223,869486469,481526640,345411035,917376416,830651726,773217121,82991479,340148419,116853989,89957572,741999324,205919710,51801197,80015375,338756769,662500362,971361426,809211952,215814774,168984372,696244425,597867833,462396731,561287907,57768075,799277097,393334296,869426438,172830810,622410838,268202863,988503086,420631375,400393109,382604329,150082268,930883766,676958419,293945972,198085036,287395655,650922525,58781634,286306434,972384652,172552914,924506265,825518422,582760277,23920354,756555113,466523659,403520519,811026790,995086289,650331949,394298114,691043404,552123158,737702232,603477656,971846302,179005708,730204270,363402683,41625982,622189697,510859611,139975235,717615077,891166722,380001944,41829960,292277677,218199430,286033857,696242613,983337178,701775647,452090861,165037610,493497306,844556399,452988021,602921478,982059045,751525727,340957303,75143264,870071734,67625530,78068151,347516699,138007010,754096956,92070846,292000559,674618660,972825058,642474484,184324826,107734646,315604232,279935911,311991163,83830648,404108640,895529698,904154386,696762806,310516340,494214349,853673232,993053923,565105179,29758762,860696471,856828745,573326174,3379446,118318940,350000028,163504593,170660512,602231576,791992220,884627005,926813387,721383463,575436631,50484998,149181244,413676449,275985160,371861906,272595197,894205008,942064138,491487510,607944680,919669275,835924904,337059381,690627643,433664247,839268000,639884654,393770517,690008306,458755971,792332259,687856915,561186542,501720407,245557398,695676569,776770795,389224302,686875102,849637879,197179956,87001728,686170901,68279692,473966537,722687555,466177824,342111538,804167499,756880969,925278756,65511091,330410892,895193161,571547697,106378576,482123629,103099978,762235865,530958283,948242387,195917585,460134056,577276869,632728608,337919330,253550114,807786118,71001929,951446267,516957823,707997868,387388975,528803976,583325069,242643342,764077509,252462171,547651321,676416360,54441143,991639907,622731377,451771050,884552656,182875897,592395385,81569877,775252825,388687155,259418756,707963877,230578545,488261509,945359257,486202162,127779243,426812302,834111783,840732605,100269887,473103639,438007774,51593897,925757488,33858109,207716650,623021605,603978910,42768284,449114868,594634160,295125480,611579352,119066188,804042135,275983056,34305140,38352361,747188507,37671082,855509972,865528862,478887985,220985610,213503477,937389965,378954612,758425058,168074536,713119228,309651243,664161514,83954576,252728975,59121431,648325876,789244210,331871607,212807481,890048629,496779005,236264300,972528507,370788725,415932780,729006680,796404120,417072784,956730743,634780357,386931858,647021928,512680573,368958398,591517971,822611542,321116959,905441929,50951506,538391863,936813412,111958690,568234293,164050803,363250202,617968368,687166483,374529696,440871885,707505818,706045694,581744980,937557218,41075395,630404786,360079545,287191429,71722127,440420559,395901359,494569430,507749056,78762000,532989891,975402560,382121415,219759977,135322191,563918463,751331216,373837704,397577110,274841206,984698024,255778335,30029701,657188684,69745463,980890590,530337933,750169540,566803021,362151947,207132954,805306433,16087158,2461497,287161337,949764905,696729155,623062783,152970738,836656747,884541867,1085967,789179070,721489551,146234528,475983343,850524125,885846138,141967918,643332529,693575191,797949947,785928429,411897133,786809037,865105601,677006307,894899073,787137136,337402254,156889954,262183476,644469524,367389093,267944119,934239057,161771338,978895660,11215377,166835972,162615404,673445391,927872807,233637073,571087288,42239182,118068570,2167562,488786599,24229429,428427232,259317716,321863121,449143972,23514189,839383975,956097389,414195200,524637209,408416464,109312507,942759799,895359233,108592236,711971491,155317817,443652947,127934098,773294153,189338834,282870661,521294961,505532403,802081530,862219951,608799104,814362047,210655982,713450037,279827186,966032660,42058486,570271421,155808516,808786410,553258764,702686401,80429638,297593830,427435755,4732103,212995678,615437751,892117232,465424691,572900005,945689323,51735941,554167456,715440101,235880868,245669529,729546282,924056670,760929148,666023164,904245261,991299082,121735874,526346262,61392993,961144551,936868324,725849375,61153102,394263129,405557804,308173111,509489717,117382439,395535160,342290228,582720143,754081463,582879233,272622392,703262837,428076056,567738141,900320033,37493600,556407991,967715830,350153541,995999032,871008538,149050030,611353868,754162185,659956012,867665806,60865458,678317987,937884456,585009997,607010259,594163932,195170082,134261026,722527099,939251013,861310191,505514227,80416615,567271425,27698142,372365079,540069248,306197155,504461356,788547607,27162392,413870128,927778696,359724259,82503407,757210195,803389853,892206751,319260980,792318702,476286302,981724054,749516587,548219782,870123710,627765121,360394967,556702927,370069946,415720045,744421863,734365897,879974818,929033775,990995510,564889276,692397639,882893535,176928002,705520357,298946497,695046193,85542581,516637958,998165754,878746035,478940600,410049841,460658514,701721371,728497067,423653974,485363379,705711993,414630177,787556427,898348212,1119419,108632690,310812686,206788747,272084504,420558341,29967438,129729053,383629290,167237146,670217794,327592528,132096278,962685255,112461677,905187888,846915275,340804063,512563871,988695869,20263158,332457961,263287220,762393409,412874037,161116141,824487285,879804592,577890492,164235086,977497897,928965721,178172015,881516289,723047570,769347828,623060661,53653444,893876746,829706205,406247452,148128181,473054164,431986090,653134080,583262791,39016210,908472481,895002747,193408781,236772721,143201095,809337652,24335555,58018676,527287869,177948422,869527930,818020,133001998,287490354,526802515,466898205,705121270,740972578,309274739,742005905,159549515,868620691,988401935,202228642,883957751,961402655,453719975,735788264,496449872,278727575,815090064,530929058,318114596,702284044,627547516,351720472,600032529,639028185,553538169,984495460,60650983,824457633,172805178,424201837,534402088,333089320,853194023,875379177,698218414,550358839,363109741,361538084,284967007,896003521,897040466,847289371,674042618,965318712,845067624,117662213,744938194,967907937,803493671,810095399,899485622,966339798,609503832,964005094,119629104,377642020,764382132,963043357,182690922,546281906,24354363,612379476,330123274,176921485,632117892,919474652,425778429,996608203,872238515,575742949,747938077,176339692,831598927,761463799,333357253,454352522,167822982,977162560,412617136,348218894,818121345,537885964,975371072,162104235,480722579,370145136,123993755,475802671,849288530,952205256,103764816,464849213,45085083,620680986,87732302,394262151,489818106,673232999,63926190,32949101,980437807,954260183,905471235,137677330,52719627,962031050,155240220,657420278,144674438,512396948,820405333,864599312,585443236,944658016,771333884,403379354,370168288,864494428,747840965,594901095,398937883,901903796,558623090,897610370,685640404,735875306,710749423,762206587,967942553,864099183,887337033,547600234,204521994,487729409,523700044,330085818,618860853,784172179,386872198,836344429,973342382,878469285,874580701,615584401,663086521,987811400,966667779,131751282,182081263,117714257,374511740,145690896,359917159,901343111,577315777,959856482,529858181,205962841,212904051,409365986,748234734,892568483,321548756,624920171,514633991,675435809,691741324,808780197,289330719,122712310,485995621,989927458,851454444,709198559,274081070,413422971,730259111,222547054,996141615,904654276,517089461,458590955,387665327,703453074,763663418,599126303,160451479,377157631,440013335,561003038,379987712,135028353,146315669,478622628,272074926,786402216,6115792,451145543,425544982,200387738,8942165,661347160,240140427,114513453,655048225,215066668,737238583,327860629,315051523,797075378,20230683,375609686,25094840,791740567,575318561,931120611,790678489,346220205,556988345,199336162,2136221,404318910,898059401,649963549,91316260,259162308,424910297,132326595,699670307,380505342,73030853,516239172,288914377,983103980,68896616,858417066,207968592,677603777,115400963,221225440,683579400,302393368,365536714,969715530,312253312,634030921,183854103,248644197,319243450,558232732,416254290,912826801,978613688,200963404,319757190,601437527,839012381,43466474,709838229,208728192,86623114,602801575,305303629,725815525,533629394,261860259,733065387,974525119,12796169,13210692,831667362,704017042,980881088,904709130,262884104,566167682,356020689,72356607,958454315,704812989,459355962,208793064,223259180,36900636,57936428,74205794,449828005,730414689,63570897,246450082,487959034,886048342,846795136,557165000,933083722,230036965,718130882,645828855,45334154,246241663,226607469,332451759,755855135,375709871,251583232,499479701,237805889,687298997,470026157,516370861,978996314,100877710,318861672,582325197,23939531,610160691,771188463,768198973,470893759,453298711,7079437,80914999,476954914,324706743,893461470,476502544,762416287,11943873,835656786,955171208,825547468,731588569,853852438,935647171,101279510,685053045,606475756,744529184,451701552,417957264,562378484,544951865,728748797,661529278,563819374,303382238,39823101,335492931,536888058,933580533,979882441,160344680,571636882,646934847,248665033,834148654,870780162,727879543,621394508,326771628,571823024,195829659,873897575,599323467,3297115,279390474,594396543,644766770,414418079,559133476,793044049,324324634,887417425,899738264,866280862,914328567,753539904,386630397,431989517,48816065,116766127,496620818,792371291,891167400,129155494,914918571,978156058,522790599,802185717,697896354,498300363,457578416,807415534,280152282,275127874,887356325,76525153,512806588,575844281,654427373,774675616,402929366,869429014,697897764,22686799,81313041,846279443,595801157,994601534,798809399,756084342,347515707,825492030,250743271,126812499,645497153,924735306,841057308,833332450,571837853,779071679,620476985,18666563,710817907,513577017,584038008,868347072,46832370,451327999,76894300,323871452,36309450,598150950,55897762,543151946,361487942,376676112,556234085,41269502,463385598,418566225,511960171,590956650,215136957,507352122,245376199,993486525,930210855,317799605,597270645,508679002,475274612,79769745,372528133,207735912,230007134,648677303,250871609,712024666,208621473,961714627,874255882,785639221,328000143,380550970,169283652,988817388,888825554,771012242,622894821,191758673,868500756,463193257,922397032,265851752,370379867,794832079,625919818,146387151,404281309,57711308,470888034,544466296,87939238,960969255,299590422,100464740,858116719,105674700,536141250,825226825,179835932,277872773,598083647,456775700,231242345,269990801,890223165,322402124,81952737,558909399,291808789,735479551,450162056,255624993,117634095,985302981,590721708,171095580,190460532,156675915,84725400,618134645,206639161,215682461,545146594,908977798,276415478,24017950,635381431,921021389,893900492,707814658,247956368,70431051,305825864,114257260,23973410,823064061,262490102,398086021,215325399,712544434,716865470,7582841,787645255,153040599,512996900,296260957,837725483,282705389,619369736,99701744,982604188,449661707,833511698,351764623,897720159,950895035,824999396,515408100,430690834,880161769,597524634,900894199,583552541,554744848,930865091,816523657,592250389,808411530,129228007,340147917,902813038,151338759,661002045,873534812,410928430,325315597,477946796,493387765,443359627,123526078,181196111,749178357,921546238,391402045,51851916,773886429,924765191,125593717,545508521,634097160,312700981,424535326,478764720,185378823,930412011,777056446,328532611,965350983,122985567,31336605,225550210,664787129,202425861,822761332,577731433,2709466,226576308,486495,536881267,708578452,271042606,7162092,512757355,159821551,225862490,129715720,808549619,380098350,838600763,745533149,570274600,277410267,704373462,669439311,710666740,43195488,234580859,666991263,630239951,115813019,967620510,986377926,579694637,900501248,995209063,998081508,737752213,784231791,863936702,812396780,203188494,57835602,280669616,706810988,948947489,552956064,686163150,902486639,646153576,183165504,513090600,492107994,170127327,230264911,663885370,832119799,695181451,882196039,450780825,619521978,962827195,338576064,341292992,399887570,102634957,338558808,19882621,112962746,64727986,296373305,347176363,31633221,809733057,162689184,63488027,4049205,360347598,142355941,779531550,392657888,299826828,241811337,360846116,971434462,373684478,192376076,71123782,230259155,972307731,723720033,375182593,812963540,843774441,357870598,786898409,271366770,310262680,923058288,66379288,717802508,342237685,970942767,567945159,112650129,452895419,922650901,794418038,556942273,45169976,969499799,819751562,226458949,21326632,247669075,146644829,806316599,381002788,13465416,110839243,483254511,206766338,912901793,279312102,393388835,150288634,740449634,352803762,134445824,993583089,877262882,19120830,188905391,347197927,50140495,607414011,942554737,201070990,350168658,527873180,362620416,31683812,807406799,831173153,890718982,747836267,872184339,937816832,412988647,744596371,678825777,783711480,205113451,118576311,759272894,891213947,544058598,612855377,182476937,478710141,740541508,334703948,32069938,595278572,699371045,147838799,531667176,759148677,982318798,17317083,31283406,729946419,666946846,193784910,285020346,550890060,106435908,950741570,165637803,994150951,807451158,792717926,221543795,596682958,850377310,471820281,645025576,830312616,10925884,871243248,463503531,102865845,363182943,23635972,116216145,264577440,466570286,132437744,109929036,675020511,360629057,123944813,214674957,704864838,885385860,326212842,446500310,749014233,373894570,758438375,780543410,66900578,190229792,47298996,957176273,974379333,684558300,523825081,343015060,620328054,645901571,766630080,41469743,376698241,786597674,971277283,484082511,623474622,430104286,105741412,299988544,440468410,307233019,79568171,439591865,478701197,746209270,712684480,92062835,790897186,70871029,761106090,386669898,464244277,577214047,407255549,158700888,787222213,602831584,716924359,812875686,126281443,306250155,967205791,563987842,359272169,265053516,836682442,600384799,523879181,678634974,687593200,153429313,928474130,102404272,567934288,300379987,354824066,763780946,852497333,351949558,357567210,967143533,489452784,151573140,898213837,854927198,553965439,676070055,121212116,844059743,538297634,591150011,646122920,278989305,486185814,60137472,829683351,233851563,479323069,412211122,53554997,872342214,463294565,487890043,954790333,393270275,948988218,976259080,812571806,96256594,803068928,992981253,819461052,28447174,277485442,236480179,76750358,346137830,656671091,223255986,175577812,246368309,454358045,332407540,876698809,269834829,773634312,377250107,170078253,975533123,621309273,528900287,219639854,339980210,680551051,209475401,1142087,430864200,37150828,591720545,834699864,881074049,838321628,240722767,257815060,438855062,78873955,123868116,341102692,165196282,512596934,605124871,619475754,353286073,111290984,239844649,264901101,533794449,198052844,703523066,649905460,118531233,587550648,253831897,4112738,424408778,355842588,473836082,208152890,619150779,670993409,666016178,328555935,908167147,841511006,863209791,166486187,262283684,640972619,280613994,445079811,550232704,711991327,842913197,691980517,267954512,113127139,565006943,147477488,833510796,272443627,461136864,824400537,986984550,385698464,752652949,8467864,447866993,409546375,854319293,536540556,314957049,426286656,387024448,71737473,718686606,668772246,109831699,527586053,280328483,427975308,506043878,599574920,757113868,4919876,593355669,437262110,791617069,277843021,533040518,323020330,784097119,785990538,893674738,208317056,826452305,433425933,704809678,994153774,964439004,100015823,153567609,354651362,109382316,160883561,96002701,670745285,127352547,819774710,593304464,989802657,22885314,738332605,915096065,855178525,317684090,852035298,119201658,776224625,319783767,518390756,416757109,489455889,406726815,220544249,133282753,219409929,123105861,392110244,811397606,331795633,131757494,106973596,209622600,46805923,41078122,131687372,924067452,834144006,178186360,278010906,617470345,421894466,552836295,52951793,200505886,597303220,157224745,591903814,16715066,97915900,395999986,769050251,889642765,3473983,143616280,225136221,213438699,292823565,369852277,502482771,544891659,78826780,279206536,518190861,848178894,297703842,374037192,288069218,114261475,140974615,103886851,419975353,602835972,980617559,74977139,382612645,435154299,524547592,22063289,176571116,896978204,466124035,527942671,325973783,710613157,825350081,947999024,56138571,751852558,448802935,690982058,221550990,603877468,473076722,43258078,397157937,655599483,567543889,385320242,495948375,18452861,15845399,425935734,937324500,984768486,41190770,640545327,125789020,594645376,84506872,117420728,658585796,784608399,386708748,718121815,296095907,380462765,603753472,577817644,239204249,451363455,422990655,908221126,516275997,425596518,30372638,119193423,432482001,366424869,163446628,736196539,821437277,756787173,78086356,326299666,393443846,766788757,563099964,90957967,221433855,128013646,721196400,163754812,538733832,253268183,118779321,689433754,887965131,186010404,200492803,437652633,738111399,32812156,862205972,54636385,357343458,873035358,35317739,765744426,775440670,317209401,573905950,609667212,361848709,67260296,805073738,178483363,282566230,764095031,662478457,912799376,75639164,977808725,1969852,252434524,67910373,137736937,898839930,682272762,252079451,605821126,235095581,742733149,660891897,719686084,864294354,553416350,261401344,431152089,369972618,184378417,606255499,361342047,489132688,153295758,732274623,919969065,434377303,898696718,872246000,599617164,952110403,821747194,946093879,460683384,451233831,598830971,93033480,700746774,510901236,522073285,918380549,698209869,144870845,349918514,892141988,436038624,92806913,320626738,500777439,257783076,857997703,750865440,92851229,341962857,625784340,722978534,139513675,497807363,902946129,531652011,314722662,738240230,570192473,437916605,676115509,128921743,517378399,571676424,145799849,59860472,136276192,972821645,65364628,182098275,33110111,499050581,623875679,324455691,414324401,910836888,94550660,147743083,677269090,561018180,525205536,841840884,808836463,307108418,851920571,450580764,781095650,247007021,421025528,553405508,746144044,146020201,685036820,546382602,680779645,411333787,252715271,552201094,897175128,785821021,975571131,587388783,888187167,943451794,870088215,210506217,904012455,933182743,663534079,892499486,352609340,573719874,513843432,315461078,730918222,169779385,907604980,276483973,664032734,56169313,500400215,235416962,921734627,187422154,418181654,811154212,283675009,481783698,158959103,238991678,607598961,49151140,857595150,863728637,887155091,280958626,710938978,675984614,77090614,750578318,144789875,296045854,620348652,632090985,174755928,901705453,54831760,497940165,480940781,285195110,654204771,133100055,921331401,726717485,892863751,919780485,342150710,735385681,387683076,577340199,687270437,559184860,661241836,213857281,427168288,235389157,952156021,418429238,524382617,769590862,252769156,57547958,529714986,55760465,506953946,782660584,678366655,144759107,864151135,649852539,975461559,74673823,278705901,743837787,503964618,605328422,321313219,526500407,652007016,561278569,30896143,570551190,389072843,575836080,854052780,332060655,283792923,149814148,337344934,991461362,449571203,157848148,388646201,760026361,581861480,455458383,410510869,714349521,491057367,69098286,313533439,93233136,352333868,946877054,876686169,22585183,854056698,291675923,606937149,971980031,236622316,847709348,12835189,894813381,374347408,865520323,492877689,27645333,299275962,955133467,172190586,508684302,673742645,12238657,536244986,447571865,123988695,106790601,348089934,632809007,258134965,553110971,432257711,622126257,935503059,352964966,936407005,4439217,254882455,274710146,93342619,610593564,490284840,144390863,485276856,765812927,384400578,488925987,394886480,146202192,956086896,121506342,212527308,927304153,101455074,622957536,728924044,594111870,504690232,566970482,744046329,130914784,483280315,308442871,334595974,843972630,994678443,162479273,793773008,101129264,146975287,973953816,429644614,242209424,216300498,742866406,934414771,731413776,91305852,972208274,302305351,516039324,131380804,713499868,518114072,456932565,187810773,355820706,12810526,788370902,829756993,699769765,867507150,879520121,84157580,909358912,399577687,660389200,501502311,448346768,56270816,989435477,281747466,967667607,401016156,670694951,83917558,915114952,887233251,147701651,384964812,836027,409995849,79093217,690285148,926653436,746047757,935906918,595438515,899328237,227939176,114372078,136969583,540566159,699711919,290217831,7604307,668380078,931559385,709329385,837937490,442646464,865077711,315375897,596230938,169790535,502619925,486372223,346422372,828154300,919664843,690848970,450806686,77575231,628791882,51136551,135680865,886584133,545275433,43376010,886596875,155958505,375702371,499300271,112923423,287140512,874698153,367485438,201566363,173874759,179888291,801315464,233695610,911399107,810701398,287996543,143997204,149312208,24589200,892407563,827153103,561508174,451716075,578757244,792790592,176572398,580839110,581505596,380029606,147992170,872965574,768719981,352624141,495888262,218447589,268150412,34876233,838255779,257736886,740687223,231470002,225675514,153601848,516950266,463000579,217166452,678019509,784200917,780758917,154994891,712407111,876038623,383948341,409427307,629977195,905934107,566658757,923102647,968172210,648928351,502206147,654508681,430000838,364222854,611387690,889038688,191949226,829911783,374752253,433449715,725282729,311623263,956638337,729110347,413350286,153993942,852583368,50399283,348298429,890179885,125206803,214854580,200852861,210958308,316900962,842704891,205276417,192962952,160971148,529810452,802607229,201796939,829681235,834153245,783305452,654736113,17029518,595405112,286133546,95017609,212648284,91962681,830397729,301142087,56348681,639579184,307700028,337024976,252344626,594698903,220254500,32202315,665107685,580574004,55641331,873271194,405196154,92324940,327220641,795391966,583186145,160663791,878127716,882660326,85723218,892650609,421577646,40168973,479732028,114487764,886742726,81850181,944500040,5513179,971541889,328030796,353258776,877858986,178379035,852966374,747370349,523134054,361057463,770704696,923013215,129727621,343766362,791504417,146330037,945402831,484803647,260024525,161514698,178089492,880107900,936431251,324186538,562279889,176281461,152381862,127339441,334951893,446602795,275845408,633149473,500526243,743951515,636928664,494068996,429715159,578515992,691920307,989824375,86711363,872529733,475960731,120434471,240683367,175956331,191367956,860246261,440383708,669579499,559664891,940928036,740704062,745325729,463514326,385193545,615390979,316864833,417560276,745264024,91889455,627336275,381295437,898869824,808733759,291405089,205008333,241969088,94767910,638185069,608292877,548090388,751862042,932673879,476594170,811661157,410829249,748210140,4174466,318166130,306552282,504291835,776341027,761246712,333861922,804228621,515216516,564060155,397141674,934812742,326492641,177166070,604604046,191068685,522970126,773441403,36358471,807573209,727010056,719501134,317244615,410905309,433221532,557152993,889670578,683032420,897409213,482949382,978681000,944671986,187020260,173619936,770754245,283087727,160041493,631391058,481383628,95635857,875933078,415968580,954179840,314570249,155167529,181146289,466265974,907403172,777881092,852271788,132563408,528401687,18394884,895888634,85351893,292330440,267401112,377322768,548611626,526984316,251658004,134751811,550673304,819265328,424431936,946921976,449912068,941762756,366156349,847981515,593514438,623070251,573584895,45995112,691329215,240736801,149807460,142677484,37056138,674959825,758371145,358683397,690603472,336491494,853723852,816071313,817224298,889953074,202775367,669113196,449218624,25366533,147505495,879716540,437553503,901315771,970411976,534517632,942555349,805553893,882946438,816030855,148439825,779942867,74363114,622705438,294880467,906768015,524934808,553446466,522250611,745482651,309743165,734776532,71639432,565631588,533253500,267540479,217828625,756478449,95058739,422611715,449772902,989501334,796355249,966908213,646584016,158462204,445998626,195272096,714742321,964290421,118260394,418925087,678152852,904232466,573826289,265356144,824000807,774121690,951817639,72689856,13148829,920058464,944972676,800971547,515457004,9315273,473543569,856523482,42070736,701644478,532196479,776058286,701292372,794643477,216312266,696812261,978780429,769707383,216873410,40855901,890203272,996139855,420344254,880927981,782533483,206071526,915330439,829825104,441714400,228995611,707046194,142288277,814040484,924462869,849156830,1192000,557010956,771609982,704804015,829370818,428213970,915403636,276661363,69134574,578983322,310992363,49858309,104746797,178749316,800624552,946053569,127484837,511861616,956120700,695173204,393028658,441562139,331936374,859268267,952262779,555049995,773631419,916520611,965275493,816663869,147505455,315592527,80067550,590949003,358686809,4249690,8310501,42624158,687737510,9207147,378897134,482490777,541201090,372742559,114208453,50254124,928584864,437570859,958529201,935040356,802336789,94633415,287919684,300057181,680708579,54255895,189084010,350920688,648326938,374077816,900182860,648252819,751236531,302763692,787854322,744680861,986480063,776840222,683410715,364603938,916481193,929333346,484064718,65509259,725647537,349860437,720137855,522503347,528385904,359420320,787515663,581880683,963543412,941590742,615901466,493542344,194787702,223191432,750010194,592410076,918358987,151031718,292829326,878376347,187132662,68417876,454183516,979399562,702297635,466757774,680648920,860883915,635684115,732551323,385776678,296147932,836367529,841581317,859617310,359492616,836237591,157100068,754974266,848231754,630773860,541211750,45545948,442824851,223409777,91317972,172095549,649945846,885106008,331230816,367717936,370931670,872176533,760674427,28930818,266547856,460934651,708869867,719316119,97523868,153229266,38642783,216730462,764264991,502510384,534226277,397237077,282002709,673383444,522402682,681365232,752147310,731344557,425170111,705909897,217554076,137430209,788842551,894920427,280271359,149841842,8820856,535695279,322558223,950116527,794727263,331994975,30716384,537166892,666179223,70470558,18508449,989372977,409164744,867280565,155592686,45673948,928534120,495986035,329763286,375126130,802769062,417844823,124703971,400918920,458132805,798075933,380460401,292278395,710910819,366902054,96565047,827768707,416699419,497180026,949929319,618510148,135447209,311594378,874688900,464013053,95704809,70870653,201864366,784970032,243116845,865835152,842163011,683153820,344114624,183590741,377181167,625276577,985002645,441828502,571621855,495290161,567221074,770615349,146402382,236001100,293343388,355590370,11787433,686188509,728702908,892263442,387787183,807669194,417365044,969822760,152363241,482351506,446286250,542052800,31537294,989006853,874951937,101657948,938281426,884804604,491018546,488283540,508444811,82875922,789132653,926554314,605076152,526831407,2715288,498751409,408526740,932257597,524300716,866906359,223186295,775895523,146829843,866878434,499318606,254470725,231037765,516538007,416051967,698853799,674153191,82116591,356770753,809847203,702275403,188412000,647178310,37224935,383374251,422942221,4229920,951012529,51010954,910659218,496059036,359907171,340881654,867135580,527396028,897283193,985336056,399082324,76691273,107476055,7496936,956325818,618864721,296331449,413591980,567023196,568071818,331204368,844362811,424392812,433911333,346305194,739432705,278519,458168389,352533491,821826326,928148077,165146638,610619622,955774159,190653565,540362672,253022357,85667763,953112105,307160169,113618114,941400599,137233523,879042622,793876024,213450252,144678676,124193202,924210002,655189528,403423650,228735871,50231556,783748391,872424159,106886358,74793058,674257645,606395230,681789969,697058419,585098023,251770239,7723706,669589028,824696023,33641422,444201462,990617844,811801545,182053291,690724983,884108569,162539313,401475590,191046956,123239287,479577366,177862589,973869140,806501414,510522744,941824435,737807187,766916381,416154683,507531057,86490214,857963522,937329793,804993964,852854673,842055275,745671220,831013569,696052195,67506340,928395942,337378952,706788616,889582,465959981,316264447,930428800,860292337,99170809,262420550,748795032,898458753,471884214,270667072,982048022,947810700,58231657,580665000,122124727,524905405,982427868,959925966,587842139,537423205,340496313,267196928,517409951,634426381,489823323,627456912,342589901,23310562,171057914,914903176,944916788,111898222,533517058,343112569,436645568,153410498,484889883,265573542,880882605,245380859,922188668,161645487,202877063,742997727,929253377,268055254,741811817,502172026,325898605,176553217,217286269,645469422,992615584,917486466,311727069,55562923,205780426,788281240,549295544,241466483,912591313,88903887,348876965,697093428,526714956,770863442,772346474,770270830,284419562,707334321,202205127,329589900,878371816,425206152,74885391,427996493,932599916,655032225,630142524,252328057,870209403,575377773,495052956,322134287,897164227,700225993,762969268,306339626,520761979,756589326,301821688,775284070,445512802,820212893,388601745,772534749,508339405,991677196,713026448,758268886,398840682,265236611,908116281,592880855,219558294,968652305,486078804,602992317,678122403,12333603,78984182,395678373,279784290,942719450,565004434,11373013,292986338,882911469,777364486,368994007,920892491,390913575,479108715,708396233,99185759,490890046,979933642,491295538,301515798,214568744,768720668,633621621,751423398,230109889,984153307,912117654,450166625,10130844,414391354,794899340,985360541,320336770,732020297,554328188,242187160,554467748,483221814,127511071,930308970,34581420,21251745,379871217,730587445,292008888,110162002,592978997,548934917,664710674,859052189,790433348,398337844,799773715,512034190,399792041,387321502,424184659,898878359,541333673,799359883,196159130,884215963,83092414,745001929,676102027,815968393,954973624,278565947,568873200,966836875,971892775,145283654,908512925,702961111,854492727,917511209,522211383,629155935,221170227,32080736,63113076,77187448,733421503,404876394,658799706,131059979,492332715,447446184,115648652,186953574,881436720,45759263,645717000,911430091,626549807,883145981,141048403,611623460,115237899,66401952,852569290,847067870,874568649,419197465,29691434,65327800,303199107,223436768,183334914,871002426,537285263,653859510,539351551,523362299,205852105,535628031,283594400,62260662,522808412,720589525,130308821,31748367,466213194,156694281,814433066,972989945,852469095,445217809,353586234,281074310,423668902,316229090,39415829,699713852,385591320,883405708,641599559,291018610,806822740,792140224,702280442,414477616,991032486,795306590,769217861,356961125,218257583,850789209,758365117,363623174,133664651,596136614,41125158,583751063,929538157,496473146,740255632,856994693,731280915,818888583,862416148,307807814,413312973,294160068,561490440,783155857,366082576,671243953,842669908,329478450,654112989,30830791,935173282,330023937,860055177,932376365,955286656,45740068,620483583,63324423,941900764,138907072,860385225,272296287,501741898,823073479,788143313,959929874,927087262,906125323,257299344,807800735,817875841,762859601,652399290,184030428,527935991,150728772,44509114,864224976,223946410,157288052,611426707});
    int K;
    cin >> K;
    vector<int> L(K), M(K);
    REP(i, K) cin >> L.at(i) >> M.at(i);

    int N = 0;
    REP(i, K) N += L.at(i) * M.at(i);

    mint ret = pe.prod(0, N);
    mint den = 1;

    REP(i, K) {
        den *= mint(pe.prod(0, L.at(i))).pow(M.at(i));
        den *= pe.prod(0, M.at(i));
        // ret /= fac.facs.at(L.at(i)).pow(M.at(i)) * fac.facs.at(M.at(i));
    }

    cout << (ret / den).val() << '\n';
}