#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 1000000007;
using Mint = ModInt<MO>;


struct Mat {
  Mint a[2][2];
  Mat() : a{} {}
  friend ostream &operator<<(ostream &os, const Mat &f) {
    return os << "[" << f.a[0][0] << "," << f.a[0][1] << ";" << f.a[1][0] << "," << f.a[1][1] << "]";
  }
  bool operator==(const Mat &f) const {
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) if (a[i][j] != f.a[i][j]) return false;
    return true;
  }
  Mat next() const {
    Mat f;
    for (int i = 0; i < 2; ++i) for (int k = 0; k < 2; ++k) for (int j = 0; j < 2; ++j) f.a[i][j] += a[i][k] * a[k][j];
    for (int i = 0; i < 2; ++i) f.a[i][1] += f.a[i][0];
    return f;
  }
};

void exper() {
  Mat f;
  f.a[0][0] = 1; f.a[0][1] = 1;
  f.a[1][0] = 1; f.a[1][1] = 2;
  cerr << f << endl;
  cerr << f.next() << endl;
  cerr << f.next().next() << endl;
  cerr << f.next().next().next() << endl;
  cerr << f.next().next().next().next() << endl;
  Mat g = f;
  for (Int n = 1; ; ++n) {
    f = f.next();
    g = g.next().next();
    if (!(n & (n - 1))) cerr << "n = " << n << " ..." << endl;
    if (f == g) {
      cerr << "found n = " << n << endl;
      break;
    }
  }
}
// found n = 1000000006

constexpr Int L = MO - 1;
constexpr Int M = 1'000'000;

void local() {
  Mat f;
  f.a[0][0] = 1; f.a[0][1] = 1;
  f.a[1][0] = 1; f.a[1][1] = 2;
  for (Int n = 0; n < 2 * L; n += M) {
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) printf("%u,", f.a[i][j].x);
    for (Int m = 0; m < M; ++m) {
      f = f.next();
    }
  }
  puts("");
}

