#1137361 (C++23) No.3394 Big Binom

• 問題: No.3394 Big Binom
• ユーザー: Misuki
• 提出日時: 2025-12-01 01:20:16
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 289 ms / 2,000 ms
• コード長: 29,247 bytes
• コンパイル時間: 2,072 ms
• コンパイル使用メモリ: 223,080 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2025-12-14 19:59:23
• 合計ジャッジ時間: 5,975 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 4
other	AC * 22

ソースコード

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <variant>
#include <bit>
#include <compare>
#include <concepts>
#include <numbers>
#include <ranges>
#include <span>

#define int ll
#define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1)
#define INT128_MIN (-INT128_MAX - 1)

#define pb push_back
#define eb emplace_back
#define clock chrono::steady_clock::now().time_since_epoch().count()

using namespace std;

template<class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2> pr) {
  return os << pr.first << ' ' << pr.second;
}
template<class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N> &arr) {
  for(size_t i = 0; T x : arr) {
    os << x;
    if (++i != N) os << ' ';
  }
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &vec) {
  for(size_t i = 0; T x : vec) {
    os << x;
    if (++i != size(vec)) os << ' ';
  }
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T> &s) {
  for(size_t i = 0; T x : s) {
    os << x;
    if (++i != size(s)) os << ' ';
  }
  return os;
}
template<class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2> &m) {
  for(size_t i = 0; pair<T1, T2> x : m) {
    os << x;
    if (++i != size(m)) os << ' ';
  }
  return os;
}

#ifdef DEBUG
#define dbg(...) cerr << '(', _do(#__VA_ARGS__), cerr << ") = ", _do2(__VA_ARGS__)
template<typename T> void _do(T &&x) { cerr << x; }
template<typename T, typename ...S> void _do(T &&x, S&&...y) { cerr << x << ", "; _do(y...); }
template<typename T> void _do2(T &&x) { cerr << x << endl; }
template<typename T, typename ...S> void _do2(T &&x, S&&...y) { cerr << x << ", "; _do2(y...); }
#else
#define dbg(...)
#endif

using ll = long long;
using ull = unsigned long long;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
//#define double ldb

template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using max_heap = priority_queue<T>;

template<ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP = plus<T>>
void pSum(rng &&v) {
  if (!v.empty())
    for(T p = v[0]; T &x : v | views::drop(1))
      x = p = OP()(p, x);
}
template<ranges::forward_range rng, class T = ranges::range_value_t<rng>, class OP>
void pSum(rng &&v, OP op) {
  if (!v.empty())
    for(T p = v[0]; T &x : v | views::drop(1))
      x = p = op(p, x);
}

template<ranges::forward_range rng>
void Unique(rng &v) {
  ranges::sort(v);
  v.resize(unique(v.begin(), v.end()) - v.begin());
}

template<ranges::random_access_range rng>
rng invPerm(rng p) {
  rng ret = p;
  for(int i = 0; i < ssize(p); i++)
    ret[p[i]] = i;
  return ret;
}

template<ranges::random_access_range rng, ranges::random_access_range rng2>
rng Permute(rng v, rng2 p) {
  rng ret = v;
  for(int i = 0; i < ssize(p); i++)
    ret[p[i]] = v[i];
  return ret;
}

template<bool directed>
vector<vector<int>> readGraph(int n, int m, int base) {
  vector<vector<int>> g(n);
  for(int i = 0; i < m; i++) {
    int u, v; cin >> u >> v;
    u -= base, v -= base;
    g[u].emplace_back(v);
    if constexpr (!directed)
      g[v].emplace_back(u);
  }
  return g;
}

template<class T>
void setBit(T &msk, int bit, bool x) {
  msk = (msk & ~(T(1) << bit)) | (T(x) << bit);
}
template<class T> void flipBit(T &msk, int bit) { msk ^= T(1) << bit; }
template<class T> bool getBit(T msk, int bit) { return msk >> bit & T(1); }

template<class T>
T floorDiv(T a, T b) {
  if (b < 0) a *= -1, b *= -1;
  return a >= 0 ? a / b : (a - b + 1) / b;
}
template<class T>
T ceilDiv(T a, T b) {
  if (b < 0) a *= -1, b *= -1;
  return a >= 0 ? (a + b - 1) / b : a / b;
}

