#687961 (C++17) No.1561 connect x connect

• 問題: No.1561 connect x connect
• ユーザー: 👑 emthrm
• 提出日時: 2021-08-11 03:47:14
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 47,544 bytes
• コンパイル時間: 7,018 ms
• コンパイル使用メモリ: 453,556 KB
• 実行使用メモリ: 4,348 KB
• 最終ジャッジ日時: 2023-10-24 18:04:44
• 合計ジャッジ時間: 11,209 ms
• ジャッジサーバーID （参考情報）: judge12 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	3 ms; 4,348 KB
testcase_03	AC	2 ms; 4,348 KB
testcase_04	AC	2 ms; 4,348 KB
testcase_05	AC	2 ms; 4,348 KB
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	2 ms; 4,348 KB
testcase_13	AC	3 ms; 4,348 KB
testcase_14	AC	6 ms; 4,348 KB
testcase_15	AC	8 ms; 4,348 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	AC	3 ms; 4,348 KB
testcase_33	AC	8 ms; 4,348 KB
testcase_34	WA	-
testcase_35	AC	2 ms; 4,348 KB
testcase_36	AC	62 ms; 4,348 KB
testcase_37	WA	-

ソースコード

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

template <int M>
struct MInt {
  unsigned int val;
  MInt(): val(0) {}
  MInt(long long x) : val(x >= 0 ? x % M : x % M + M) {}
  static constexpr int get_mod() { return M; }
  static void set_mod(int divisor) { assert(divisor == M); }
  static void init(int x = 10000000) { inv(x, true); fact(x); fact_inv(x); }
  static MInt inv(int x, bool init = false) {
    // assert(0 <= x && x < M && std::__gcd(x, M) == 1);
    static std::vector<MInt> inverse{0, 1};
    int prev = inverse.size();
    if (init && x >= prev) {
      // "x!" and "M" must be disjoint.
      inverse.resize(x + 1);
      for (int i = prev; i <= x; ++i) inverse[i] = -inverse[M % i] * (M / i);
    }
    if (x < inverse.size()) return inverse[x];
    unsigned int a = x, b = M; int u = 1, v = 0;
    while (b) {
      unsigned int q = a / b;
      std::swap(a -= q * b, b);
      std::swap(u -= q * v, v);
    }
    return u;
  }
  static MInt fact(int x) {
    static std::vector<MInt> f{1};
    int prev = f.size();
    if (x >= prev) {
      f.resize(x + 1);
      for (int i = prev; i <= x; ++i) f[i] = f[i - 1] * i;
    }
    return f[x];
  }
  static MInt fact_inv(int x) {
    static std::vector<MInt> finv{1};
    int prev = finv.size();
    if (x >= prev) {
      finv.resize(x + 1);
      finv[x] = inv(fact(x).val);
      for (int i = x; i > prev; --i) finv[i - 1] = finv[i] * i;
    }
    return finv[x];
  }
  static MInt nCk(int n, int k) {
    if (n < 0 || n < k || k < 0) return 0;
    if (n - k > k) k = n - k;
    return fact(n) * fact_inv(k) * fact_inv(n - k);
  }
  static MInt nPk(int n, int k) { return n < 0 || n < k || k < 0 ? 0 : fact(n) * fact_inv(n - k); }
  static MInt nHk(int n, int k) { return n < 0 || k < 0 ? 0 : (k == 0 ? 1 : nCk(n + k - 1, k)); }
  static MInt large_nCk(long long n, int k) {
    if (n < 0 || n < k || k < 0) return 0;
    inv(k, true);
    MInt res = 1;
    for (int i = 1; i <= k; ++i) res *= inv(i) * n--;
    return res;
  }
  MInt pow(long long exponent) const {
    MInt tmp = *this, res = 1;
    while (exponent > 0) {
      if (exponent & 1) res *= tmp;
      tmp *= tmp;
      exponent >>= 1;
    }
    return res;
  }
  MInt &operator+=(const MInt &x) { if((val += x.val) >= M) val -= M; return *this; }
  MInt &operator-=(const MInt &x) { if((val += M - x.val) >= M) val -= M; return *this; }
  MInt &operator*=(const MInt &x) { val = static_cast<unsigned long long>(val) * x.val % M; return *this; }
  MInt &operator/=(const MInt &x) { return *this *= inv(x.val); }
  bool operator==(const MInt &x) const { return val == x.val; }
  bool operator!=(const MInt &x) const { return val != x.val; }
  bool operator<(const MInt &x) const { return val < x.val; }
  bool operator<=(const MInt &x) const { return val <= x.val; }
  bool operator>(const MInt &x) const { return val > x.val; }
  bool operator>=(const MInt &x) const { return val >= x.val; }
  MInt &operator++() { if (++val == M) val = 0; return *this; }
  MInt operator++(int) { MInt res = *this; ++*this; return res; }
  MInt &operator--() { val = (val == 0 ? M : val) - 1; return *this; }
  MInt operator--(int) { MInt res = *this; --*this; return res; }
  MInt operator+() const { return *this; }
  MInt operator-() const { return MInt(val ? M - val : 0); }
  MInt operator+(const MInt &x) const { return MInt(*this) += x; }
  MInt operator-(const MInt &x) const { return MInt(*this) -= x; }
  MInt operator*(const MInt &x) const { return MInt(*this) *= x; }
  MInt operator/(const MInt &x) const { return MInt(*this) /= x; }
  friend std::ostream &operator<<(std::ostream &os, const MInt &x) { return os << x.val; }
  friend std::istream &operator>>(std::istream &is, MInt &x) { long long val; is >> val; x = MInt(val); return is; }
};
namespace std { template <int M> MInt<M> abs(const MInt<M> &x) { return x; } }
using ModInt = MInt<MOD>;

struct UnionFind {
  UnionFind(int n) : data(n, -1) {}

  int root(int ver) { return data[ver] < 0 ? ver : data[ver] = root(data[ver]); }

  bool unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (data[u] > data[v]) std::swap(u, v);
    data[u] += data[v];
    data[v] = u;
    return true;
  }

  bool same(int u, int v) { return root(u) == root(v); }

  int size(int ver) { return -data[root(ver)]; }

private:
  std::vector<int> data;
};