constexpr unsigned PRE[] = {
1,1,1,2,147782957,184163402,114297516,777280394,823590429,142266572,427914749,743514368,35135184,260651115,760851742,6009034,251039972,2145473,129615831,701026562,137144218,114570999,805305287,349263816,158782026,688747903,582367837,738690414,251927204,275205292,268257331,824039928,95899160,74234973,963228105,845186490,864690809,629292159,245628498,576844708,96529595,878174413,453345523,748140933,250944961,917509281,730853348,753522600,606959946,183819483,924552173,529849730,368576420,746630334,229271874,938984556,351874881,630004091,565392647,919859049,623490390,677105165,759371633,798127998,45068547,150458936,578349963,966643317,274729435,18176125,966686991,973380673,911330235,413034895,679508228,609220420,666493012,220118485,202434859,163004030,41792705,113490160,938860569,229212790,687570817,547424335,349958321,727085263,927857513,916568323,181713426,453587067,744872152,85480827,659858542,764493465,985076095,285655261,334017690,822978810,728677844,430578681,151341037,778534199,384969559,845305341,75790478,874966173,329649566,451314836,131170285,131028665,798972112,948996493,879713116,754261452,46908958,880308121,813804756,619511348,609881164,427772476,617352242,357589430,562573813,947505462,432843980,281490645,317811868,880473732,422587902,509740079,793976117,732007939,78644663,733453862,668667243,791474562,793292925,723156448,981109141,401071964,337794201,271143756,971262196,724072411,848958500,606283147,905050526,768686133,573213520,569801739,804252429,342949451,811339287,305775458,153807786,850336483,324130332,337450537,287709460,770607930,595629697,596562841,122175269,91706650,77373473,570342558,460962884,624417692,896768673,360081562,36716780,18734388,585746804,18153793,242924640,435269223,183341720,49797108,139035987,79412289,287286543,770827272,307966364,77632219,560258939,881821926,445159048,114154342,695098066,13569844,314927752,61374361,210227790,374519004,325597064,562994458,857074880,8695254,587832258,340715873,285170713,423193219,690769426,14569762,841061234,165571792,716789037,342892600,178272235,50170173,152120846,823775430,680576425,105203414,559800400,116978568,396443216,470388078,600234660,174888581,221269078,26315138,175773063,457283141,698519603,368472980,961714490,304646467,285232785,878139392,742811638,80635582,338897045,554116480,535478333,937559462,122255041,26242038,443398109,515822430,160535291,996508581,564452711,382194576,650587987,144239622,928388716,170568114,398872109,912150328,172597421,950804404,749597310,121622314,591332137,531543884,734424926,260734691,46164090,737687993,740325940,549641728,950880091,902375866,150336014,955760866,353209636,360072540,978466015,877775090,876122534,340622424,521552241,537415904,404326710,404060579,807882531,461001976,980575210,158557151,147295533,365695927,553694307,54696746,845760035,464111601,720037320,887535529,676589742,479625828,836234232,773129549,183655524,178041778,652399283,407991216,847135698,712718687,171675410,297129276,86260628,312649209,788929515,877476847,946199813,19751019,686586418,309975374,78115340,902597591,274863889,681950224,49451763,811314993,752263551,746731318,55592900,877113578,162573832,231901187,636426892,802601667,525420706,846098743,321001388,92414303,973723307,214013176,702841345,563133715,615702757,902180886,522408334,556591847,536559784,774677620,862376551,175858918,981205899,428356918,562088898,538851898,219571592,498386667,570390907,448587173,334540350,191318617,10137292,742504034,757368880,560190589,584264394,653726405,501881725,523182275,172764149,828013811,109128481,19490650,978202062,51063241,771366703,221926302,861888956,80232387,156551032,148802682,15734342,626152461,61220261,959876199,147200263,571593156,861683835,177099088,423692740,566586749,857563386,227708119,991081739,394575763,434560321,698242007,830438034,970943998,282390805,207004,187009364,650420813,948011151,457844039,939595235,273044048,464535696,907027555,825302853,164903668,227252150,438902912,383071956,942173741,680585907,779836604,977596132,299021569,794099507,271054199,911614732,718821318,965759720,80988072,82203754,650694565,310097470,868834203,35959989,175878586,626802548,245909185,151594464,386975079,29152023,798910662,674373165,693140303,179051677,906298348,162376139,92808087,832757261,664013428,130484736,352595533,839269125,295636040,880131307,510860241,268991474,770931661,243202873,354928135,273019968,355757289,764630701,254532613,864032872,169912902,277982651,836077124,158731390,924452856,300444667,592524328,916024947,917509102,161391932,196626112,158548855,385486164,497871424,15633781,619912050,538442127,980683794,908280604,799473571,88256652,470381857,153612682,7541071,930719714,959890134,986561960,684351042,468725347,572203399,260909006,521153550,123324963,869263662,100235732,781358051,54769361,394329338,739690439,285553948,510678762,110306362,465658678,746291484,523939282,12019920,907962254,256553204,906703077,665328257,212376533,122237358,563678833,678281911,82022596,217152755,895106736,819570306,869862055,849112592,152532631,437029870,387622904,990315685,333036006,542603264,838746423,944547311,943343293,595689527,985329195,150340342,555575343,586171847,313095809,181409698,907004831,235499235,985956140,295883239,831627291,510768937,18701676,780502327,506600348,985081999,715472984,642349298,775375876,582935827,496491318,659531104,65078853,585810918,621750704,897600255,925385199,97063911,798259322,634168728,939858000,321438242,801347697,974923033,704668171,514721975,542423577,840857737,188136468,715381466,634173035,19044256,67796760,666456689,492373393,264432591,647700741,368554627,676223804,132718806,214711935,584115,462722313,577732291,236080524,143254005,292589035,371332933,551784788,835597012,92648155,481065251,879753884,187966057,743245762,956121391,992028165,887894701,282587703,898703542,531036457,325224860,309272017,435647536,688986730,41242392,450162810,13987893,126632319,702812277,256766967,110528094,40648725,481622440,86446972,512177532,589234900,483878344,428596466,262569608,974265980,916569206,515909181,235541716,467175950,302477293,43065827,496541315,758607759,476209966,223396936,709839079,217419816,977352969,821764078,146662156,706864689,990392295,75546065,747058592,396235518,974573974,568575768,153320856,366702735,59601460,827003106,775496397,663977508,143758953,286251632,790698861,964068511,781507281,656917987,428085091,541841305,58451716,696661725,358143145,544341917,404084961,985995765,974021632,35832515,154879694,74183589,273374284,61846635,662653496,519301569,139039993,401425154,592317325,672230812,789991570,294152778,860580288,458577562,364551472,890601587,219803873,118404616,277615883,738614375,789452834,250672185,82836339,850779898,277951002,369971308,798506551,432369373,865238787,424111180,800817579,815440101,225109809,95470942,878534620,281424903,603306389,663460116,591093169,507263469,714542437,41324712,22265832,131865143,272593766,246840393,913356306,945212970,727660301,424632736,442560549,652970649,101384158,227039423,257871888,698429536,3072161,754137645,604714057,600666272,573365588,127666120,378898310,515594856,802377377,658896837,408001084,431089528,590575638,94451417,993513234,812109915,722927591,771491567,328752204,746596774,614491978,156381402,284641788,6091887,11542152,97398442,880168756,447512800,959170658,675927607,769125626,120789607,501078079,236307590,493298664,21305397,43911347,22037434,1087690,890696329,749895430,179370005,72318799,682842319,746064955,376562277,502690543,213162590,14050979,529152077,106946478,553626390,634731910,797484954,884523584,756323714,369545264,183986826,146841264,680762952,786627666,748241353,178951533,453754465,638565150,904815172,605820896,40469329,850281241,55420210,793593934,460118890,934922288,612347300,112126174,15544867,239361589,467083666,882826368,530141419,38542644,736218705,900756938,745820088,460027893,537186170,244568253,132914650,870395783,719502716,972329566,308018643,501975370,771539418,652042002,73512223,826403890,205695618,524990601,434549969,522926401,310499071,844492057,685232855,791341285,366337375,315307943,856805062,646749052,646499353,60069152,558271013,166881348,327475768,406520279,118854468,828352092,992388661,827275256,476200013,106823977,18311285,508970947,763961900,551666334,729411102,333043253,432911058,614785469,69397581,172960807,85656026,709663208,519419104,62536225,461760513,23176113,894481225,244337651,428570621,791878263,617068577,68542446,663548352,931068926,849387612,939032676,808386090,619912105,100316444,16293505,429533697,783386280,820683442,302095091,557295512,647802136,346420400,403866512,906238068,828674694,571784350,441342996,6070271,794550676,391409343,870086166,920716502,237609952,231440058,294977918,989059622,64546024,540123067,94614573,350508276,856947155,880864488,305052362,131595120,865992234,773292671,551818511,696955821,979508394,864314308,410547655,857762844,128250468,169701388,455177169,446816670,708643408,847707215,737232364,405612331,53669729,459996580,962234386,311971332,203480483,483384379,696838381,389365840,878490101,201258281,122685085,23667795,592447039,696439527,714326728,290453625,227616067,985480930,872563629,519124020,923050914,437041216,775846556,501630223,455085758,347873042,682347709,631835753,167422304,408704234,838349417,144318572,489710308,597914241,52210291,353471818,98935096,548397158,246967905,735417883,406353079,626025702,869961402,115228561,758206868,86303074,56572985,43650334,291022102,138752267,91376863,745656634,259723501,655582952,899547025,543859493,543338227,10077027,604340265,74453807,132475584,257329537,769392507,258493423,337339204,903279102,402504725,128671302,434648743,646815960,329543609,824234438,455266619,43214843,942826403,287863289,151907701,579212395,75267116,427460295,654696959,516575918,909571089,710437023,134267081,818690387,367106612,318571439,464185366,793466188,210430837,555926671,585853851,674141432,176574275,5366838,832000790,52573686,697516315,477862684,54142347,753530559,773126492,505291254,980122347,468313022,316024723,610994901,663716958,178298951,819162321,613456111,884036385,921382019,98628804,720560477,273957245,358572370,440889738,709586172,724882526,522782782,924859614,758633808,118990437,138786250,126677837,911583198,957390991,33020703,197609268,107907062,419800709,487311296,203459228,816636603,191805583,626178654,996351538,138310697,41595211,32952292,396615927,322072542,366829317,144680277,92941976,871891515,81948353,863023417,324125086,994445053,664287175,960809570,908211307,709863503,825521047,657390815,248489381,214452615,779743044,280350882,423865707,235120172,568073970,920209434,833120075,86488282,333502591,928971808,131798039,717012009,97161929,947004062,609903713,549774956,522889238,404532293,255795510,282634366,956029875,523236720,811735637,468806604,139982387,949191561,787774207,377774383,30344815,255130077,69708440,632443595,958611312,677703266,528269735,801872274,289086052,560865139,908158425,669672025,203166788,206806975,535247051,843588291,666404748,105492994,371717950,594128994,816555528,383256426,393898211,565313814,493604974,669492676,694992306,629087827,385217133,565183860,145606749,971191164,304549880,131107017,869764977,135151557,343011399,53671871,445805359,559817300,925405565,432982506,868299584,886248257,607072669,264511787,727374583,971961222,100883605,51995392,771765897,265987962,306283523,42869804,191158177,956228778,948243060,454380938,201115253,486099930,751157236,405939508,378397337,89236731,196006909,878882274,990543381,227766344,382905370,896150852,608977914,390436126,565120975,747947468,339096754,830031350,596510236,628340074,579764691,769098102,870828579,311523859,653097926,170192692,543108535,368489098,377008875,756997631,763990562,353358932,930491629,863208737,194118990,762396072,764649228,309827587,305216123,966321035,501342302,167549175,912797431,948044302,668743115,241373256,245816087,413066132,10951390,943288264,643810556,102759784,771628910,862972797,22165537,384091658,81728034,208930107,551496393,153361057,305458832,563991047,714896257,375060134,824957813,12979506,395762788,930537392,627288015,898859310,60648353,223452132,27905656,227937816,689024872,73039258,345659715,820827073,57786658,285262845,943347644,530575919,889800236,602738576,954241974,307548617,686811398,137480318,492444305,671494906,139125407,499667580,684169574,632383604,565933982,420065280,422255239,587744140,914940986,970965123,681435119,698271922,646538242,657408078,643494059,70811867,676162095,663451875,216853136,153551698,904448476,66992729,375004090,856328502,730377086,665787070,971970139,718679771,7225038,9162811,375415049,594018344,234020891,426505439,763359175,638269550,493317981,94098104,147865527,172480567,927247909,878078133,239076230,998739182,626149345,203268002,813490914,207255780,489652292,223466940,445687558,472690853,522869491,379349134,234780882,712923958,775573753,223353370,504677194,602454246,419759962,619483247,31456877,926140646,595712963,205752865,830637087,767463136,79887973,898661491,805837006,862179002,950224848,718345611,877012509,550791822,437627158,288784322,551140496,81984396,557283340,21099322,258522670,488575543,435327515,150196336,227699543,176932824,981851192,671728577,98309840,871595955,311219671,127076461,646889365,74806098,643393945,416028271,871524105,879689527,474858394,222839565,763605506,615716361,261129924,874557852,734025887,849041970,847641031,29081729,613969635,284693712,311791404,740062581,397005273,206996500,652786108,112729951,489029923,557339659,51060681,958566187,276501064,527491101,165182708,475392651,34552270,4114041,47377993,574507352,583016993,924306517,192759217,743961333,861900870,576626388,995339551,4462786,10115884,950923594,894431860,444494814,252939466,540984902,101962662,159948561,753767571,407772455,196825566,874503840,790096378,948487368,578364216,127565365,732539307,459383614,610140731,971106240,966081410,927604276,453616284,708337801,693063666,618714562,185922339,411174818,28164088,984020838,567219038,573755426,911430624,597108238,740460881,815212675,336807300,448927251,274693877,388809753,283112328,112266850,225837014,917744369,802722286,932005321,540490062,68311114,925174910,484824263,664731263,819742753,466406976,789915895,47608286,782708900,584091457,629413816,744906816,401047451,934222028,211319693,131997513,413585806,694357585,545516637,158593736,148184948,722864339,112509636,508961428,878117515,246844695,343597916,862556820,577644647,4905783,696956124,509636105,435989101,773519,643679294,177935285,749084158,254638413,826030932,27346502,943923182,697524900,899571370,486417596,666335697,716149906,797525827,759428437,335290695,181711852,522887437,91327522,655140389,806162020,529637428,382081205,48652903,673877744,755448572,695970320,282413148,990086404,182774154,316815676,953914063,60933911,852440723,285849984,632429594,390195744,941988026,672619365,811897622,515576963,129294704,304881407,645144681,816937348,438152769,158430406,214378923,101734293,69325755,531126952,135217225,542633842,55712784,86065435,830970139,554091057,891929134,905433654,923409240,255832760,41542859,269712562,368109911,619520442,136499238,724115800,212419409,714210288,63278044,369253118,172080569,707976724,946684576,590091297,467033259,708727937,453319586,61297561,29257650,765038268,856640790,493853353,832956841,246344463,904566778,909926655,527649309,558901890,56382364,854971349,160755862,710069298,448361423,726894210,942718844,361489488,936741423,193406837,621249512,963882251,446323035,182261688,968569533,682781747,679364587,271903728,858484976,479169303,104641089,909196358,229530864,805772163,704720648,928798165,24446582,62514131,556957806,701205086,713795603,755130390,520005038,626905084,828642925,658361894,142943906,401545400,346823448,17244122,463515825,917720675,359619055,89454975,52846886,699441200,440253003,426848606,526571095,577275730,661793231,900752674,570655139,28232538,49934100,761315383,505717677,625308895,526382216,395893771,891189253,704599547,11750199,377988334,895318529,425386440,923359636,130797941,53886374,948040420,77780065,973226635,540433041,242147218,818886492,245821741,981829403,69200091,64355173,812144775,468118,807853695,183423299,995897841,993925215,30341662,35583710,929228824,34743155,721545047,807990410,6989386,891280848,531385276,173298928,875750042,740489143,895840633,357257182,768412922,192289638,324916013,512271156,469808532,589804683,504912822,1018389,221376283,23666418,988893389,390456645,990687765,797073612,584111048,797956225,36406303,183089123,768412637,559201355,954983035,855895786,156778432,798125225,755924237,574270811,128723474,640002827,678177190,165382497,991504702,899598616,315835739,724850732,755282483,710587735,157261004,51498520,959092459,528908002,866768105,638758990,49186181,152658303,87432835,156780638,801395760,995895767,184622188,730378707,792314549,401347168,168364836,637762535,27160102,464723637,252823126,216442873,952904959,898165515,309159171,867374299,715624052,89782940,306333024,193030800,93460403,603786063,225600356,341311730,821612657,432910217,404901024,211463328,525898408,787845234,688297947,280191253,41156579,154285124,822308182,876859801,981502314,483747510,26166614,355844317,971154495,388751851,318343741,467207385,425805530,470552078,470031544,92150054,705360982,197568344,236062984,361960527,217557424,653635156,801254404,193135211,350154751,267285773,591520945,105652868,263587402,122949373,613779729,95274915,292576242,245269181,360150239,605917509,526514021,505001084,611016010,320605300,521304508,551053509,222935817,286852604,149377408,246139527,754397941,240395215,518623046,42770924,338176968,265111995,445153012,727794428,750697196,924252905,844210511,360191975,484875222,601774777,773433671,109648981,875845292,174336007,496400112,883009461,817395804,743663604,140862652,612513180,447353891,146834964,806471910,309084599,844336460,481087326,739740760,253893833,199555313,325935121,695264942,541868846,140973425,148997218,626694350,984806867,883347555,181750047,299004530,324208721,846097506,276134667,45816521,280309120,326570283,707715465,719344424,674802730,90062660,839496022,647468868,478810914,620490235,634099241,802517733,836753754,347896884,543355949,126616541,846580800,335345054,499919522,567581830,49286471,917286446,526936141,244790279,713852029,729999415,252561750,749017521,242937404,37536740,74182090,233133622,880716238,155614298,730376019,614599780,918296206,205006772,68242202,363889335,826983557,449751686,123980554,687007875,775548941,939794739,660373297,393319507,312106016,146792109,487835240,736799024,682995139,88658012,297134889,781563145,169820307,147507466,83519146,939044844,839668107,729166432,839880711,521797585,484249969,980172015,445431771,804778575,956595641,496027688,236990467,335237323,179640899,280780277,399785902,102411097,925108238,213884510,380468551,729839811,936115845,307469760,153022541,993496473,672590479,959215434,505665883,283810444,641369481,816038095,33662384,261872597,972518096,423298267,500932448,301001039,359149834,263716083,441813439,841706637,406180381,824922092,251333203,943662027,557879722,762462977,880068670,733521570,196217429,737226053,118306325,966822735,711988896,222831910,951950548,569524961,29792986,888595391,688154841,888782906,270181822,94263055,364150482,135679676,629310237,139903827,641403709,593507798,542298109,398395310,754953774,937731767,668399501,70140231,742983253,126163316,973329668,628579691,275703368,504422352,534364340,56327286,600472356,47247893,511514910,355710649,101218835,913792878,226797420,100884094,880490892,770320618,274220518,997411840,677929342,208162697,108205067,852403558,922041215,561906971,145236228,729205627,533172798,623700841,486783063,134851164,596813709,85997670,242264926,347132201,961694093,8798638,411320378,271925651,188646324,700602860,810226957,507282173,184476275,515489814,408166075,767369162,168697828,944923242,405061071,41854496,687299856,45084386,314827943,114349848,870137154,543854065,377100740,940410145,609630534,377658622,854332765,178315721,865997440,882468677,155434921,285011938,537671089,557992146,600501860,258929802,594369941,196454841,305541600,240710761,432480104,832671633,49230782,617278362,641668225,406132650,779203317,192623252,374341408,833339604,492773864,344008549,109160837,155934107,513257898,935342584,114868668,585601918,524246449,328538186,136455619,499398753,574091819,801462520,590710342,50234521,944304878,315162390,183747488,401596622,979814378,715768413,311446564,555830275,892830558,805284049,689311366,43359955,472027845,232475902,70557186,218097946,743277389,108219185,510782107,504748935,112748491,849881942,510480096,551795853,104003466,505475849,691102499,663655707,393424794,392073028,550435523,953979403,829889569,714793047,945314751,598360005,736745605,621849134,646824547,478151842,715487092,344995769,764654830,959976068,415779638,824361198,67159990,255833449,865006727,387588068,318740834,616182077,236987748,241392884,493959523,115058162,306001489,217698461,101649508,101056385,225250449,463927055,932526829,249378333,946857429,991809942,342696781,848328868,732838724,878150764,288754439,819620391,272242173,740203986,622985553,373642423,758402033,815433503,917903353,920170454,284448007,325975762,400191483,725443184,595712340,726457289,489203403,445570386,13366583,154646423,807565287,400999798,779094991,851881349,177939335,446263410,790640609,6526256,596966714,621509439,469431163,279579238,122539245,602392224,345145613,208285213,812505477,714740750,221305942,168700833,290357756,909915399,491766636,320096084,783635402,349777577,76817539,213163004,148148083,711128458,915292212,218760047,807551124,104587916,229077181,613977368,912332165,813578657,388753463,635825839,603875746,202263189,259039121,873931523,878850,523986195,56574582,979298895,465747446,134375178,142210887,67458230,851634654,500807142,601663539,988120199,970114938,266934125,977357948,907059962,328879167,290702,708229425,1104478,141301396,393788815,753293325,204531622,774859176,938224809,887888219,842863364,366523166,722585849,109261300,502302912,396885406,367669038,531577745,888309813,293908121,73047017,129057836,990659400,105842962,789815621,597983928,592520140,694884164,393483040,769058435,694897543,94413966,944259461,643269752,191868473,350809273,860819437,398275736,845033381,240217952,932110661,937745496,401623958,952749465,213761086,106448934,383657329,79563547,544738011,974582854,478781078,286298895,384800407,892389489,958509490,684684295,772410906,566035276,999748930,210344015,820778601,734602729,976553711,352250377,177101020,790740785,2755712,713175572,416995589,313776850,300831285,936412718,235615660,137989775,361978780,2334066,457289933,804681893,139797799,881161609,440761179,27836554,844312596,625273236,106672656,755867939,299143845,643783528,483955893,530952663,797452253,796229175,825447202,254252611,662800626,71623468,62730471,298040950,876231641,711836478,578444546,618387788,516116753,559446796,241670573,402679886,521154134,293622197,260860548,470572910,91198076,675887285,392210802,251778507,242907418,440688851,898517831,473442876,89937828,39819286,909199074,295424289,899918750,18486900,488708055,407630196,341925233,383445089,895923199,598585878,244798087,423684448,167208003,480459779,733833118,391037027,213652727,367577930,505483460,360487223,300643625,822886944,205798951,943848188,345972043,371171878,995599090,136113602,292431437,40382732,158908630,205435389,647563083,23569135,615363855,13753911,778197019,389607201,750146347,198047668,477514963,385181916,248811010,133150969,522168047,431114683,607663045,359115508,775875268,86880089,844207679,296306346,480385338,99150787,425966706,170146939,362016234,510185334,590944619,78406834,638576718,493379283,805984497,800643984,381822488,928170817,853814431,856502913,586951291,1787625,102440027,605528753,539250252,328613986,318231189,967749298,403017733,828574456,973140992,988033394,885109807,141593855,179179132,600270870,851963162,964969554,121568050,641645502,243915983,84914674,331903751,688649109,907395566,266830884,949957243,966861133,983074591,324710959,824550591,832746549,592729168,710922641,515032786,265944811,641890440,509530761,549919813,80396382,660809189,310325107,758741523,370168448,646664560,688675078,250896986,625767185,134676582,830504570,434161658,170081574,235116118,761686147,873292656,584203809,829046936,982702538,332720652,740878878,524321303,346179256,268346238,190806783,2184230,481142649,448310400,136664012,831965776,938663533,215473284,823257653,141289084,491523843,293752784,710206003,428217857,641497729,913591891,126769875,755902538,883460067,416937454,322608896,642988046,747858314,313230268,989928498,202229781,857782808,245389413,541551130,204911060,819552104,503348330,497690667,153104252,733836674,869104598,826103837,834746286,241522346,659831427,172687972,821286158,485739665,577912328,382724853,305049456,548370421,911950675,975297166,709881684,695130835,589675087,674334355,489245072,75623546,243155341,499516197,106409617,357788285,664630954,782414948,674044889,551856212,867275036,304372660,737748430,251552903,411307756,223174039,304822798,907728266,695054032,236145381,520361553,409336085,470759475,843461319,787141715,365076269,863967675,363171248,530743097,537272918,591515676,941642533,56146812,18089906,968400060,608591561,257203717,92532829,273977748,826993219,835831747,221835755,375905466,734255765,205699096,910952408,391353853,347021802,803319194,567426313,409401475,771784418,60544690,798705958,207457685,594932507,902334850,911016090,459562169,567013504,801161536,772303784,62124315,534656159,358429007,308264372,384150951,940779514,298516454,712955240,972347197,158751669,482149881,522590374,703587416,266535332,913976203,622563251,110882603,609872143,291277797,741963269,908981273,991220495,998729321,385474415,697149640,531044292,181998189,713330061,450982522,280336464,182299267,353820128,24027908,236489930,946237746,304260271,72248990,507581755,726887832,945620781,654842967,3053750,263009583,414635751,175369659,485507278,243420436,448411347,328199932,108347466,48948684,172718900,363518683,796519091,574715857,491139340,42021226,979122877,774451532,778770187,334807693,106785601,812102482,562366165,927401555,627787211,478551236,722395950,614956434,71644950,171793286,753064744,525080135,696017717,231041309,936093316,266837734,584865685,570451469,671817113,546036355,792591369,529361714,630364,321377680,288883373,27754208,332130330,674365545,535610905,748915030,887081131,341935591,582979715,946403287,18206776,140543889,186729876,249034265,981837183,658107233,557026098,76285439,629681961,737854623,810162517,628403007,106446360,215727153,289461478,154677297,634967934,708790415,880742905,536490077,392386612,995200834,343367157,646985243,894767510,612198247,671428796,228269097,46091630,823224131,261138937,512903382,384249367,811899229,253939062,479259955,651655908,824937394,111671530,754417297,781452061,641602107,672404350,951302188,360683249,889383754,831952840,706079171,182411193,615029452,583349171,627438773,127251750,961893209,379038157,55313511,233914404,892223039,965234958,41582426,841582041,835526635,662572959,65263709,127221394,119731633,95509729,170301770,385820647,373584182,866183483,316387542,903108185,526221008,43153830,733523876,802497920,893418671,744242133,739690286,277116219,232445070,15547208,985781866,419601970,844674648,714725321,637531422,747854758,669628068,745461331,582621579,373265785,759118851,272102587,710493360,437929299,469520920,594870529,369140017,800130687,43118208,374662937,392885836,44865065,678865379,939420307,305381259,989842161,933707402,103030899,199328822,632696810,497811982,202188238,193721993,884076487,255734234,669815238,867038437,50561428,794853199,576637653,661238149,82910432,269909471,973346162,567224622,221674605,70785179,875320602,117553276,537150282,429314464,880819675,898883160,923670168,360887691,880991425,230660740,199696185,917436730,283789142,81837435,967125012,9541545,423503122,21757200,524231568,337287915,579104450,616460699,11830304,63670328,449547758,879013340,304752861,258981637,611473149,705149020,599284222,567610083,251766217,724031842,2408355,683274893,473099317,182284568,106157143,589274770,277592754,543792994,180223147,973154206,21465593,170316654,636997092,180562750,879851537,675283148,722961693,379105971,886207163,303369005,730483866,209099963,713368271,672634428,688615983,666467402,186193520,803727971,747162997,159228969,125653443,604425724,398503963,21588361,102521791,363188560,524475872,284829615,586993965,417434253,8161362,83571807,601891619,551636721,540682387,135863243,105527208,634688068,468166285,106184837,697443192,103918809,166352852,72718994,933655598,312478158,726119902,561622045,602653962,570512880,608762846,613993780,140445778,407191318,874389851,669017161,17009774,872640306,663116421,56429643,616481780,1376008,850822416,369976775,777765033,789737912,258266640,893662125,143970585,108701979,182179731,802210454,968318276,426407459,207645510,802455323,644433205,400646759,469601680,460180633,389228004,655109074,787682360,876338455,564337438,979832064,626369874,529578942,312852628,204130021,59746738,24178477,224804259,443474192,928186609,216067806,197146161,739220199,223174644,125155535,936613135,89006750,6222558,135033066,611349657,431153178,352885085,256030783,951690292,921951159,604635942,184071548,346992884,249560430,484402806,101938371,680000101,805935144,154771039,689955854,203583890,365589805,861790481,644686135,921892007,390652061,210025964,923779110,443493148,864888727,730435813,638079671,385389086,449807172,544439754,632847236,762265128,579559522,562060784,649278735,840219429,876239734,785928283,234053196,13919708,109351095,642372879,280267349,665476244,554090366,339019208,511009449,636204621,53163589,857808490,113145061,441973647,692218014,662064052,807426732,450797263,19894482,222875180,979904497,777690970,72323975,897021337,120521363,832412943,126551906,892904045,207468757,661025501,312941081,863897414,451023059,681040924,63234654,296505210,575734955,64231432,518477137,789060440,601532661,545746096,255768350,103774907,368721774,739424967,82820869,845674864,219683800,84077207,570442966,991356411,940488338,503302778,538039297,42924860,251985215,706805183,20935209,1545111,262449467,24427126,356406532,572278416,58756077,917261659,746952075,971465813,13568390,166574376,943087219,16626801,467807297,323353295,13096249,646864808,665812588,961456476,934265358,467086981,368312564,68642575,276204741,769507495,689689910,844421635,29308256,913642142,708851811,40518946,427968390,356062147,465387354,88835891,52849644,469747366,70647419,744862073,937875562,693373735,170999101,325640553,518371451,612719850,612433950,840139811,562096079,124962832,702881496,581263676,648527412,318227099,479917181,81739488,139950553,883615645,50577350,704295351,411756935,853552931,313858038,793857941,230828304,194827001,51040214,960216442,205980332,100693527,497247853,554529150,815386534,324039347,574864923,885848404,890486932,637526643,945315700,454759028,430045386,107313286,557268621,922402726,266474968,374924946,135262428,119801893,693962566,642473933,66998642,213878428,714722366,442327745,414817165,989352551,219011871,295891894,303472389,187803375,323454322,619545224,159321991,588717957,44656147,500280021,64092423,423581190,162458718,397566071,860476514,493688297,118773069,696097337,834118861,182250752,462569378,983917580,69074316,431075512,572407258,296069457,896252566,572295304,878333558,289253237,686561002,900382524,354424106,28057871,366051615,912932521,657269645,859817485,666755517,353951721,912820641,460119063,142749819,53326600,523959445,525874972,221081138,461456385,934760008,315358412,836964463,943377864,406304781,433494881,46948501,348338213,841363052,684457576,997719971,349893053,937143719,174418894,1,845603976,0,1,1,461401156,0,1,1,207121523,0,1,1,123402032,0,1,1,718073277,0,1,1,592557461,0,1,1,969362789,0,1,1,484697441,0,1,1,962243096,0,1,1,194243543,0,1,1,209629281,0,1,1,723069758,0,1,1,766331159,0,1,1,461418075,0,1,1,883689912,0,1,1,215120801,0,1,1,881874272,0,1,1,454105305,0,1,1,377928138,0,1,1,322795151,0,1,1,630204915,0,1,1,11689423,0,1,1,266251473,0,1,1,222682907,0,1,1,834048635,0,1,1,339325974,0,1,1,277891399,0,1,1,377179437,0,1,1,99411624,0,1,1,864974490,0,1,1,923979287,0,1,1,804656047,0,1,1,984826747,0,1,1,987864203,0,1,1,895228597,0,1,1,476688684,0,1,1,240109191,0,1,1,477456021,0,1,1,707273582,0,1,1,60954130,0,1,1,354508240,0,1,1,313837796,0,1,1,482548455,0,1,1,871576636,0,1,1,902775427,0,1,1,926394900,0,1,1,453948817,0,1,1,116456813,0,1,1,155534282,0,1,1,865509017,0,1,1,249770921,0,1,1,374261700,0,1,1,192111678,0,1,1,274026792,0,1,1,197032039,0,1,1,46394647,0,1,1,516167380,0,1,1,169630177,0,1,1,26564919,0,1,1,450263168,0,1,1,592809503,0,1,1,439582580,0,1,1,215531520,0,1,1,120628934,0,1,1,58907053,0,1,1,164864740,0,1,1,909890689,0,1,1,745492656,0,1,1,844105873,0,1,1,250151898,0,1,1,992146528,0,1,1,373490083,0,1,1,744941816,0,1,1,277232603,0,1,1,609962388,0,1,1,819551252,0,1,1,612746842,0,1,1,616320790,0,1,1,707119526,0,1,1,421766296,0,1,1,169755796,0,1,1,774767765,0,1,1,692749130,0,1,1,980924468,0,1,1,303332135,0,1,1,307237360,0,1,1,425670391,0,1,1,690664019,0,1,1,201671535,0,1,1,731323579,0,1,1,835208633,0,1,1,655773320,0,1,1,526167768,0,1,1,939495492,0,1,1,550193415,0,1,1,439653399,0,1,1,658991326,0,1,1,276987553,0,1,1,553807617,0,1,1,913428894,0,1,1,728035362,0,1,1,546499913,0,1,1,130729677,0,1,1,474438197,0,1,1,145579171,0,1,1,94874551,0,1,1,892686004,0,1,1,186953009,0,1,1,99054849,0,1,1,734961764,0,1,1,322645659,0,1,1,722966846,0,1,1,118124667,0,1,1,991061563,0,1,1,967732239,0,1,1,658077727,0,1,1,88430350,0,1,1,631638751,0,1,1,775038670,0,1,1,761296807,0,1,1,9890295,0,1,1,519687018,0,1,1,126293978,0,1,1,655671988,0,1,1,244411899,0,1,1,817972574,0,1,1,887726232,0,1,1,172062746,0,1,1,48982198,0,1,1,826717608,0,1,1,670723081,0,1,1,108568906,0,1,1,266031699,0,1,1,89569833,0,1,1,60279459,0,1,1,294630683,0,1,1,127184141,0,1,1,398573023,0,1,1,567046454,0,1,1,398892489,0,1,1,512941332,0,1,1,210585144,0,1,1,729138999,0,1,1,657552689,0,1,1,76720950,0,1,1,165249558,0,1,1,324317808,0,1,1,64130455,0,1,1,317335425,0,1,1,398571936,0,1,1,76330106,0,1,1,387384817,0,1,1,610698193,0,1,1,940563132,0,1,1,852307595,0,1,1,862883253,0,1,1,277083000,0,1,1,613055952,0,1,1,466669702,0,1,1,98229427,0,1,1,849895929,0,1,1,924590860,0,1,1,180798632,0,1,1,667238372,0,1,1,935926453,0,1,1,280854232,0,1,1,741097854,0,1,1,540359296,0,1,1,877622402,0,1,1,181700551,0,1,1,564565670,0,1,1,823679856,0,1,1,190909706,0,1,1,302264042,0,1,1,531071202,0,1,1,154958500,0,1,1,879641210,0,1,1,967424695,0,1,1,883590633,0,1,1,474708685,0,1,1,201588931,0,1,1,317217848,0,1,1,858594345,0,1,1,516957946,0,1,1,428744859,0,1,1,974655228,0,1,1,235681720,0,1,1,584737726,0,1,1,366994186,0,1,1,749697556,0,1,1,191076670,0,1,1,864328217,0,1,1,588446487,0,1,1,182671080,0,1,1,697448076,0,1,1,916163132,0,1,1,652852777,0,1,1,90854881,0,1,1,385999011,0,1,1,917363700,0,1,1,625567001,0,1,1,163295232,0,1,1,520536017,0,1,1,597946069,0,1,1,479960811,0,1,1,702115075,0,1,1,962795486,0,1,1,76305708,0,1,1,831269480,0,1,1,30418355,0,1,1,975587859,0,1,1,744674500,0,1,1,774628776,0,1,1,432239455,0,1,1,8118746,0,1,1,998022350,0,1,1,665020126,0,1,1,832367606,0,1,1,824693054,0,1,1,333337380,0,1,1,823469357,0,1,1,72878597,0,1,1,611046536,0,1,1,195948237,0,1,1,994549509,0,1,1,971514355,0,1,1,983871879,0,1,1,848642029,0,1,1,688873793,0,1,1,799501654,0,1,1,849692053,0,1,1,490105609,0,1,1,895482979,0,1,1,945322692,0,1,1,626810756,0,1,1,897340439,0,1,1,165176758,0,1,1,262542385,0,1,1,548253259,0,1,1,181824321,0,1,1,720004463,0,1,1,523132065,0,1,1,60857634,0,1,1,736141743,0,1,1,14441005,0,1,1,760511652,0,1,1,563347965,0,1,1,935228745,0,1,1,557101397,0,1,1,741102675,0,1,1,678117804,0,1,1,16057066,0,1,1,62762350,0,1,1,103458164,0,1,1,951742601,0,1,1,246200744,0,1,1,627061251,0,1,1,757497505,0,1,1,251298449,0,1,1,698048621,0,1,1,248497209,0,1,1,485304324,0,1,1,991136692,0,1,1,442459237,0,1,1,595115338,0,1,1,641903069,0,1,1,195101603,0,1,1,397363061,0,1,1,609245440,0,1,1,886614911,0,1,1,997841263,0,1,1,603979934,0,1,1,523361362,0,1,1,499482899,0,1,1,429494683,0,1,1,150269157,0,1,1,53279317,0,1,1,517175601,0,1,1,507738398,0,1,1,898944401,0,1,1,693575530,0,1,1,737122395,0,1,1,478070015,0,1,1,120237023,0,1,1,491167116,0,1,1,684659399,0,1,1,963238328,0,1,1,571068784,0,1,1,117452040,0,1,1,357149235,0,1,1,212101286,0,1,1,864060878,0,1,1,679875338,0,1,1,423287914,0,1,1,394983750,0,1,1,456718757,0,1,1,512805909,0,1,1,110051997,0,1,1,25915945,0,1,1,266133454,0,1,1,794115966,0,1,1,661901502,0,1,1,31291839,0,1,1,452014273,0,1,1,914653617,0,1,1,141644985,0,1,1,923418477,0,1,1,868470955,0,1,1,251048003,0,1,1,354952362,0,1,1,662434285,0,1,1,443735454,0,1,1,264426386,0,1,1,19351578,0,1,1,941222122,0,1,1,217683768,0,1,1,918486490,0,1,1,497144290,0,1,1,958786456,0,1,1,417108975,0,1,1,860154526,0,1,1,669043669,0,1,1,656942729,0,1,1,823416879,0,1,1,535792740,0,1,1,160356922,0,1,1,92990109,0,1,1,768040387,0,1,1,927026347,0,1,1,55939271,0,1,1,577804480,0,1,1,963007907,0,1,1,945171058,0,1,1,259485830,0,1,1,572635447,0,1,1,812153540,0,1,1,164549245,0,1,1,316005562,0,1,1,663052037,0,1,1,144750436,0,1,1,515472702,0,1,1,623311128,0,1,1,132244300,0,1,1,580474954,0,1,1,666080155,0,1,1,229383253,0,1,1,942877008,0,1,1,27811266,0,1,1,413321033,0,1,1,179334223,0,1,1,963069627,0,1,1,740950989,0,1,1,88605894,0,1,1,854555027,0,1,1,903928054,0,1,1,747837481,0,1,1,336242617,0,1,1,705052369,0,1,1,587611116,0,1,1,864176627,0,1,1,562972087,0,1,1,796794372,0,1,1,718572690,0,1,1,651547147,0,1,1,129510857,0,1,1,514093135,0,1,1,357372467,0,1,1,120648691,0,1,1,784834215,0,1,1,811007407,0,1,1,706227128,0,1,1,359867071,0,1,1,977093975,0,1,1,347929337,0,1,1,417580752,0,1,1,296847153,0,1,1,796049130,0,1,1,505665553,0,1,1,145566981,0,1,1,932195403,0,1,1,612760960,0,1,1,940086526,0,1,1,397519995,0,1,1,699474344,0,1,1,115635131,0,1,1,327762954,0,1,1,267857791,0,1,1,510168805,0,1,1,760433678,0,1,1,393967788,0,1,1,658044557,0,1,1,743387899,0,1,1,428594152,0,1,1,491317469,0,1,1,963108853,0,1,1,500692783,0,1,1,54015221,0,1,1,907351161,0,1,1,859662776,0,1,1,737339493,0,1,1,638637608,0,1,1,523450051,0,1,1,144507628,0,1,1,423610520,0,1,1,372938722,0,1,1,721156668,0,1,1,156826441,0,1,1,575298414,0,1,1,54501223,0,1,1,817309662,0,1,1,687401108,0,1,1,887266240,0,1,1,706016044,0,1,1,742232413,0,1,1,621909594,0,1,1,697431734,0,1,1,858861841,0,1,1,327132099,0,1,1,810765292,0,1,1,498510692,0,1,1,896040040,0,1,1,708834760,0,1,1,549971038,0,1,1,492065032,0,1,1,708631107,0,1,1,529864580,0,1,1,237629051,0,1,1,269328320,0,1,1,671728564,0,1,1,901524093,0,1,1,808597006,0,1,1,96137284,0,1,1,254895679,0,1,1,38026684,0,1,1,276779324,0,1,1,981246707,0,1,1,20852056,0,1,1,377357592,0,1,1,17139651,0,1,1,68423694,0,1,1,44610882,0,1,1,720730065,0,1,1,510032754,0,1,1,53488508,0,1,1,200195687,0,1,1,381060749,0,1,1,657127135,0,1,1,989045432,0,1,1,389595635,0,1,1,821855010,0,1,1,632714204,0,1,1,460746958,0,1,1,163284189,0,1,1,951096652,0,1,1,64294528,0,1,1,372811784,0,1,1,952480178,0,1,1,861738260,0,1,1,766706267,0,1,1,617468285,0,1,1,292723761,0,1,1,257089192,0,1,1,846380982,0,1,1,550218107,0,1,1,98133599,0,1,1,239623738,0,1,1,605587008,0,1,1,502642618,0,1,1,283917435,0,1,1,276312957,0,1,1,122084359,0,1,1,145232526,0,1,1,940902835,0,1,1,344317157,0,1,1,198845230,0,1,1,189411684,0,1,1,129421430,0,1,1,408030075,0,1,1,525636887,0,1,1,577044966,0,1,1,229858200,0,1,1,462891450,0,1,1,974944902,0,1,1,808603891,0,1,1,360702173,0,1,1,69274998,0,1,1,288205174,0,1,1,272272965,0,1,1,90707807,0,1,1,810455628,0,1,1,434862004,0,1,1,320592274,0,1,1,888025555,0,1,1,665796332,0,1,1,887538673,0,1,1,918827360,0,1,1,283234787,0,1,1,285943882,0,1,1,548313230,0,1,1,889045945,0,1,1,230700497,0,1,1,682675148,0,1,1,525890193,0,1,1,140425254,0,1,1,839759164,0,1,1,824069687,0,1,1,871170353,0,1,1,310587181,0,1,1,245280387,0,1,1,24280442,0,1,1,276203661,0,1,1,965383725,0,1,1,95791394,0,1,1,557677262,0,1,1,235461239,0,1,1,276890101,0,1,1,235234284,0,1,1,306763164,0,1,1,422241019,0,1,1,40349393,0,1,1,578775617,0,1,1,1461177,0,1,1,283281435,0,1,1,527835366,0,1,1,604256082,0,1,1,917415752,0,1,1,34736424,0,1,1,797147434,0,1,1,137426453,0,1,1,483121813,0,1,1,115497410,0,1,1,100582005,0,1,1,623103346,0,1,1,623483028,0,1,1,861903579,0,1,1,684586089,0,1,1,30013648,0,1,1,809682007,0,1,1,963409203,0,1,1,382619268,0,1,1,169313530,0,1,1,664229728,0,1,1,60318556,0,1,1,733947083,0,1,1,612846931,0,1,1,740799366,0,1,1,306743603,0,1,1,764557106,0,1,1,394441787,0,1,1,358188628,0,1,1,281221366,0,1,1,671782716,0,1,1,899013965,0,1,1,159253349,0,1,1,24629004,0,1,1,5799330,0,1,1,689520926,0,1,1,271203773,0,1,1,3320614,0,1,1,181282896,0,1,1,74101187,0,1,1,679947826,0,1,1,151941440,0,1,1,890078622,0,1,1,757363386,0,1,1,645608096,0,1,1,363736337,0,1,1,218186582,0,1,1,355513235,0,1,1,406268989,0,1,1,249018316,0,1,1,546686263,0,1,1,218117727,0,1,1,534654078,0,1,1,701245302,0,1,1,727443910,0,1,1,451593357,0,1,1,952040104,0,1,1,963389946,0,1,1,177720787,0,1,1,646219478,0,1,1,846845975,0,1,1,461593643,0,1,1,747615562,0,1,1,37916516,0,1,1,163404670,0,1,1,53208798,0,1,1,586333005,0,1,1,25208941,0,1,1,591415450,0,1,1,354401080,0,1,1,206971665,0,1,1,190770971,0,1,1,742436940,0,1,1,68774176,0,1,1,54956674,0,1,1,957373921,0,1,1,284623445,0,1,1,319225953,0,1,1,989178617,0,1,1,466004422,0,1,1,318312490,0,1,1,766341214,0,1,1,809304779,0,1,1,518197399,0,1,1,11859318,0,1,1,736585754,0,1,1,273369127,0,1,1,262381857,0,1,1,716870224,0,1,1,540330710,0,1,1,965370861,0,1,1,514765586,0,1,1,623882698,0,1,1,120966529,0,1,1,82259715,0,1,1,886053799,0,1,1,78954843,0,1,1,971879839,0,1,1,95162100,0,1,1,1236286,0,1,1,439960879,0,1,1,390786749,0,1,1,706959002,0,1,1,530551490,0,1,1,977246577,0,1,1,235965779,0,1,1,396507845,0,1,1,881122780,0,1,1,228339701,0,1,1,333840386,0,1,1,388571115,0,1,1,533253965,0,1,1,261196230,0,1,1,507534935,0,1,1,536828838,0,1,1,765898022,0,1,1,49821627,0,1,1,945880812,0,1,1,299861562,0,1,1,689117670,0,1,1,151323143,0,1,1,91142374,0,1,1,332194087,0,1,1,884590124,0,1,1,895656200,0,1,1,165539726,0,1,1,8016306,0,1,1,289666929,0,1,1,174821492,0,1,1,384541265,0,1,1,298423103,0,1,1,326337275,0,1,1,742570395,0,1,1,606538452,0,1,1,857860411,0,1,1,159635375,0,1,1,201631994,0,1,1,933333718,0,1,1,512278681,0,1,1,356236992,0,1,1,740573861,0,1,1,147599829,0,1,1,708404800,0,1,1,866990811,0,1,1,160106779,0,1,1,967637237,0,1,1,192544912,0,1,1,484702802,0,1,1,22712568,0,1,1,945570714,0,1,1,227959982,0,1,1,398863715,0,1,1,412783007,0,1,1,441383902,0,1,1,644369816,0,1,1,484955153,0,1,1,120928086,0,1,1,360448830,0,1,1,809338590,0,1,1,525198619,0,1,1,164652231,0,1,1,357324294,0,1,1,439619745,0,1,1,553593110,0,1,1,746831907,0,1,1,154460215,0,1,1,948092221,0,1,1,420874275,0,1,1,718712198,0,1,1,898884589,0,1,1,358041028,0,1,1,73555810,0,1,1,147833885,0,1,1,712181013,0,1,1,739520395,0,1,1,331606598,0,1,1,261356861,0,1,1,548249879,0,1,1,739670466,0,1,1,328195876,0,1,1,145411904,0,1,1,315067003,0,1,1,824743263,0,1,1,559995104,0,1,1,587764387,0,1,1,995349441,0,1,1,634538217,0,1,1,228908685,0,1,1,503802297,0,1,1,621948485,0,1,1,718084316,0,1,1,221828597,0,1,1,54029931,0,1,1,376014845,0,1,1,999752799,0,1,1,958127521,0,1,1,979045956,0,1,1,978086637,0,1,1,666667176,0,1,1,852933674,0,1,1,759109829,0,1,1,201380817,0,1,1,774493534,0,1,1,874318693,0,1,1,621439297,0,1,1,122983984,0,1,1,856080258,0,1,1,336109225,0,1,1,974937712,0,1,1,856211511,0,1,1,311263202,0,1,1,611935375,0,1,1,743165340,0,1,1,703351348,0,1,1,112167554,0,1,1,895647100,0,1,1,282817799,0,1,1,568531660,0,1,1,272728041,0,1,1,90000557,0,1,1,315391509,0,1,1,382607206,0,1,1,92017717,0,1,1,751805130,0,1,1,720063960,0,1,1,820418500,0,1,1,366903594,0,1,1,819637679,0,1,1,592637837,0,1,1,709764729,0,1,1,377007135,0,1,1,882845299,0,1,1,637932274,0,1,1,368967826,0,1,1,155775093,0,1,1,578382659,0,1,1,344687189,0,1,1,281412307,0,1,1,837256082,0,1,1,281062152,0,1,1,685663044,0,1,1,748892090,0,1,1,805307409,0,1,1,449389419,0,1,1,830237888,0,1,1,524387703,0,1,1,799670387,0,1,1,201155680,0,1,1,110826863,0,1,1,124730157,0,1,1,950497497,0,1,1,440420172,0,1,1,562435365,0,1,1,553686838,0,1,1,768783649,0,1,1,756659919,0,1,1,314646951,0,1,1,938467305,0,1,1,362368051,0,1,1,461696943,0,1,1,592140302,0,1,1,59758751,0,1,1,15029627,0,1,1,686395893,0,1,1,85582424,0,1,1,245404791,0,1,1,196383598,0,1,1,139681505,0,1,1,544643657,0,1,1,901512666,0,1,1,983007615,0,1,1,459984419,0,1,1,427910991,0,1,1,924372974,0,1,1,807089849,0,1,1,814100743,0,1,1,763756504,0,1,1,253239494,0,1,1,908266687,0,1,1,974264501,0,1,1,957737693,0,1,1,3911479,0,1,1,306501785,0,1,1,364331703,0,1,1,267705624,0,1,1,865427314,0,1,1,608558872,0,1,1,531381003,0,1,1,419369047,0,1,1,832804290,0,1,1,930466937,0,1,1,408053300,0,1,1,377418949,0,1,1,492652767,0,1,1,152210471,0,1,1,489810813,0,1,1,437143038,0,1,1,244848307,0,1,1,52138621,0,1,1,982519321,0,1,1,833630463,0,1,1,332117842,0,1,1,102927109,0,1,1,691974096,0,1,1,395044617,0,1,1,761623768,0,1,1,596005051,0,1,1,615878296,0,1,1,6992408,0,1,1,197225560,0,1,1,620375991,0,1,1,493146384,0,1,1,907435734,0,1,1,71579430,0,1,1,726519196,0,1,1,770568660,0,1,1,414500697,0,1,1,832881509,0,1,1,643093808,0,1,1,939434093,0,1,1,202913891,0,1,1,641530541,0,1,1,447559371,0,1,1,583260022,0,1,1,778672911,0,1,1,242859626,0,1,1,378476410,0,1,1,301665130,0,1,1,22416777,0,1,1,620383706,0,1,1,842618878,0,1,1,886075742,0,1,1,606819381,0,1,1,987991012,0,1,1,343479686,0,1,1,292030328,0,1,1,338131547,0,1,1,698451393,0,1,1,608022081,0,1,1,70371510,0,1,1,724599300,0,1,1,464821588,0,1,1,581443396,0,1,1,266188858,0,1,1,64261641,0,1,1,544671561,0,1,1,515081089,0,1,1,98104276,0,1,1,101375925,0,1,1,213278391,0,1,1,44983383,0,1,1,122136746,0,1,1,293491168,0,1,1,177197594,0,1,1,287105895,0,1,1,474506143,0,1,1,313208195,0,1,1,768195877,0,1,1,616524428,0,1,1,201595120,0,1,1,992510821,0,1,1,549690002,0,1,1,212434293,0,1,1,514454394,0,1,1,415970371,0,1,1,33482223,0,1,1,813771105,0,1,1,970054215,0,1,1,674245977,0,1,1,832255574,0,1,1,592923490,0,1,1,178574269,0,1,1,811414688,0,1,1,870388611,0,1,1,62586597,0,1,1,756751907,0,1,1,363418896,0,1,1,232457847,0,1,1,842167441,0,1,1,204829701,0,1,1,565431259,0,1,1,643063457,0,1,1,177951315,0,1,1,421617342,0,1,1,715144587,0,1,1,269603306,0,1,1,946912307,0,1,1,6812652,0,1,1,977163713,0,1,1,710925142,0,1,1,235908280,0,1,1,713252009,0,1,1,842779056,0,1,1,452738701,0,1,1,962178972,0,1,1,357357731,0,1,1,540891515,0,1,1,726345665,0,1,1,687313840,0,1,1,237005005,0,1,1,213604345,0,1,1,943746385,0,1,1,186508129,0,1,1,588578891,0,1,1,691233076,0,1,1,529703634,0,1,1,158666040,0,1,1,708966074,0,1,1,862690516,0,1,1,976074631,0,1,1,637017164,0,1,1,31861959,0,1,1,629753339,0,1,1,659597419,0,1,1,622655841,0,1,1,127606507,0,1,1,172169699,0,1,1,502142459,0,1,1,883552967,0,1,1,380576362,0,1,1,340091259,0,1,1,438754096,0,1,1,631686067,0,1,1,25024460,0,1,1,797632598,0,1,1,82140891,0,1,1,248630679,0,1,1,548699457,0,1,1,477731878,0,1,1,704089279,0,1,1,932593375,0,1,1,770410528,0,1,1,743887085,0,1,1,133036816,0,1,1,171601473,0,1,1,494060024,0,1,1,732717286,0,1,1,595838286,0,1,1,827183540,0,1,1,286590471,0,1,1,157136149,0,1,1,980797628,0,1,1,568777266,0,1,1,12266699,0,1,1,404952969,0,1,1,200698376,0,1,1,437830329,0,1,1,535489682,0,1,1,784539124,0,1,1,15260544,0,1,1,893154071,0,1,1,617612857,0,1,1,793039649,0,1,1,899855659,0,1,1,648676464,0,1,1,891177684,0,1,1,551003762,0,1,1,65704610,0,1,1,947130626,0,1,1,153732275,0,1,1,432861433,0,1,1,996868118,0,1,1,601075489,0,1,1,795087776,0,1,1,883659380,0,1,1,911025652,0,1,1,784034125,0,1,1,11338475,0,1,1,726306957,0,1,1,679357754,0,1,1,415074036,0,1,1,611003197,0,1,1,708224545,0,1,1,360942335,0,1,1,239853420,0,1,1,535404351,0,1,1,410742987,0,1,1,943539159,0,1,1,361130744,0,1,1,278837563,0,1,1,710334397,0,1,1,315736275,0,1,1,892553162,0,1,1,729969899,0,1,1,103008710,0,1,1,358896295,0,1,1,788823402,0,1,1,530660051,0,1,1,378035057,0,1,1,784525462,0,1,1,870672970,0,1,1,386973926,0,1,1,944709663,0,1,1,29432654,0,1,1,784611267,0,1,1,654404289,0,1,1,663345399,0,1,1,552780130,0,1,1,255043675,0,1,1,322346953,0,1,1,250182648,0,1,1,535410182,0,1,1,940979426,0,1,1,450532012,0,1,1,239676969,0,1,1,129342053,0,1,1,474643431,0,1,1,767178311,0,1,1,810390231,0,1,1,389437178,0,1,1,762572755,0,1,1,452887920,0,1,1,702935382,0,1,1,607737950,0,1,1,335573262,0,1,1,128751706,0,1,1,101210250,0,1,1,620426153,0,1,1,672827412,0,1,1,396164193,0,1,1,208028716,0,1,1,632539823,0,1,1,591743388,0,1,1,576605869,0,1,1,967599926,0,1,1,538342953,0,1,1,470569640,0,1,1,549305226,0,1,1,669773582,0,1,1,910152676,0,1,1,708972843,0,1,1,862376750,0,1,1,769906673,0,1,1,628078629,0,1,1,375724918,0,1,1,961190121,0,1,1,783900476,0,1,1,875415082,0,1,1,147660362,0,1,1,509262651,0,1,1,459993480,0,1,1,143992680,0,1,1,986259833,0,1,1,469670425,0,1,1,205701012,0,1,1,295467043,0,1,1,902273328,0,1,1,544439157,0,1,1,800783628,0,1,1,656127293,0,1,1,68335782,0,1,1,27264715,0,1,1,941831765,0,1,1,962655668,0,1,1,965930494,0,1,1,806449174,0,1,1,244005013,0,1,1,495423745,0,1,1,522215101,0,1,1,955777440,0,1,1,105855746,0,1,1,557699208,0,1,1,468451947,0,1,1,629739568,0,1,1,895425589,0,1,1,881651105,0,1,1,823291630,0,1,1,753151122,0,1,1,448926933,0,1,1,169300135,0,1,1,275871459,0,1,1,523846374,0,1,1,717804621,0,1,1,133596772,0,1,1,381869586,0,1,1,369671741,0,1,1,785577935,0,1,1,289903245,0,1,1,373647328,0,1,1,933250558,0,1,1,414789063,0,1,1,970792657,0,1,1,601163100,0,1,1,64774674,0,1,1,876482420,0,1,1,467073221,0,1,1,34171140,0,1,1,282797733,0,1,1,214608778,0,1,1,942541344,0,1,1,870671362,0,1,1,439345700,0,1,1,452985339,0,1,1,265120817,0,1,1,510282467,0,1,1,110756724,0,1,1,509869358,0,1,1,121484979,0,1,1,636895266,0,1,1,875154541,0,1,1,54995109,0,1,1,798848348,0,1,1,463369877,0,1,1,441318938,0,1,1,372155823,0,1,1,529495725,0,1,1,799563485,0,1,1,735140351,0,1,1,778542467,0,1,1,416730050,0,1,1,548571392,0,1,1,816656750,0,1,1,907649534,0,1,1,63441866,0,1,1,942103610,0,1,1,970737258,0,1,1,506227706,0,1,1,743235105,0,1,1,412482697,0,1,1,961139714,0,1,1,18915392,0,1,1,886392802,0,1,1,41524260,0,1,1,735573769,0,1,1,236957025,0,1,1,895692471,0,1,1,376002040,0,1,1,286208367,0,1,1,646852690,0,1,1,298067659,0,1,1,37302887,0,1,1,540792162,0,1,1,592821302,0,1,1,700817310,0,1,1,607232554,0,1,1,19954421,0,1,1,400204001,0,1,1,991666720,0,1,1,314034836,0,1,1,169529624,0,1,1,842571737,0,1,1,768449983,0,1,1,213550600,0,1,1,608373854,0,1,1,520013350,0,1,1,870954659,0,1,1,149068114,0,1,1,435587852,0,1,1,127839071,0,1,1,493196341,0,1,1,903495003,0,1,1,549857967,0,1,1,51597875,0,1,1,930172993,0,1,1,205546227,0,1,1,310619395,0,1,1,890116016,0,1,1,920056109,0,1,1,976167329,0,1,1,565649830,0,1,1,20581528,0,1,1,919665542,0,1,1,304952469,0,1,1,944199144,0,1,1,593353991,0,1,1,19307526,0,1,1,868511532,0,1,1,552609287,0,1,1,964839030,0,1,1,862360578,0,1,1,669755132,0,1,1,384194478,0,1,1,768479240,0,1,1,839022631,0,1,1,592440052,0,1,1,916450830,0,1,1,782669612,0,1,1,68531234,0,1,1,467458810,0,1,1,666024488,0,1,
};

Mint solve(Int n) {
  if (n >= L) n = L + (n - L) % L;
  const Int q = n / M;
  const Int r = n % M;
  Mat f;
  for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) f.a[i][j] = PRE[q * 4 + i * 2 + j];
  for (Int m = 0; m < r; ++m) f = f.next();
  Mint ans = -1;
  for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) ans += f.a[i][j];
  return ans;
}

int main() {
  // exper();
  // local(); return 0;
  
  int T;
  for (; ~scanf("%d", &T); ) {
    vector<Mint> ans(T);
    for (int t = 0; t < T; ++t) {
      Int N;
      scanf("%lld", &N);
      --N;
      ans[t] = solve(N);
    }
    for (int t = 0; t < T; ++t) {
      if (t) printf(" ");
      printf("%u", ans[t].x);
    }
    puts("");
  }
  return 0;
}