template<class T> bool chmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<class T> bool chmax(T &a, T b) { return a < b ? a = b, 1 : 0; }

//reference: https://github.com/NyaanNyaan/library/blob/master/modint/montgomery-modint.hpp#L10
//note: mod should be an odd prime less than 2^30.

template<uint32_t mod>
struct MontgomeryModInt {
  using mint = MontgomeryModInt;
  using i32 = int32_t;
  using u32 = uint32_t;
  using u64 = uint64_t;

  static constexpr u32 get_r() {
    u32 res = 1, base = mod;
    for(i32 i = 0; i < 31; i++)
      res *= base, base *= base;
    return -res;
  }

  static constexpr u32 get_mod() {
    return mod;
  }

  static constexpr u32 n2 = -u64(mod) % mod; //2^64 % mod
  static constexpr u32 r = get_r(); //-P^{-1} % 2^32

  u32 a;

  static u32 reduce(const u64 &b) {
    return (b + u64(u32(b) * r) * mod) >> 32;
  }

  static u32 transform(const u64 &b) {
    return reduce(u64(b) * n2);
  }

  MontgomeryModInt() : a(0) {}
  MontgomeryModInt(const int64_t &b) 
    : a(transform(b % mod + mod)) {}

  mint pow(u64 k) const {
    mint res(1), base(*this);
    while(k) {
      if (k & 1) 
        res *= base;
      base *= base, k >>= 1;
    }
    return res;
  }

  mint inverse() const { return (*this).pow(mod - 2); }

  u32 get() const {
    u32 res = reduce(a);
    return res >= mod ? res - mod : res;
  }

  mint& operator+=(const mint &b) {
    if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
    return *this;
  }

  mint& operator-=(const mint &b) {
    if (i32(a -= b.a) < 0) a += 2 * mod;
    return *this;
  }

  mint& operator*=(const mint &b) {
    a = reduce(u64(a) * b.a);
    return *this;
  }

  mint& operator/=(const mint &b) {
    a = reduce(u64(a) * b.inverse().a);
    return *this;
  }

  mint operator-() { return mint() - mint(*this); }
  bool operator==(mint b) const {
    return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
  }
  bool operator!=(mint b) const {
    return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
  }

  friend mint operator+(mint c, mint d) { return c += d; }
  friend mint operator-(mint c, mint d) { return c -= d; }
  friend mint operator*(mint c, mint d) { return c *= d; }
  friend mint operator/(mint c, mint d) { return c /= d; }

  friend ostream& operator<<(ostream& os, const mint& b) {
    return os << b.get();
  }
  friend istream& operator>>(istream& is, mint& b) {
    int64_t val;
    is >> val;
    b = mint(val);
    return is;
  }
};

using mint = MontgomeryModInt<998244353>;