template <typename T>
struct Matrix {
  Matrix(int m, int n, T val = 0) : dat(m, std::vector<T>(n, val)) {}

  int height() const { return dat.size(); }

  int width() const { return dat.front().size(); }

  Matrix pow(long long exponent) const {
    int n = height();
    Matrix<T> tmp = *this, res(n, n, 0);
    for (int i = 0; i < n; ++i) res[i][i] = 1;
    while (exponent > 0) {
      if (exponent & 1) res *= tmp;
      tmp *= tmp;
      exponent >>= 1;
    }
    return res;
  }

  inline const std::vector<T> &operator[](const int idx) const { return dat[idx]; }
  inline std::vector<T> &operator[](const int idx) { return dat[idx]; }

  Matrix &operator=(const Matrix &x) {
    int m = x.height(), n = x.width();
    dat.resize(m, std::vector<T>(n));
    for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) dat[i][j] = x[i][j];
    return *this;
  }

  Matrix &operator+=(const Matrix &x) {
    int m = height(), n = width();
    for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) dat[i][j] += x[i][j];
    return *this;
  }

  Matrix &operator-=(const Matrix &x) {
    int m = height(), n = width();
    for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) dat[i][j] -= x[i][j];
    return *this;
  }

  Matrix &operator*=(const Matrix &x) {
    int m = height(), n = x.width(), l = width();
    std::vector<std::vector<T>> res(m, std::vector<T>(n, 0));
    for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) {
      for (int k = 0; k < l; ++k) res[i][j] += dat[i][k] * x[k][j];
    }
    std::swap(dat, res);
    return *this;
  }

  Matrix operator+(const Matrix &x) const { return Matrix(*this) += x; }

  Matrix operator-(const Matrix &x) const { return Matrix(*this) -= x; }

  Matrix operator*(const Matrix &x) const { return Matrix(*this) *= x; }

private:
  std::vector<std::vector<T>> dat;
};

template <typename T>
T kita_masa(const std::vector<T> &c, const std::vector<T> &a, long long n) {
  if (n == 0) return a[0];
  int k = c.size();
  std::vector<T> coefficient[3];
  for (int i = 0; i < 3; ++i) coefficient[i].assign(k, 0);
  if (k == 1) {
    coefficient[0][0] = c[0] * a[0];
  } else {
    coefficient[0][1] = 1;
  }
  auto succ = [&c, k, &coefficient]() -> void {
    for (int i = 0; i < k - 1; ++i) coefficient[0][i] += coefficient[0].back() * c[i + 1];
    coefficient[0].back() *= c[0];
    std::rotate(coefficient[0].begin(), coefficient[0].begin() + k - 1, coefficient[0].end());
  };
  for (int bit = 62 - __builtin_clzll(n); bit >= 0; --bit) {
    for (int i = 1; i < 3; ++i) std::copy(coefficient[0].begin(), coefficient[0].end(), coefficient[i].begin());
    for (T &e : coefficient[1]) e *= coefficient[2][0];
    for (int i = 1; i < k; ++i) {
      succ();
      for (int j = 0; j < k; ++j) coefficient[1][j] += coefficient[2][i] * coefficient[0][j];
    }
    coefficient[0].swap(coefficient[1]);
    if (n >> bit & 1) succ();
  }
  T res = 0;
  for (int i = 0; i < k; ++i) res += coefficient[0][i] * a[i];
  return res;
}