const int C = 1'000'000;
const int prod[] = {0, 383627936, 631817256, 746563723, 213222837, 909322097, 91408919, 739817951, 236395189, 113594243, 138933352, 996532650, 289512251, 670762098, 386333453, 398180745, 581119288, 925396960, 148018707, 862540599, 738674764, 111476042, 344382361, 327972774, 415323948, 239199505, 218798836, 839442437, 201996627, 590403011, 678280080, 127497443, 21256513, 473504013, 463364983, 486985286, 11969498, 804521190, 837621429, 301045085, 473539622, 942399480, 37955368, 220549516, 256026837, 223514656, 99019731, 632913776, 454342731, 451686007, 530347484, 369092598, 66807319, 874253974, 92934171, 156975397, 671539054, 957742645, 76860901, 67166366, 31328182, 393578297, 526017190, 191601018, 676757398, 504121787, 979251023, 285196005, 664695115, 167605224, 283380351, 198922808, 980490705, 37757811, 341707274, 278340335, 99006276, 807409993, 882678939, 597991391, 552986864, 815292801, 420789950, 757255928, 982193961, 84949366, 523217783, 460740014, 493020977, 743438834, 679430967, 53278594, 975518439, 108133808, 374452206, 271481028, 875125783, 485057607, 665473936, 759839865, 580768493, 191016376, 421428047, 653436107, 108044023, 833115126, 752969062, 944659952, 856693280, 632441141, 218925307, 716960632, 210822273, 164642187, 979826624, 659544484, 536948294, 298064214, 560105590, 365838516, 443264174, 656143647, 953285111, 523043740, 521284435, 121962016, 574090515, 452627938, 525199111, 372782927, 167527144, 60555709, 412263325, 241777410, 510100801, 393214247, 670993743, 551715791, 259047645, 534733845, 946153281, 104411565, 709609621, 541702734, 195817021, 103447189, 747497658, 113687938, 476967455, 348900796, 967872130, 309270972, 814609044, 397634458, 410541871, 400766393, 119601680, 550860058, 430921161, 131925376, 866324809, 503627612, 307960625, 193994498, 126008939, 647056750, 542626077, 297265134, 970173947, 820816864, 46665878, 207825068, 225903120, 55495630, 575882196, 980694508, 455271423, 739084340, 465659260, 876379709, 327153889, 412028441, 854482537, 259416892, 762646433, 954552258, 27225037, 555177444, 680222153, 245172518, 837219908, 961044085, 712251424, 828185733, 833479185, 402785934, 572137763, 428153786, 383402775, 317463755, 175460802, 894128611, 114415326, 421485924, 634628741, 622994899, 259171908, 761138375, 508978779, 868698330, 566643158, 78056909, 904327775, 713803520, 233858728, 460862209, 126843524, 650843120, 122485971, 270700824, 139685266, 650926019, 91213261, 866908495, 100119417, 55127434, 696502917, 478451061, 456767121, 79726256, 537150996, 762170587, 354553817, 753642975, 313891406, 931603826, 7660325, 681873733, 904706200, 969347708, 996796370, 647111805, 204462774, 292979861, 598176415, 470948463, 254536647, 221308156, 370908844, 704123975, 786341257, 646933107, 262066040, 604754917, 304540254, 416556132, 996762291, 462072025, 593866271, 504857958, 793687549, 304886291, 264902462, 627150282, 367874796, 694977200, 967707360, 689616196, 167751668, 701581492, 366824865, 806457431, 82943073, 259960183, 472684618, 244974598, 626643562, 408506627, 47946470, 913166609, 948516761, 223045332, 391374259, 205161808, 13735750, 461783814, 811799015, 957356804, 841662126, 345928297, 622942190, 916780586, 915550587, 450103560, 461783053, 858513300, 141428731, 789905174, 883173343, 212981810, 826024649, 442292974, 74245634, 741998451, 561674389, 488953545, 75113939, 308709486, 631874385, 492149751, 27457638, 834903990, 322723941, 165465484, 463290807, 137518656, 671369533, 46714479, 928724662, 420956456, 358729382, 790011325, 142584374, 944454615, 854096550, 82419928, 244300856, 860576273, 108777388, 975404158, 749263850, 706722918, 243457841, 340411613, 884941327, 66138030, 137365081, 47317516, 687512112, 280303934, 69317292, 161737958, 153243596, 260435358, 271136693, 380608997, 111608241, 388356177, 681573335, 730379315, 985126043, 11084396, 374329091, 76046432, 157893775, 569475711, 437439735, 292917799, 539733329, 784211975, 335514917, 68483541, 168838702, 864645833, 46394897, 600116043, 902891881, 837600544, 333707612, 48546657, 213678478, 879758203, 353204847, 880293168, 379252957, 35040805, 232429208, 479375641, 59597936, 660971651, 348220290, 955787436, 893935288, 984401052, 44104759, 108010314, 663017924, 624514109, 521730900, 886509730, 868401117, 69628119, 332184608, 991078405, 403360738, 961341599, 762401379, 909146315, 996016736, 567090440, 219836892, 593674128, 661902288, 805360991, 629529066, 543497894, 144188933, 645128955, 772752588, 535433520, 538764722, 76463716, 249366934, 729638598, 756650541, 449129311, 984123683, 120085253, 566522755, 907810206, 848788254, 398425367, 831229362, 923544662, 10112336, 180607664, 224204828, 351012639, 804181180, 460124234, 717421177, 402488009, 588634223, 831786081, 521191160, 891007950, 381053444, 994069137, 912515553, 205687374, 343427540, 3185766, 63047269, 175674319, 804602637, 406504448, 526913441, 205700022, 859561768, 967582460, 209704785, 98032025, 233640676, 220510636, 130200830, 896130698, 701778459, 149487225, 131319531, 676646956, 36914096, 638902841, 57630059, 468363965, 340348314, 301539483, 416389208, 137279367, 314736425, 426566799, 191639730, 799099636, 319669642, 630515541, 382883297, 787065335, 675362076, 252988700, 63635722, 45476855, 748045564, 108455606, 388468513, 956293364, 492190252, 140965476, 44356718, 901446946, 609594374, 71718212, 961341370, 348965180, 901714658, 631853268, 64726623, 799302946, 186819444, 151601285, 599134657, 702508461, 312207844, 94725033, 944712495, 882635612, 961975962, 197999255, 565600132, 79333619, 984890504, 599337899, 991199634, 401186069, 780770402, 79421176, 695113939, 208848848, 687897407, 59713231, 985031777, 577039239, 869279465, 568738944, 650696629, 346761231, 158667556, 527245402, 602125286, 17744129, 278450204, 129461002, 112798343, 485380383, 942092490, 236491251, 241175393, 89019869, 974228204, 430077191, 210586958, 453807909, 211956713, 261614390, 598703131, 117137152, 783261125, 38799053, 55191259, 771629152, 671253023, 990762330, 829420130, 936123164, 249099422, 36282063, 331299189, 377101833, 897781158, 481012437, 212625535, 980702078, 198742951, 913921509, 646587082, 989406626, 14343198, 432328105, 286360313, 498675225, 258968655, 279379087, 48968467, 740244250, 831969451, 408982144, 529026663, 368405158, 276100779, 474328333, 195617369, 295726450, 963918515, 685706521, 918979551, 929563655, 701418137, 526184759, 910350653, 648071043, 346076870, 221638237, 639324791, 686596947, 275840098, 37025070, 738304021, 484666976, 502712004, 213863951, 507061581, 436491091, 239654259, 57072868, 323425767, 474912941, 182566252, 100532954, 856694453, 8720118, 197000644, 338921289, 991697645, 470590379, 604992949, 855086850, 765092085, 914298415, 258890649, 801269822, 63395468, 444434365, 492338935, 823635066, 597167034, 163005906, 774294907, 356572962, 628780809, 811205747, 824399205, 380410049, 712723197, 273665828, 814933971, 671444000, 416398368, 410328146, 470127121, 638285306, 180398321, 530521322, 906171683, 174006376, 930441293, 514154332, 815645136, 58558309, 973971620, 226108100, 827378481, 410847249, 883232111, 623068888, 278898511, 585445959, 346172296, 289489579, 331711982, 92340246, 450189789, 565408757, 259900397, 608020870, 429928427, 212979678, 763072325, 79334542, 264164589, 648161131, 329220376, 385674859, 452570917, 304644835, 860321410, 529223247, 102923891, 382315619, 273441187, 966174284, 640341672, 401790653, 541347032, 486528567, 127841478, 917039187, 491284271, 98660532, 766738782, 758813069, 280142847, 588161473, 232740490, 467701620, 432491631, 501767738, 241599206, 571455665, 880118157, 314546570, 627402512, 14403497, 412536168, 718243955, 657909691, 674925305, 105998940, 54483538, 626229315, 284371613, 725812648, 774016525, 34693738, 562794162, 616937689, 319441202, 558182625, 994575661, 763573905, 802772943, 491582525, 290590068, 228929524, 710371764, 61972997, 480981471, 327685043, 193142936, 982909831, 67097345, 312746676, 223917595, 343858962, 442078980, 9016598, 239274173, 796422234, 234645116, 191201331, 707273077, 511139475, 981408140, 526844616, 970332347, 520568305, 104992143, 702291545, 362798002, 297015809, 477812630, 108673083, 532738328, 402696471, 11739738, 984670451, 364069392, 657308604, 814374509, 86184383, 275515351, 652093434, 190713779, 892979056, 901123763, 1446508, 578747624, 55272597, 894674479, 473009938, 209235042, 123395061, 953906786, 538225952, 260461668, 579200766, 12074808, 960586342, 434393575, 450086465, 957002618, 699042094, 554051626, 736710539, 415318735, 91970436, 532306578, 283682962, 444898715, 763315848, 905056349, 641843760, 930326137, 987674818, 219011778, 414962989, 310574330, 123466682, 476831122, 136230949, 1627432, 505247101, 905628409, 802110177, 959192907, 633431190, 664318031, 698907512, 234081996, 334133858, 527872701, 103473178, 130696070, 595099038, 743709593, 219964468, 768690238, 423198848, 482556929, 864209502, 757530258, 198039570, 10529904, 727484781, 328745591, 576734845, 785054686, 764235979, 679619882, 955466179, 546047870, 988173679, 499705201, 752252926, 266263085, 715124585, 248150506, 447358888, 6338577, 395629303, 135693903, 933059589, 764815436, 706555582, 303185845, 663289304, 283304343, 235754163, 255118564, 441712514, 582130919, 193460372, 839577808, 198827536, 105529435, 389070972, 592105787, 983190678, 349799733, 294603948, 915468469, 659847365, 158812976, 97537944, 396429553, 293152685, 52997962, 691705816, 262305057, 605820245, 118544250, 887769682, 672766085, 469487510, 963971588, 141089953, 904212042, 211299993, 199926524, 587094204, 952370066, 943740876, 812710201, 437290466, 301009705, 510646133, 677254509, 434221918, 71399952, 880221353, 349915434, 735945934, 227769790, 891091579, 846894815, 758975125, 733329538, 757587754, 20749691, 956889608, 757749997, 214792592, 984401493, 768442955, 891693426, 2687197, 749852257, 203584641, 301111070, 694283465, 99321000, 621142661, 745156027, 368601540, 94509347, 150384544, 488759012, 800611015, 120323459, 137361541, 454992865, 77789339, 699578962, 472010277, 477123043, 614342685, 18463590, 683965277, 139214762, 811178225, 466921280, 17110038, 143974743, 908357009, 740563558, 415946150, 941641280, 603977573, 874659238, 346627058, 416461991, 236831540, 676701673, 436868838, 984716968, 918068247, 49118048, 237685230, 602708509, 671579155, 325269679, 7706185, 147444699, 880848118, 184588988, 551132115, 358220077, 980503328, 485791753, 210785183, 985084690, 283546619, 332998067, 341616695, 211231639, 796780044, 58686322, 717484788, 356681373, 245642730, 142634858, 789156093, 231639983, 78450037, 622884966, 770051413, 992892196, 32368337, 320832173, 71670503, 218113642, 490263584, 759559526, 854095869, 737121667, 271379158, 734965379, 61604857, 708601562, 570400036, 520337178, 528289928, 487238068, 573463867, 775035331, 181604299, 769924384, 247105468, 47533663, 226543237, 495598178, 0, 936388924};
const int inv[] = {0, 547090994, 20621830, 976559988, 736284545, 650987719, 73085532, 443226567, 291798531, 90508346, 112186012, 655240683, 854213529, 396364085, 111375783, 262099643, 817179768, 474672146, 481519010, 612708884, 573901567, 280962204, 15523602, 513931259, 656884532, 811880836, 553171378, 687687147, 766227869, 246618934, 639551397, 104810924, 845480962, 585539307, 791104257, 472922714, 792175643, 956142137, 985400814, 371869511, 760794690, 472691146, 930131557, 370718011, 258313946, 701022384, 989918789, 200081098, 174675185, 656514099, 797297282, 664264508, 803051674, 820849974, 188723272, 900940509, 853890496, 931339588, 625166121, 690459456, 727566941, 807611210, 781630819, 280801034, 490458056, 918976678, 559604022, 37586782, 467285540, 857278484, 242654591, 762369101, 823368593, 631564059, 471348630, 384906094, 774621736, 848004959, 662003612, 973376780, 256787558, 849392836, 544378760, 994860896, 211474425, 357449223, 295833671, 518061502, 959001020, 318699214, 524066504, 922988776, 77652732, 374023448, 39070366, 767980239, 901073858, 465360984, 356468943, 775661596, 624442221, 131809296, 533844474, 374016796, 747642139, 828946638, 400850986, 504808861, 716183547, 131881529, 578288743, 747749933, 899669482, 459891546, 274247417, 605360924, 370772178, 655141879, 637933179, 35043908, 316948099, 794038415, 297479368, 988038994, 241266612, 222858927, 199518815, 26647066, 753837063, 573428306, 731740011, 258264130, 656289539, 487364699, 370828046, 517420890, 185401182, 95150605, 445242177, 204136185, 870270585, 889736149, 707853537, 931045969, 852110076, 852647611, 823574477, 615334959, 822860438, 623292381, 170280857, 708353035, 217575339, 92984883, 790773396, 667259788, 874375512, 969505971, 341430265, 737551561, 777779850, 246103935, 139226646, 26665103, 551883875, 188857566, 42361015, 863254204, 555864737, 153509897, 733451549, 948968900, 296478380, 144279307, 528090083, 910349555, 363660930, 428037046, 236008533, 532155769, 177435707, 601044356, 978240118, 903582499, 336921193, 201845931, 976056922, 20502965, 329958932, 290446527, 430221099, 808834460, 172332220, 743999074, 660533595, 718321372, 979171169, 102857664, 497162467, 113529183, 338476891, 967763299, 105417610, 948089790, 934824442, 18253565, 917519811, 762925598, 955209141, 174522134, 475652639, 828996920, 789856132, 517680288, 484066059, 388622375, 654180451, 55638440, 417495543, 2595999, 311342384, 531895404, 205015753, 530877609, 610588149, 15453263, 73638128, 371083228, 309971258, 591300918, 46037608, 117312780, 635811757, 85803863, 207986388, 524305380, 516977808, 288982156, 541730139, 46617102, 740488844, 35212991, 649962683, 368539431, 527281805, 931642718, 168869030, 603398687, 365223399, 605559983, 155018615, 312099659, 28816025, 645908289, 822407946, 46092360, 704334309, 528636861, 884348894, 546316298, 769851773, 142403167, 938448380, 703112840, 702402631, 372297869, 857911537, 832157867, 791449996, 397708667, 167678983, 338592706, 598536331, 513665355, 850193083, 747621424, 77149524, 784785736, 14604651, 716118293, 575699617, 640749636, 587759356, 15266051, 281941066, 422003770, 647654317, 645094843, 155047756, 552664912, 265441001, 194691389, 208329903, 946969781, 893741409, 997470982, 485750590, 971970644, 501557101, 341500264, 168087162, 700466097, 141569336, 710785947, 362881631, 400032919, 736771725, 777362757, 185327008, 330944983, 497088215, 697922394, 550928791, 750740246, 73745652, 879193455, 940353194, 229128087, 734412123, 875962884, 246090709, 41608955, 315761698, 459113892, 926474587, 676120175, 802211387, 960378097, 909335032, 117132835, 19974421, 31500707, 661630301, 473550467, 485078302, 178461537, 253263843, 416339093, 198421054, 113744131, 697658975, 310659188, 777880810, 446157110, 685091269, 679571433, 530184196, 302810810, 704067637, 208354658, 373740535, 61162977, 961341618, 739815748, 869476711, 828637863, 66661189, 996993195, 543040652, 194731094, 783431627, 750371698, 625175523, 884019254, 725728182, 901433965, 880133353, 408247503, 527445815, 610960108, 12396393, 132729084, 104663656, 693551221, 466756037, 618216359, 643883893, 842641686, 114401408, 415617561, 319060276, 78220217, 24432295, 408201169, 765519923, 780322089, 995876875, 864123331, 52538721, 142364357, 91017481, 12731393, 935688780, 991798066, 123822445, 27113350, 633893911, 331837096, 225424225, 378575323, 955474622, 678869854, 688452149, 510850629, 972269149, 857174697, 187060579, 68132176, 319093497, 702122356, 271339501, 899895130, 164193848, 489447941, 432736264, 352501670, 300128355, 621010473, 672686621, 851743363, 782332530, 795137729, 166638529, 814583537, 532720887, 721067067, 555658585, 147738516, 926977178, 317578875, 472403844, 621875868, 961554119, 376025610, 166668461, 875043426, 170267608, 776126033, 362940982, 539583625, 534324859, 190349977, 365849999, 527518831, 189591054, 361516150, 277441563, 927269949, 305012685, 848304676, 260716544, 410104259, 659772097, 456560290, 615541245, 260638782, 242964259, 878586917, 126258719, 445544359, 284384809, 608772129, 878850432, 103854979, 939637540, 491808296, 258286356, 184099475, 550170806, 178800373, 791026697, 517507641, 524072480, 116425580, 983865, 202187506, 263350712, 121068312, 466613334, 164701251, 134083454, 954784642, 896758623, 915950291, 670118422, 956027020, 244460022, 124820105, 909958937, 785998491, 763719498, 928440152, 270696761, 170523443, 234749877, 806337629, 856710211, 369395269, 28488779, 541995362, 825830702, 610302937, 380880181, 648496435, 165080692, 286475871, 68785153, 844826807, 622949345, 799035408, 704238116, 327017773, 894533712, 87166369, 101389640, 497188822, 797299422, 451124459, 10877231, 895554940, 45113555, 711335368, 870941497, 209098646, 773743730, 11537327, 90519926, 346898136, 525538076, 422426853, 147070908, 281969803, 630136512, 700544532, 258384365, 462686860, 661822132, 822693790, 211798946, 53539597, 954984408, 543529656, 927881231, 609655815, 177984291, 404572660, 439528538, 585280107, 948675771, 234152156, 871984206, 488639325, 44049644, 906533997, 993876618, 48796451, 793656049, 442509263, 812029388, 608259240, 553386090, 78557488, 58563317, 81659543, 345330639, 685527943, 474724696, 961854733, 415654725, 133689206, 953624104, 901990711, 949399356, 594370930, 547328885, 371017175, 410824916, 322882632, 61007451, 554767914, 41447635, 306654108, 895427774, 638326867, 840817288, 342156011, 629508219, 319236128, 965072801, 885721831, 660425817, 441010963, 205540455, 474632896, 299060358, 958749161, 949818277, 428231793, 885750310, 730146188, 917551275, 153743926, 481475732, 583128545, 608913643, 82135660, 49240294, 387520197, 393970769, 668304563, 804330360, 547466916, 735517757, 535103722, 412232849, 369071102, 537150724, 821486686, 922431549, 575971335, 808853178, 450574753, 767962506, 473430233, 99707001, 496979523, 647173490, 551201534, 771383349, 471452911, 35211525, 706827259, 419858538, 832318265, 691849757, 946490948, 349598877, 589542307, 718368699, 809343023, 955961707, 189253396, 781996650, 934155464, 123974362, 312185321, 746589830, 576455012, 199282225, 137812702, 631429999, 85172633, 953699102, 147666134, 301172309, 650756347, 168494301, 753962492, 412214807, 763719343, 842497854, 474117109, 858302284, 192189518, 108392760, 17948030, 521084004, 415564310, 676276693, 685603345, 587091120, 97526139, 254682397, 746410868, 919171191, 53176897, 204470072, 257631808, 659937034, 170274237, 563479683, 950934038, 193677163, 993191505, 735547988, 449913518, 336216717, 320456278, 712199179, 147042583, 408559241, 236925749, 723820590, 370175342, 207742336, 875577100, 417308216, 257223996, 53258263, 622800994, 747446569, 646073419, 190988584, 93512470, 82258069, 991420583, 795016869, 568077314, 11177962, 661024114, 684408880, 440655725, 25109852, 509923906, 681729358, 43912562, 488725622, 873427720, 787557064, 452011873, 438257082, 994343197, 63240723, 915252230, 239675204, 633011673, 305685359, 44621250, 151299662, 779538168, 961128627, 443774252, 372911761, 366055615, 12832014, 242432016, 269326801, 300127156, 868896754, 325316758, 938923069, 795780793, 222507617, 28473923, 627557795, 916019308, 370445758, 580087009, 264533587, 222907099, 142141207, 126539819, 904456876, 587687936, 203779319, 136989628, 956998445, 668528310, 93263284, 662175, 904131736, 537388375, 697810005, 821887072, 762701830, 736292832, 951809460, 885080498, 277447673, 626196211, 55572501, 711668175, 927381443, 645279957, 302285548, 640688132, 286448051, 679677825, 30139185, 789257150, 191120356, 295428814, 749547892, 556048031, 939117984, 538405854, 309159395, 57370200, 676798588, 919858375, 184442683, 499486548, 68913354, 819451543, 617276347, 799709079, 235733509, 884875246, 817352342, 869749966, 379699255, 596138988, 588650118, 806570337, 15487374, 149090459, 439444769, 741181834, 824914178, 893382031, 100781180, 725633154, 571719157, 321271182, 51577933, 49591002, 307660689, 30466222, 918371188, 90069859, 891517665, 226386178, 989312489, 282102670, 153448406, 609213081, 62578008, 129474421, 260188408, 107227142, 165290276, 791835104, 975127238, 103675838, 279754121, 415714232, 196831306, 725075246, 294571390, 58453356, 987988392, 552879603, 562509122, 456581296, 421707183, 263784280, 965238577, 694810578, 995827080, 975078326, 814736777, 403189988, 307505771, 249215714, 49650831, 140914689, 119788554, 295357409, 42245667, 64328845, 930858870, 639435948, 104871472, 880786387, 679627880, 80285217, 252173494, 934045690, 74944081, 688063600, 137347859, 626507176, 37390755, 309220665, 610801216, 567489123, 108988682, 924492, 335700266, 222937324, 211440952, 118203337, 277250682, 172652069, 866136414, 629816875, 490152559, 468217478, 686563677, 745282957, 46508831, 843686206, 183774533, 914722829, 474901241, 264973068, 953215229, 408865167, 14215857, 479774876, 569395658, 477810379, 136323361, 43473659, 726130960, 253465819, 908087798, 166228153, 247415124, 924897654, 826736190, 807673901, 585223328, 372392020, 189502890, 249730709, 105703102, 921138625, 77570174, 128417894, 971249258, 475382866, 657962042, 98238368, 816294457, 385346147, 296570192, 218135212, 877506004, 717134220, 288976980, 840064241, 666877278, 612843327, 921260131, 408324831, 983981675, 893906387, 5847563, 78476046, 670105028, 623669632, 444737404, 243778337, 272052992, 563341240, 90471650, 755633991, 753623102, 322903998, 18220644, 738911016, 519999764, 457939332, 149893541, 421869261, 737039227, 226019991, 83794806, 310520919, 131953617, 371649779, 386163490, 89037155, 413433381, 277789744, 45253619, 463465414, 726076998, 352656308, 125953934, 97083052, 640415337, 566181545, 186625279, 812126347, 268755161, 74826101, 522283294, 317046530, 68381967, 63569578, 20864089, 450491024, 55584345, 424045252, 689907656, 515198556, 197814646, 702728251, 826108817, 625628595, 565335457, 868919130, 148282435, 430101167, 361952035, 480711373, 0, 666503677};

signed main() {
  ios::sync_with_stdio(false), cin.tie(NULL);

  int n, k; cin >> n >> k;
  if (k < n / 2) k = n - k;

  mint ans = 1;
  for(int i = k + 1; i <= n;) {
    if (i % C == 0 and i + C <= n + 1)
      ans *= prod[i / C], i += C;
    else
      ans *= i, i++;
  }
  for(int i = 1; i <= n - k;) {
    if (i % C == 0 and i + C <= n - k)
      ans *= inv[i / C], i += C;
    else
      ans /= i, i++;
  }

  cout << ans << '\n';

  return 0;
}