int main() {
  int n; ll m; cin >> n >> m;

  vector<vector<ModInt>> as{
    {},
    {1,3,6,10},
    {3,13,40,108,275},
    {6,40,218,1126,5726,28992,146642,741556,3749816},
    {10,108,1126,11506,116166,1168586,11749134,118127408,187692415,941503421,64334502,171422003,349404639,414370691,229496053},
    {15,275,5726,116166,2301877,45280509,889477656,470102989,131617800,543346538,672693081,528691884,433100319,259856352,631703746,121492784,65000963,67868821,431503520,556143263,898859209,822402657,746831347,942022314,42461886,245383965,159194955,442319965,719053964,735342087,986228635,385914410,746460380,499191314},
    {21,681,28992,1168586,45280509,732082734,37461992,885687205,403247903,630794366,96311199,188560385,132214957,81864959,656832813,129969437,337127917,885747691,994734031,901081506,113735510,330166803,692897482,221245902,823578678,149151767,513212823,565413378,343413792,552163984,401017125,775469314,768705741,822998669,524634565,141276343,644398112,617812249,791340223,983870515,203398182,625614815,683890375,368195928,142285464,986226417,160965035,405204827,206471233,652493150,587867820,808610901,707659600,22802536,445444835,187616183,160982744,457176050,436730256,169883893,240716120,405440669,340484060,656210817,36771327,96126498,306426249,814430155,444930212,988328253,540530995,382743352},
    {28,1664,146642,11749134,889477656,37461992,949940562,34890374,408395779,465431123,169444072,476095424,659247954,873440607,926228358,615656154,946323264,52968124,753942504,466886220,131497623,574943442,651491966,558045773,251030380,281770571,626734327,538734009,338782739,544266404,882070771,638524752,866251039,377115307,677270990,923683803,407681394,135644897,799433050,734586418,252356851,562319011,202766611,459305661,237631148,937873188,999735041,471421437,196454674,548587822,155433694,513218158,425727801,201766011,618282733,853358524,794224019,317787454,420202005,208101995,561508157,165138107,680690785,440574802,642204069,1519935,740668820,993620892,358321040,609591537,544950607,452208170,885834624,821590676,398458087,516061104,713420418,988022777,345184826,285034175,821685364,13669476,704448103,129864472,272789356,791468167,22642555,191074948,725893030,621310461,91319075,716141215,100651620,124026881,366140815,685675711,544588613,31892809,733368799,814661720,416829950,25354705,920576064,404858750,224503153,408647840,32879424,449601451,954308700,384324116,674296838,792515237,188224955,323348585,972509240,558237931,478379644,769454589,5532215,665030504,378063244,50177022,152536855,592606999,936002695,561844587,98320627,393845743,234288387,975460550,94761064,230083310,437478027,493404365,809166706,952865395,30537948,269093029,454344596,528546169,743583991,647074729,593751773,863574928,753557944,354148307,464934709,275033859,450276861,375178856,24286587,880771043,120621725,710396662,135056587,742687865,845401042,8181486,277891374,585736419,570298110,955283694,601817563,141857657,613931527,134904117,127307580,914760872,56527073,515151064,85256390,867641311,644658123,516456196,546485053,695768127,950249035,737354235,328196921,664437558,654797167},
    {36,4040,741556,118127408,470102989,885687205,34890374,247777016,233426110,328755371,705627253,787442872,382905968,14599213,54410761,601006292,612557411,15449456,990194963,286282085,699722725,781620769,840139026,489073872,334785849,435236311,109774734,741619354,198733961,979223831,316303898,39151097,758722723,846456337,302710767,751509519,910422866,269441528,739223079,47041872,144990978,835832181,94144832,432122371,718847361,143249505,202420879,524474077,175432350,259981775,949834434,650788361,314338901,308488393,925015945,735629952,55340122,870087004,914406437,652461932,824517283,13384791,734924498,195917202,347913012,345009223,72962601,728865665,529666843,443583543,797807890,499559112,582526183,750449603,794171249,339435367,795879914,610395113,651525515,665256279,771083632,124044838,103256298,555278857,168723782,37135886,926137424,193565944,44104251,848927128,311714530,740363205,103826476,426742610,675142274,731839743,444416323,663478468,724122696,351972777,394976529,438819547,910482232,104665901,409225876,167205682,514913255,760105145,29299318,710711305,114816263,854763814,393789740,110116602,971095517,965304627,656067527,345333181,54369787,393350947,645767328,278297447,584309442,643959646,760481447,306899117,556007296,90782544,501999191,487093902,851119019,214855164,290938704,483935411,931413698,87706720,543982301,557974404,993894344,617966931,450284946,530064541,635450110,955879320,855098870,534537883,745899211,102957101,662330955,760521286,880202513,410332359,896841550,21942388,327590993,607470931,510274101,755158989,271684724,681115728,979634385,116288824,441075062,869557219,498624604,668265455,563569496,411144207,372553915,26571455,299681786,483501145,332251237,514296631,262088005,767350800,242709545,312245270,625558060,630739736,166453361,987400268,534085288,177342293,635886216,360697926,830064107,142999667,796390630,541632626,524331979,832128250,56784302,599770934,420185002,36118708,960687380,886180310,494123322,256629996,167297430,422622751,387880447,805197257,990906673,197392117,409215677,751867399,114891717,20016317,539423303,506437722,420323843,17970683,326175155,607163024,810675077,843118080,586603097,332437402,683685949,604167445,591515392,281318475,78155302,77262870,295568742,84378564,642943804,12418388,229594263,734305604,17384828,186823879,593406287,961690928,25278271,599757507,378599083,885999372,931931154,847818732,310703306,179718037,657210250,145528035,460498835,941558183,335135033,141616629,159440568,260876848,890714211,188331960,684788951,962770200,647749365,692000110,84789890,537064226,34450693,41361159,550194872,245249510,900342927,708273455,11582750,128969774,512056024,55621840,349004103,637116327,221258619,579454604,113893155,576214565,70474670,23918406,481813326,650352628,246808992,284149773,322921320,932867440,994253316,940618752,728504628,428989277,122474883,119546567,24132989,106306057,431011676,611024275,216092722,58878209,120907053,721629563,912245906,362994491,77928369,598179975,862251408,302060801,740845851,459478020,470575531,272055896,271404799,997912850,546477555,102801686,821058456,253389281,766070116,630671870,387593406,363890599,503970373,198459011,993364983,210948547,542855600,819226189,105570790,913838629,104902492,762607730,954174415,72362182,262189042,660554698,644882931,306650491,22189921,453123535,325669077,343206525,974951457,351413353,739439727,691749300,370158155,944047087,188614448,382554560,385741341,62378861,740868823,256532720,721260792,546722312,476298563,606762613,98776597,898445055,605244416,333859175,433695415,401161555,572855900,243667256,85343275,675159111,922771403,996753883,954048792,469148681,19943310,296231983,99393046,204271242,312577414,956614050,159362747,723539464,111719269,894138283,588450712,602782641,981925081,900433722,180543976,267328359,522848269,4196876,67000221,107779275,321728788,528597009,269434052,964941752,949825535,975030569,458728260,549511657,418171228,245570031,648210002,972434486,581872841,635344873,319802131,678265430,806155028,954458488,526854316,847377932,635338258,992797405,996032138,354562941,45336905,183006406,369367986,247817599,491651791,494803388,962480389,263666033,589248787,333002562,984917436,533517314,834849849,760791455,813814450,264438765,491534108,918145304,179243081,160538845,82373668,881806227,278695929,385349193,933393279},
    {45,9779,3749816,187692415,131617800,403247903,408395779,233426110,197302784,177620321,206888828,835061252,770003207,167817536,517820843,580617827,469175694,251779825,370582103,72645164,713328911,277616510,902795788,659852725,220506451,987735057,337008278,326694483,929531709,623473947,796684890,777051644,795130911,868689620,888962474,15266105,133906102,896971307,432781360,609904712,139195228,582320632,810000435,144947710,694533822,353828777,974567746,545012102,655590198,684583110,709008352,516538184,177659042,730381723,46966182,70580724,546296538,649380101,839329069,521579662,795443379,918648017,416884199,467381920,180180330,922394205,388926319,338398209,519862997,15436054,832899909,25205988,638023458,397967187,958525485,625245409,761065828,308642848,984865575,166574801,351074508,483949359,826042702,587151802,332893090,23588721,198575871,217064634,935342647,875830166,870762060,431430866,714037905,451514552,118685251,876908840,648215587,848279668,60298648,631459253,423970402,946540283,520092027,98956341,792001638,336970096,931916670,592163792,698538791,255778677,599081543,736931826,498542055,487642144,167722474,425497074,479036070,196741185,39983686,490171826,41410688,950392180,499418290,916512858,995578975,364239372,287759310,305160181,776807436,795631950,394372202,993536736,574952319,609892554,374430406,859025147,436507546,532241817,70196027,667557733,86629981,53437441,215255354,775586987,386301783,329730035,202594580,163573385,90440286,830055244,592282175,146234819,713607860,431108208,391672172,89707230,227887893,635772628,670074546,823064293,429723599,720075550,708101376,728992627,35839866,649628048,777233024,769395244,273231976,452388241,103609465,50984607,571111271,37433616,645071594,241717405,852257157,792730997,762093846,260970344,710690387,581362111,325183396,887018246,894572200,248056865,450822007,28780679,485097554,610718927,844021940,806875641,356112859,159635847,788536148,115844061,32006334,343606685,949709181,501111333,368083991,85114366,231716730,758617505,42613424,792424028,406591750,7556235,372313392,875852936,303229657,493990389,413068577,970321428,914931582,883280547,348694252,48829705,693879473,956820845,494398843,524838672,55642290,291803820,838072276,937627886,352806075,872719356,645619108,203657091,833772501,188791198,15808272,336497713,294256664,801099446,152749995,41154832,192492036,312034558,714016971,939095632,362217612,344871905,183574935,889188174,138994256,960429161,296389559,883734447,484177868,83759713,357767259,405799384,404997964,179592455,903922102,309177362,762328559,846181321,186860329,535482051,303516149,218656364,107450950,239712834,878534309,957325925,369018716,743188094,890784475,179418699,403243176,82350077,760467414,628649939,536068242,546840675,460160401,131727617,556807821,103868149,100658424,320228785,310512098,723638547,644759206,54096166,438468025,280923557,715718353,545633130,123399383,171267284,991718619,983352761,402614189,319762846,922715169,183148106,404824713,482568353,237420087,669034731,275370689,906758281,912995718,736734514,669078916,551700747,844999682,490707946,397056376,72201274,440950741,308110319,99342341,252577468,439457763,862615164,97430404,650977533,227567872,732837766,486412310,424158571,314727501,706889056,657623511,936876993,355562470,9669720,793140369,959968300,899351234,219020216,880286167,595856391,493610283,799709671,824990610,720595839,329639104,976749337,936889221,809494863,315709609,237042146,110330913,567862810,101728268,746956576,529866255,586725298,648040801,779748452,153236583,914584631,749408847,513718701,14088744,993137657,564190068,564615128,218058108,134675641,474742395,687879968,690548088,277156362,833518401,580665444,577772528,19376544,299323127,895099027,299338547,839803398,687138570,578794727,71021961,41918341,510329763,609712540,451003507,709704951,186996194,578245109,487769767,658075788,864769755,506366568,233278984,86797707,695583509,153704084,307322932,831266923,199868472,103620682,993020713,659107946,396528525,448813397,73914984,907386095,831778457,594736347,150616395,988883526,366215643,167086401,868932945,313717943,593312471,235565012,521329248,311252446,123949902,964499849,144982401,326364967,391588166,501164095,279706676,683502822,592927881,202357005,297878695,111559939,437962853,837545570,371947446,187758155,101943565,305769633,487510260,916387514,682044268,61059324,657929288,460684128,163896142,161536407,538311886,723564214,36418739,327436336,989827281,124248645,832708688,882308790,710452531,77716353,875129876,836074411,531835865,56875321,833407105,423331035,393581722,167353704,46338145,795984501,429448793,921170554,895713357,399606530,448677100,376663936,565811400,301582936,103096130,89229646,456280484,935984940,257863967,62176804,520077003,989724020,230216016,198426323,232816551,723398169,947598119,145563483,543560195,769283254,687695853,412141785,458246892,322562821,870174788,792046447,992281653,261650102,321433331,28258915,361339155,916537223,304030644,26483722,311683688,962388783,635976431,109322303,111089464,562711339,932659823,884184806,961770497,482763443,787907009,283606372,844167426,96801505,102993913,616787769,332259272,90020691,33473958,108789187,901500422,168357636,853210301,871337077,376008840,609311701,33409148,458480523,530786778,390698056,481382022,680007463,849208790,270019810,368593263,287960378,683678741,840373286,472091096,256821798,909688373,636672904,857109891,992260814,638259714,682582093,715207690,600484323,181860536,177868141,849248564,743213709,255749170,601589780,577202203,715681221,735331176,522995960,337047396,380280967,562020808,449068543,963757501,321956499,151307217,161277903,285233282,762020021,339297753,69679348,52568303,535629098,658030018,319086680,600634301,532594728,293331051,603165887,881090116,441710021,197876329,311209998,65489057,438038471,846586492,841740111,900892505,272268279,272662986,89882804,789135775,548746487,93712454,214835785,687205843,809953436,716639879,931867150,5763196,404820388,529438877,222826259,393767310,372063277,755012934,553961581,34305285,137826363,970617902,758748623,22630688,297099624,233382191,919549105,715661682,204181124,621028315,733111353,820512193,577134999,902996456,829943695,846032894,905693877,542196551,252622955,523732069,530997965,533006837,460888302,533952669,844001205,812367056,483211338,158530789,288773918,681553155,968699783,254686618,449601998,599196037,225007854,290070160,539848030,608861062,188322344,747926660,538066172,847178687,798739308,292443380,645523492,583709863,519984309,947227788,785996221,849492107,217296632,379082083,328454321,948218307,458921548,733036260,335345610,773876458,744463437,69765238,106787889,312188870,578318834,7590839,644251670,957688430,335704885,472634567,890314526,887231598,869685716,675313178,908538033,362098899,320019526,244292819,322269049,505039770,483852205,866472202,694039567,823738103,892325140,758360001,346368562,815348254,412182503,471602176,990001493,666290216,161636116,879511684,412410210,446019037,337121630,658855385,784637957,536675583,404218240,960104489,897138435,48992282,548012990,560174715,792156454,160189169,705905872,573054279,928960434,598430005,723118328,3133966,709956394,400173006,843883821,846982537,379029168,361068204,661888589,887835679,493479920,976133608,354917572,765784969,49078976,364396665,502948009,205972104,807960031,802286021,744327814,245246294,420470862,538828146,696329703,411129575,588274570,6230560,547505555,473360733,576825268,869928171,485124875,32250130,382711654,49947367,690021132,761491956,113839876,634613886,973389949,360297061,350465803,385111971,501526753,394165342,117902532,47188185,669058037,586179392,803534253,9867730,117081149,270343570,869732012,535560128,74135321,913166862,745264069,367865464,623137053,135895289,799585395,704614475,888437551,472048245,210649737,887519734,367380507,467654308,310951744,120246371,1570185,489874614,177001364,639465634,752300677,618186089,125694494,282846280,736316609,953882934,653497932,841032400,979929908,640731760,744566282,956866912,308789171,978715397,648405630,702106874,252210450,37223998,173800106,569247455,870763443,145425498,15568087,948078131,543632996,464071584,555186162,273468192,844935944,319095366,541561522,462755462,976898547,38432185,745007341,431518992,996017081,641720868,979768983,850953140,572191500,305562385,828023713,101969831,319513329,411569368,498489858,687104004,861506575,386766011,47630047,485950686,906252626,435904945,523398217,237981274,184197706,269135307,723734629,996762583,961708129,184077468,987996423,232884778,412092659,38185479,920544354,863648751,226193943,388570440,67028234,139276129,987378193,100903448,903580344,405505214,867338867,333622878,921218665,511487222,463201346,414182967,124574190,125984615,331268678,712901251,926814813,792501262,571854656,980486453,67546855,150063837,986275190,522883996,773384884,81195741,381162217,512867735,787522767,774407258,380624609,500979859,425339121,963880441,911568272,792258594,350130673,602869571,264295247,559699881,354311181,316717483,974583423,385148768,775793636,276045306,192338240,677282938,975826894,376504882,438875821,650005503,18308145,573861618,505201938,646594656,659950897,130894025,249286645,298317355,654311532,836465450,865286055,895177950,246676014,195480007,816931196,479506395,881134448,708030910,402627578,94318479,239737460,50326524,124781860,692461839,182412976,588599601,905280444,671991486,149716817,47905658,64714287,716724851,557647216,28241812,713896117,846376494,206401418,428739231,942397989,324941900,306688147,258918808,206428157,459115203,714606128,901629112,466484868,310408763,294905148,749311051,394101771,403806550,498739596,248404900,190125924,522025988,356210447,962389205,814535861,3980315,250331408,790031419,402340345,314834487,602818980,373056826,513025448,514106359,330630795,280415656,110664532,260357566,438075255,589257527,858090853,422891205,620257075,790506377,952563016,765975974,960893637,543352842,365161673,624020379,800469365,251809505,622790780,765922253,402911760,997555042,559439272,29544238,878217449,228591540,899811201,871109199,546784719,253989180,599758115,684560325,694533607,280703340,236096123,66961640,589317182,148043719,775804319,268637104,330635805,56702421,125110763,721113904,467948371,559561215,304843404,297100892,617590242,296473496,369817637,718004636,526124218,325406214,131642557,869709758,216629105,687991036,573256824,311737341,758758392,234589476,806451920,213768729,631008009,285161193,822185858,233315562,217016673,677480896,804760339,303459984,221413383,399022533,365958714,40799195,381705662,789465567,637528335,343565435,451970239,746068672,166867880,819274545,76504657,397541090,634573222,532288800,461447953,593079116,206340568,73124197,802335966,905865702,467513529,84938694,290540136,695515463,3667894,705686513,717484972,407798786,866250512,73759857,988625790,225509686,921183249,230949763,381533094,278804584,32480390,574582357,123789423,768169179,487732014,297765428,731832401,432860256,598148966,289492130,97013575,442023507,762069525,931825284,458140597,189544522,921471521,275855481,956391146,193634695,84677511,113885808,830941679,431684736,119795183,940323412,300483044,11521577,885580158,695593645,494983307,139383566,821276667,477452984,683243183,361935517,273621685,4025495,476432519,678629225,920228510,134283532,278793091,224178916,869681152,174441945,438098978,983179206,95895202}
  };
  vector<vector<ModInt>> cs{
    {},
    {1000000006,3,1000000004,1},
    {1000000006,0,4,1000000003,1},
    {1000000006,9,999999991,3,22,999999972,26,999999998,1},
    {1000000006,999999996,96,999999845,198,999999752,999999942,632,999999384,75,272,999999777,90,999999990,1},
    {1,999999956,198,4214,999956725,189183,999597590,999776210,3355642,994521618,997404693,13699534,990231089,999036138,6152683,983996162,21987911,993019186,991457770,7154119,997377220,2551590,998485993,999093191,1620135,999199739,57937,135637,999916042,26632,999994795,626,999999966,1},
    {1,107,999998535,999942165,999444951,576165,29348012,211895609,221240708,676073373,341916115,675315088,920984885,238042460,404633960,558683120,987311741,798387263,152522485,141958987,548131137,776356265,693304349,922972595,826291169,525852836,206268113,735369307,845202278,128167752,884756831,610711296,776692687,118575609,20151946,63313885,54201070,937991413,189155785,476519393,494464705,16230911,17050708,58083192,223981658,776332021,295194475,771592522,178497912,513975810,279183132,20514139,13495283,77586872,484591080,810715054,724108123,38479371,705040706,329658325,51719115,57940041,450143629,979867988,906653130,31995434,993958208,742664,999939541,3110,999999918,1},
    {1,999999639,18317,1077829,871297985,377828077,268322266,893859690,193151642,546075680,163144958,857050431,643028099,185267082,282174451,917027319,711496839,879877364,216060021,238738168,545507143,848519168,292515948,812221768,726241975,581730944,199917502,380930212,923821258,42318841,577438817,261081137,131675232,807714963,209521382,699721310,92016231,663456512,327508906,117585205,593161595,283088291,187978351,520826406,878622562,70022425,157361700,480907436,329062828,827775747,757086971,565229996,918227775,902941141,257377860,112578061,56215077,565005604,464117410,514468457,380434359,162686635,31341195,350408100,293616027,823002334,658110054,371261815,174721612,391327856,679311932,93801129,682932862,190435414,121257500,932826231,342326029,148956346,659915009,118820492,767746693,225262744,752536534,437308315,332843953,109370078,276049689,530161994,192214867,157062462,219979031,611914183,307899471,821387966,615079501,362587964,724968146,934272686,305237182,573883305,909141629,925480272,395988572,346792223,145790140,138511469,943629170,44511599,329034147,821505999,245028769,837735148,123407489,260120971,606062420,266458448,271705401,101415276,32775585,522079494,307209159,926030996,79252471,475290790,554514183,470510190,750895077,383849221,717726991,128921008,100000385,706798990,564758649,537648957,981566491,35095443,932952837,635711110,633413775,621647519,323641562,341123611,578059214,84252359,826122746,504256321,349823801,19585253,66759279,809781530,774230873,461783299,76368293,67908380,890068520,200913625,820027654,94569547,970845792,332838981,117842397,452410975,111188901,155729746,13623411,677300925,290384294,116600453,401128294,811285267,232405750,211651202,946233573,149828812,546845912,517360108,51265818,998708004,22133,999999781,1},
    {1,850,38843,977308292,224852426,589824792,355343950,566132089,57219747,305873657,328721511,89722122,960372939,777840536,803096862,435433334,58248143,76946971,852276450,439574410,609341909,730000703,521790123,828648704,440431099,444041677,421470818,729432528,665953195,335915859,573858592,903306923,119995213,982056241,323855947,952317721,113764870,488494822,309727757,950407319,657211677,718610519,369947189,258472507,852837503,213510789,473919774,155316288,150639864,380590669,43525788,174702108,13638879,670516234,860180888,419251246,799464827,871033102,801361388,884035973,216218687,988697472,181854776,637968858,904693720,126707118,527596252,408007263,844375184,596984018,947630136,387932407,615989257,777896391,603702399,952424240,93224809,163676569,908024031,547795108,857763370,590472721,694931701,561412994,686938582,850184166,823536228,420992738,221405719,631439798,925108787,690692127,397480957,789681045,645628517,894828730,749572988,644419759,809680891,884307697,542060632,887158365,565719119,673760737,545913874,84811201,982019810,599926992,641547207,754591084,430061171,767874291,896287073,794826272,116387497,560313486,805904119,153040947,54888582,979996091,580663937,783773695,886404820,35233189,357474416,708243855,852960749,85696197,240460506,542695407,438543318,577843235,340097385,462273498,560055481,562207598,531081907,663585254,377190644,630238783,700208604,268050333,962272241,593103076,737345482,300468224,389342496,543077435,783503620,529826205,590236228,495246668,419444183,203706709,90908034,342059370,184699732,353147020,546514652,437561632,293570497,364867970,446413026,500350824,239187866,488051217,6092978,486960845,968279122,907889336,58164724,602883516,446062789,83445555,355163957,654630136,521453600,733035016,944294748,294333309,557160850,522545766,549399509,902501522,18491633,738366048,902690656,353996002,69430502,144720094,579236359,509864003,278002827,2456839,220368386,493230361,227044504,153602347,271893670,475658895,405518105,660299181,229171858,162176985,212194261,785779519,526628766,104253907,72644533,480121030,826637650,895311508,302415632,814031151,18447731,226816771,612489667,136277270,378714174,762676651,697562910,79451038,339161210,192802364,437330438,577456543,531998487,469804619,7749670,334275891,945421669,486821786,828752073,706255236,111043596,420826464,858407370,164857387,580680839,349434449,349090587,583807218,863101446,346620116,230556813,794371622,7093190,562491712,434833194,830106386,652192881,603708479,251496879,712068630,689384867,712790652,649837950,995684701,323900502,623426624,400405900,75849368,245862381,280719585,146422653,327386893,755742719,41462608,851387499,683830859,732834732,517733797,313454866,19567651,274641274,652395150,73984848,699572773,512817858,81262954,914513850,842191624,397878810,369564163,849660169,366839751,379210257,759269994,970282204,944419484,320838066,211414346,934485700,922499010,201600983,384387352,508901327,926202557,150157191,224438207,334997493,192022364,155025630,838587591,988646538,799630760,530326097,113429770,356899672,496994999,392101680,671285897,63650406,308555979,962127145,981783870,67455926,170076746,666491770,808079315,362324759,303725740,819442729,774086416,652309453,1218547,627265370,134423267,667111524,259555183,439583198,933348343,978031986,512751191,332247614,236582603,207205455,556838458,283729103,906058405,803030761,340445857,883639965,385531334,189585922,911469844,186442869,861488883,723789950,758704660,528501014,452197323,642117922,206305019,968163964,417704505,290472213,733299902,41403686,375257376,668712640,26473224,784706585,54400905,112204968,302981624,864532307,362933090,187612087,522286080,918296796,900416203,996104694,689584959,265982407,836103437,25400671,240297013,506484052,637798607,303782980,617212988,974804757,652195017,941229752,663192692,347864702,999535757,387800445,296985699,996357368,857773494,745193967,139880593,664890364,683271338,68229010,231397888,469670802,168715782,368966218,642988951,947196857,546341165,349764997,360474668,946198532,929390983,710436225,488500488,944501774,236154320,41285713,502048647,525076163,120666140,284015712,898645900,467750756,704919909,243273237,630047723,80566125,842076511,741291920,725474573,238803947,429985264,7205002,53727628,174829068,987778989,728058965,982609880,121621,999999487,1},
    {1000000006,2830,998202226,78442197,444166015,674459620,706749917,861495097,692399212,294504257,734763102,249868562,711361075,104296235,369452687,125247389,228148626,685077842,210552637,900675477,344240382,641726662,825191367,267619825,974756020,860143685,466863065,576528085,769936442,705513480,983895071,477143691,502618921,330790782,238841009,307727773,829487121,75591691,180838947,839348444,335870847,75365727,302558127,639919449,291205927,422899737,973612005,842726551,809504464,302161847,882966929,117308643,840079405,999800271,434407016,950067297,255804362,942521929,393907243,837915820,660048988,577909113,659426486,437094045,199310310,800826621,872977075,556290208,647751516,924321812,393168509,968580027,751359956,242626014,378979899,261208471,243625359,301989687,9337295,902044767,610479020,156062732,652561608,971080160,95687532,38546435,352579754,911369151,129727143,965540209,179682138,820313351,932442780,918810876,184147235,545342710,515794409,360900093,408232309,156373582,595445633,562432957,583024151,685828869,323272209,389583309,667622574,250259693,469235669,82661867,399379037,629330435,323985852,824207398,274779009,336542468,520428784,47113815,889166585,578865195,476248978,394291560,340816142,569661057,816345764,567858155,637356187,590475476,388341900,969148013,610401104,445320248,272403274,302235622,403729696,231486854,639589801,720027672,319955565,994195648,323316751,480681648,916708104,976478434,516941111,819813666,937569180,253923471,634958064,100461791,863480460,787400483,710692718,62953344,272989769,50457832,297154735,577551952,843710568,24976184,896352642,633610541,576374590,676610027,374292999,344671879,137081145,905774037,198407224,955079918,191842250,863722183,120222650,715086356,638853579,877982217,398940074,402101930,13383714,427641079,267470783,762235392,171107996,349612330,166273016,629428967,193033876,602993,768338253,487579756,725647782,722941531,800106675,263123869,268420035,983168687,110633380,397532777,34486677,245791183,788490148,124088743,418454600,50517712,189407116,305217687,816250085,642711922,205901880,752283086,796970687,908139904,500286045,301100327,345279890,302852404,500279812,718651208,583016190,393133746,508964529,490680151,990209292,355512281,202656727,782562875,519651011,352174973,837589465,851791236,879024123,277893038,681632451,907284628,354840271,324076019,514012598,928841024,695104685,617153235,508150451,149104414,730827374,332721000,739393510,455214611,274957208,100199628,237934207,277268937,776788528,388760860,502013715,606244755,665103011,888935806,740392284,225339137,433159860,29616323,455908563,688623396,855472087,418470057,176033345,805667525,61427551,848851954,632327355,462483489,783408725,15716078,380825421,56768936,64517365,5964243,577580146,636135321,41781169,15193421,981418181,522817670,547461158,746233170,929891152,793890934,49278931,729598924,427805571,34154355,349779954,295950529,797882659,384395578,882929487,823479844,720329351,567015313,545273792,346340655,42238937,99036299,118627048,864831660,606243935,237624348,798249471,142980133,989631917,815451060,35350184,502864659,917636208,818209109,85145094,23871665,988972988,364800199,289964743,70775864,54062691,511084926,130958636,461760111,456692341,407482391,61834394,722994210,886081515,639133718,607374561,108703025,462253958,505963973,592391551,11524455,17382277,321958510,38089218,861935900,578421205,100816774,952848342,751696047,723319887,967312702,851639756,90907667,76763965,562446339,506084552,476167235,874277287,394311274,932366328,89126870,485983444,148767413,705685913,490480930,493929496,437940916,927239385,722266704,796592514,812168470,741719695,720902059,158159430,338657790,864657245,752747760,761006149,738432134,761714354,687563048,21185636,444905336,918386893,365001136,389474596,794072866,256867466,334996708,15611259,83604729,828058724,299894639,661483156,644869612,548948047,49840930,328578142,148423221,968293247,682403108,93899888,986617306,190384062,887799652,801735376,744072262,407860414,13919165,741146076,660064255,722435496,962877678,514840676,898717942,493004813,647978083,331956502,626390971,73236452,164822117,649393471,960588710,253547527,876664013,178315801,427811238,734647597,605998407,663070607,612183298,529219228,550265866,102854731,67363836,697527461,742233487,993520154,107881930,757885199,659723037,453436298,399155039,362683831,528665456,123946819,824031155,300840049,521963079,178355283,392309173,573846132,356281683,80484367,819566210,970073278,865608001,949644232,886436947,809660555,19205041,137664581,563389769,348094629,829681127,344648958,418826495,103817575,187784311,268771803,923644861,521525761,594865117,601130188,523812771,58075351,281075790,496762430,309842828,135452402,862716816,752021384,92066698,870475103,179184395,231683728,122452833,62649118,956060464,698437501,648302165,244487576,294781020,963745520,689147663,890966556,716233754,788615493,834309630,326600816,888689493,132168363,914916605,177556551,436734522,61946450,524906813,830274486,97194216,485432719,416396185,535420954,878745857,784111517,987089736,423580019,336685110,563296471,820967634,545015436,958101457,93212799,176904473,449573203,234331302,495668709,496449401,860326027,160082770,41519528,260280758,592217643,759435334,317067808,863216709,479488490,888110697,448264531,526225648,425599814,328461500,308693780,329470574,887141640,108699309,101688111,98851645,137085595,834213503,109243689,514833,706958673,597246427,659448949,511178348,111535658,887611461,387740481,822281455,522750228,991872604,770328990,461217484,238091229,555642602,450009688,431791768,635720729,463542957,443726190,282673140,339108439,246439089,242003185,944104244,483316669,866944322,838672,175684819,305920251,143901315,10206734,644743445,155422657,885649457,793293168,762184454,907627540,600645274,853894182,801318026,239095347,420832395,837765599,809636616,908779048,145634981,163417638,273311414,99293964,781511521,916355960,163647083,448701061,221868248,708123227,462714259,300677987,321173468,814924575,167571210,476965025,876462511,193497833,338025707,992763583,664282057,505038856,210694213,335967887,781433901,899433543,721080291,553300880,921068146,597267281,370848153,563041269,675166660,252889099,139626039,532876855,513850403,792151329,607741011,913554812,443218927,327275188,228071352,713007028,571412759,958553647,859428450,515911260,674919117,242536390,577231116,77278279,963081675,940995412,661377657,665874851,444334755,746870966,950764922,581572980,768821892,722682687,625377850,1079340,73056708,397516033,522837466,284749271,136109704,729476310,923729003,985019676,602307025,166000409,677841260,578488155,639490913,511284994,968783942,860947276,679386464,703150156,273631310,177825658,655357702,24456515,91932472,335250356,379352121,526302779,573796043,120056440,540166926,474554916,95735934,689192126,964597128,105157797,786742556,335836890,740663132,291386311,234860680,39625246,619396566,129554943,888561310,632949179,31166870,8586882,417769653,524168039,716349128,548245010,27476215,501915110,731823406,56407029,240809544,890817174,624410345,913073972,314375597,794766334,227470782,625727136,242817999,288326091,813168849,870140021,881828835,487122015,830134796,425371988,923561626,693804635,812783458,642140859,584814673,178791476,185986944,310454767,518509829,391972274,174743385,361858313,600488256,720884286,386906276,550508162,222515632,508079938,892515125,527094987,653995891,53758664,549437872,571765352,272666228,791581147,853134294,424127744,695412533,24490596,36775454,589633475,630858088,548753964,794365040,590981153,11032266,432874269,853604087,46958408,316598487,286533478,515745945,408659279,878310198,73222325,123388453,304445917,611090572,246856578,854610996,758080922,187997959,135713567,672775134,896682737,677326463,435855305,121222552,69911011,849911462,385117354,121049105,63433967,868845304,388113918,798957510,732338572,95752265,681655812,889279307,543282539,966949225,118932777,310193629,404304927,912191060,430016053,676879587,640608445,257773156,90380511,744275649,374835562,3579592,995045809,634488588,716814465,836960011,138903129,499561074,256021584,934929168,478650666,988166857,967738727,693687635,229105402,447806631,745047820,713512692,120298036,638310372,462518581,354565784,359629911,679142010,168077726,519729553,198634940,975304356,920284560,565038799,509375238,670279037,921924998,88393916,392123474,521460412,247305708,225421199,500985325,827133960,221722543,911248450,214289642,885173340,868776133,308038108,755158690,508482473,244701079,464324063,463740456,923365863,673723287,570833325,579557574,61014214,542405816,264719437,456424734,386888293,259823103,339303689,606265167,183022332,664226175,252964523,922834877,331552052,447171964,769671472,45757574,58221448,237429450,884058526,543500774,138632529,960044698,979894319,20856496,236485719,646508845,933859774,696125856,220708288,116963784,111991111,750773942,791872863,936108821,326062761,316162961,117566958,742575387,252003793,308335078,483333177,976504403,505227200,967051752,748623169,565021830,363996303,188431674,136741667,220961381,88982515,636571429,611432218,780917052,1885352,204584119,214273614,17785829,770314431,293875220,117333624,308596107,956319182,371209236,558409401,477313943,328195479,498306982,779132099,738357704,383851216,374192297,767325231,829364850,624194385,818808524,582462971,208486309,287008859,144702297,433785701,695815112,164623856,96073570,649254832,359258633,132710029,555454982,708243130,27619428,842747259,571414884,155794470,117149360,999584994,13967106,748945885,91818874,100654646,398326064,493818683,788550460,537533994,109891184,217290022,684279558,220840085,59598160,94677753,155686467,239678521,78674131,380585151,691315867,370185013,768323323,835216831,804562453,660910612,15314268,588463039,809919285,397105781,453868374,157565365,180599476,860340857,311452627,425045195,530252777,963233328,746293387,489300064,521405223,48614053,635074760,302054688,869882201,189563926,486136046,464841646,663116966,66561015,393885569,13378164,125962869,411616687,137222963,180767932,721939712,779736102,612638585,973570163,977582982,624993249,912776511,323867994,133383727,628053072,150026338,142009620,310846754,499621443,120141812,766499510,307764773,135626065,25410440,155813558,534910961,14657389,582559393,42457358,607934591,281553994,30273821,920243768,19294036,853688947,910627798,531565266,78603207,141663455,872051934,924419979,602143401,993818110,734377890,956499001,491366042,621707852,360685647,701518041,472959112,817127197,787384611,964433169,814163441,805684845,899213550,428156850,393656163,114712417,156539568,793592044,996256970,593471752,313191103,105271580,807716175,226472927,318980353,831719578,827359956,62649533,520150234,314118749,217921818,953269920,707636504,739212293,330692428,564082255,184452281,17237043,9071147,148346572,161756750,881538231,308839561,752030222,955271760,204769497,799294492,648265703,638095905,532785966,932574756,749044898,578760298,606272291,296760831,270722166,83516262,836049554,33138204,75423150,153438989,87909285,39013644,446606388,80796745,924200673,418277007,318998174,770794884,975557621,995034273,907504359,527637438,175887743,390941572,387967057,992867728,383389817,963591976,90720607,374416355,471704457,373172336,465917941,426029874,663342771,723603795,263188713,525538310,512955430,636765977,887468,999998634,1}
  };
  cout << kita_masa(cs[n], as[n], m - 1) << '\n';
  return 0;

  int size = 2;
  map<vector<int>, int> mp;
  mp[vector<int>(n, -1)] = 0;
  vector<vector<int>> reach(size);
  vector<bool> finish{false, true};
  queue<vector<int>> que({vector<int>(n, -1)});
  while (!que.empty()) {
    vector<int> prev = que.front(); que.pop();
    int id = mp[prev];
    if (id > 0) {
      bool is_con = true;
      int only = *max_element(ALL(prev));
      REP(i, n) is_con &= prev[i] == -1 || prev[i] == only;
      if (is_con) reach[id].emplace_back(1);
    }
    FOR(b, 1, 1 << n) {
      UnionFind uf(n * 2);
      REP(i, n) {
        if (prev[i] == -1) continue;
        FOR(j, i + 1, n) {
          if (prev[j] == prev[i]) uf.unite(i, j);
        }
      }
      FOR(i, 1, n) {
        if ((b >> (i - 1) & 1) && (b >> i & 1)) uf.unite(n + i - 1, n + i);
      }
      REP(i, n) {
        if (prev[i] != -1 && (b >> i & 1)) uf.unite(i, n + i);
      }
      vector<int> nx(n, -1);
      map<int, int> root;
      REP(i, n) {
        if (b >> i & 1) {
          int rt = uf.root(n + i);
          if (root.count(rt) == 0) {
            int tmp = root.size();
            root[rt] = tmp;
          }
          nx[i] = root[rt];
        }
      }
      bool is_con = true;
      REP(i, n) is_con &= prev[i] == -1 || root.count(uf.root(i)) == 1;
      if (is_con) {
        if (mp.count(nx) == 0) {
          mp[nx] = size++;
          que.emplace(nx);
          reach.emplace_back();
          finish.emplace_back(root.size() == 1);
        }
        reach[id].emplace_back(mp[nx]);
      }
    }
  }
  vector<ModInt> dp(size, 0), a;
  dp[0] = 1;
  while (a.size() < size * 2) {
    vector<ModInt> nx(size, 0);
    nx[0] += dp[0];
    nx[1] += dp[1];
    REP(i, size) for (int j : reach[i]) nx[j] += dp[i];
    dp.swap(nx);
    a.emplace_back(0);
    REP(i, size) {
      if (finish[i]) a.back() += dp[i];
    }
  }
  // cout << kita_masa(berlekamp_massey(a), a, m - 1) << '\n';
  return 0;
}