#line 1 "test.cpp"
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif
// #pragma GCC target("avx,avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vul = vector<ull>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vs = vector<string>;
template<class T> using pq = priority_queue<T,vector<T>, greater<T>>;
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(a,b,c,name,...) name
#define rep1(n) for (ll UNUSED_NUMBER = 0; UNUSED_NUMBER < (n); ++UNUSED_NUMBER)
#define rep2(i, n) for (ll i = 0; i < (n); ++i)
#define rep3(i, a, b) for (ll i = (a); i < (b); ++i)
#define rep4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (b) - 1;i >= (a);i--)
#define rrep4(i,a,b,c) for(ll i = (a) + (((b)-(a)-1) / (c) - (((b)-(a)-1) % (c) && (((b)-(a)-1) ^ c) < 0)) * (c);i >= (a);i -= c)
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define all1(i) begin(i) , end(i)
#define all2(i,a) begin(i) , begin(i) + a
#define all3(i,a,b) begin(i) + a , begin(i) + b
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__),0LL)
template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }
template<class T> auto min(const T& a){return *min_element(all(a));}
template<class T> auto max(const T& a){return *max_element(all(a));}
template<class... Ts> void in(Ts&... t);
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); in(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)
ll intpow(ll a, ll b){ll ans = 1; while(b){if(b & 1) ans *= a; a *= a; b /= 2;} return ans;}
ll modpow(ll a, ll b, ll p){ ll ans = 1; a %= p;if(a < 0) a += p;while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
bool is_clamp(ll val,ll low,ll high) {return low <= val && val < high;}
void Yes() {cout << "Yes\n";return;}
void No() {cout << "No\n";return;}
void YES() {cout << "YES\n";return;}
void NO() {cout << "NO\n";return;}
template <typename U,typename T>
U floor(U a, T b) {return a / b - (a % b && (a ^ b) < 0);}
// ceil(x,y) = floor(x+y-1,y)なのでx+y-1がoverflowする可能性あり
template <typename U,typename T>
U ceil(U x, T y) {return floor(x + y - 1, y);}
template <typename U,typename T>
T bmod(U x, T y) {return x - y * floor(x, y);}
template <typename U,typename T>
pair<U, T> divmod(U x, T y) {U q = floor(x, y);return {q, x - q * y};}
namespace IO{
#define VOID(a) decltype(void(a))
struct setting{ setting(){cin.tie(nullptr); ios::sync_with_stdio(false);fixed(cout); cout.precision(15);}} setting;
template<int I> struct P : P<I-1>{};
template<> struct P<0>{};
template<class T> void i(T& t){ i(t, P<3>{}); }
void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){in(get<idx>(t)...);}
template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ituple(t, make_index_sequence<tuple_size<T>::value>{});} 
#undef VOID
}
#define unpack(a) (void)initializer_list<int>{(a, 0)...}
template<class... Ts> void in(Ts&... t){ unpack(IO :: i(t)); }
#undef unpack
constexpr long double PI = 3.141592653589793238462643383279L;
template <class F> struct REC {
    F f;
    REC(F &&f_) : f(forward<F>(f_)) {}
    template <class... Args> auto operator()(Args &&...args) const { return f(*this, forward<Args>(args)...); }};

constexpr int mod = 998244353;
//constexpr int mod = 1000000007;
#line 2 "library/modint/Modint.hpp"
template <int mod>
struct Modint{
    int x;
    Modint():x(0) {}
    Modint(long long y): x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    Modint &operator += (const Modint &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;}
    Modint &operator -= (const Modint &p) {
        if ((x += mod - p.x) >= mod) x -= mod;
        return *this;}
    Modint &operator *= (const Modint &p) {
        x = (int)(1LL * x * p.x % mod);
        return *this;}
    Modint &operator /= (const Modint &p) {
        *this *= p.inverse();
        return *this;}
    Modint operator -() const{return Modint(-x);}
    Modint operator +(const Modint &p) const {return Modint(*this) += p;}
    Modint operator -(const Modint &p) const {return Modint(*this) -= p;}
    Modint operator *(const Modint &p) const {return Modint(*this) *= p;}
    Modint operator /(const Modint &p) const {return Modint(*this) /= p;}
    Modint &operator ++() {if(x == mod - 1) x = 0; else x++; return *this;}
    Modint &operator --() {if(x == 0) x = mod - 1; else x--; return *this;} 
    bool operator == (const Modint &p) const {return x == p.x;}
    bool operator != (const Modint &p) const {return x != p.x;}
    Modint inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return Modint(u);}
    Modint pow(long long n) const {
        Modint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;}
    friend ostream &operator<<(ostream &os, const Modint &p) { return os << p.x; }
    friend istream &operator>>(istream &is, Modint &a) {
        long long t;
        is >> t;
        a = Modint<mod>(t);
        return (is);
    }
    int get() const { return x; }
    static constexpr int get_mod() {return mod;}
};
#line 101 "test.cpp"
using mint = Modint<mod>;
using vm = vector<mint>;
using vvm = vector<vm>;
using vvvm = vector<vvm>;
__int128_t intpow_128(ll a, ll b){__int128_t ans = 1; while(b){if(b & 1) ans *= a; a *= a; b /= 2;} return ans;}

void solve() {
    // vl A(1000),B(1000);
    // rep(i,1000) {
    //     cin >> A[i] >> B[i];
    // }
    // cout << "{";
    // rep(i,1000) {
    //     cout << A[i] << ",}"[i == 999];
    // }
    // cout << ";";
    // cout << '\n';
    // cout << "{";
    // rep(i,1000) {
    //     cout << B[i] << ",}"[i == 999];
    // }
    // cout << ";";
    // cout << '\n';
    vm V = {660428425,489539138,342933362,80366248,932132636,297529909,992353880,863186342,914198304,103424246,324551593,828552082,822975151,384101255,408840400,378326516,823527358,538382728,750723460,377645809,461617331,886446997,799875362,593301200,432985019,65081180,251193958,323057751,39500128,786222486,417704521,691673795,32993726,749093373,314839860,466329225,723081123,712653096,724519753,198194674,5090185,339319360,320229856,11960366,183717703,961245334,590882058,775125866,787613645,11964630,97182589,185120153,340910582,558113873,525726064,564120153,101348253,360420887,701552913,448120884,140747746,907600937,338830398,500845601,563678226,570520310,842247352,928533774,866462015,483885706,321799608,118924680,494375945,766552756,649703755,927814718,404084356,47764631,372658693,502805554,851934392,711133088,97229074,893654721,794912694,346064216,172825178,265028738,651034426,267914582,106899586,343679540,36396486,290391714,823074334,858302564,407347895,202332590,518492885,136561675,730745850,689420287,456628422,360850217,491388615,646425577,353173712,571191133,406034861,840905633,287136751,330396314,668187391,858333927,758506256,583847288,266155106,6432146,68779204,244771969,666821088,459406676,437610146,243318657,955279039,190864846,861400840,136677427,413303285,115099616,497559352,342190182,59376340,835790906,774417926,345209710,876176556,165215398,814773304,113208733,472761629,726114062,163537537,6997418,398507722,638733279,576841256,187471228,272293213,99820656,252396141,898779480,723563089,174710547,821835,492400346,733503178,790248609,886087673,519139784,944798815,527012056,835633893,905580329,900234870,748418347,635679528,862368724,640014538,664645306,684828274,948360065,144343733,588572694,547004710,829773535,762392324,553708108,146612104,90968178,707666023,568634653,738311552,164989409,695239971,406568483,326425809,303533381,240035115,585576571,638203017,633630003,379397612,843062112,412762761,45667194,785913783,18586477,41785285,677276702,693510655,833743230,222067288,565019932,943135207,200071750,570406860,947532148,577293964,633046218,882525252,935126595,121685420,248276259,954302418,848187791,441948986,262658328,326890944,4828534,275821623,149770258,719060661,325968039,242009955,354872859,342576884,469952212,567083833,154550475,107208572,468672617,224817644,534205108,583917421,357185567,743817880,520722155,939131046,516513917,818453328,827818780,540987691,561705497,393923232,798505017,790105872,33041911,40297838,88924336,514178536,583041356,229424953,210382698,45616795,845670871,543301209,607919775,945541479,853048806,181293875,696183578,95275072,282625125,103976933,285430686,144594489,664349800,370323391,201960571,221638220,325610959,161360259,311232898,571992629,196507778,490890729,987598299,990247911,425321509,118253785,415998741,244297923,30776295,281847538,654939097,198498315,409794532,932085762,865964220,380740866,54840851,922641463,789120244,777109597,407740745,877179631,200990678,572955832,700350540,98131442,439700359,1448741,875795480,682037785,328872918,388001025,992960787,429668647,115966082,399079632,730447288,303393108,14293582,576746727,983227729,563847888,761897757,325129839,304586012,706158940,351053183,966758207,185030715,884674148,117064595,649713895,366962371,535537156,50583684,485231554,805199836,728313174,598033511,59757754,313018821,372069001,433393296,23683527,964724035,629460205,374677027,449043381,791634947,611689872,322195816,715027037,49352336,487682931,788560985,959011422,530849092,790196080,80824588,506554651,765633192,363823210,295507545,361193672,250677169,448996426,121720220,502051862,944566064,821036107,947264317,159984211,764541960,894588189,518670479,546342346,361378860,303576439,305153158,459411410,983259981,51012898,689211258,392150157,770697740,44462113,250902322,912737941,906355256,194546533,454533565,75206475,299660253,651106521,798599232,715334543,307675678,166024301,90047109,955521541,787337653,864561418,296236380,479730761,892547942,784935895,894443476,266781997,424110738,680692378,930101711,798584062,185480859,654205124,619008756,355316751,944661076,732863833,309647693,657381147,250303683,874682344,937963356,734940430,942264468,704880102,53942890,371000431,483365901,154565877,624490547,261089749,22728227,352299040,154856044,347501527,676978318,405762402,315971164,491190557,938929403,978964377,16199828,786161106,582902960,716181046,359211287,808343094,824187294,307044601,504773418,995757314,32463785,422588885,311367082,926585164,222155485,374368534,651904621,444691564,681152547,713556025,700010968,767266505,105520904,157736100,145242246,945319147,800717933,718731860,390765012,882436854,662877264,901718320,363220991,568560928,746378182,553142007,968039386,266734515,133940654,479965203,797926961,921372098,458678161,639921903,569744755,127998129,60954427,483756144,346886435,736830170,62474172,108213697,934113573,881272256,671069424,401513642,828862677,769379200,44643441,721819638,46913945,619806765,664094020,468335693,492121842,848340121,259883532,89044144,868221561,811612062,750567312,474774385,386082205,808619579,483846331,726388441,109034722,381509348,392808085,450914683,684442715,59737876,319955889,158009189,34932738,36737114,946857106,508557549,191267433,829473739,814365523,691054295,290023463,662399995,230131761,714446155,494490939,520898041,682456966,695103525,155041136,237367797,55184936,727320319,473623471,516022284,391905466,297831113,861215840,442252904,606946361,488369469,990938455,631218870,704767871,545016909,103636743,913282812,6321431,614955406,419075232,241261395,527519500,9702061,59311304,172654528,53673868,592291254,35577707,231703384,540343910,28629612,627695529,161655417,458392430,487457638,179270506,561175544,577045289,348690220,845020832,195995327,431815420,285749736,254019917,853755528,545142435,95265003,261062709,224038867,954621973,309065935,903721054,75525347,955390706,900938518,31070197,379417646,534366402,993464681,622103615,849013089,68707362,430409974,482224769,32374321,912828034,318542039,874114340,144398422,744009760,591676410,439190382,6272884,472346542,670913871,333412275,305595015,968062452,596429552,484761945,977965118,916773727,876538160,730210692,777730671,184553259,752111127,8867681,511208706,836957130,331067999,155002613,520782635,553782650,989382906,499486655,143953804,81701190,514354404,945792732,878426171,74625747,176003028,689230220,711066508,959088997,974754977,125569923,973824179,787593,925167002,661840783,211693092,275043458,543568437,980333843,232615138,96908352,714592200,94465948,816184603,242370897,138552282,783875530,7603299,323571971,101609041,304784892,415965650,959278687,429777235,243677064,618071398,544813570,305469260,417516617,240665748,36743153,765776848,661256541,841316531,82705215,272728000,245464218,170269658,897478355,958629247,504871862,568025392,492173591,198958804,384691775,762458366,212896872,511442484,297193726,733138799,756877306,410872157,277847401,31188412,236386254,423863427,586267825,766522581,261184784,938683481,795777202,105593099,661635248,863412736,755550318,874405011,33626981,665937265,311589443,460552776,768994689,367560118,607339499,249819479,172061939,837855752,736626136,617573373,474569117,310768028,606290843,233455814,272525905,812808795,594220229,910031830,46996036,958163945,846463277,68793126,620172555,808837488,482296846,359681409,458832030,180669134,204228001,845837858,711042516,326175048,150304172,696139952,454959536,18332011,886052660,212171707,787622786,948828437,448098968,78432025,186275739,110701640,995493526,549208793,936463887,105237853,752631810,789117765,30777440,768618043,98768799,784031377,759461052,853349007,406648077,747507538,202083205,476210342,200707967,716562202,769119303,885299621,168562800,318486599,171362226,436455037,775458971,372113036,60514886,766581726,210891456,782451304,310233895,621726916,102821701,155899862,883666157,703789742,496800597,486203882,926076802,848484167,802646774,484467961,996562985,860171951,778382615,694446637,372800563,540949001,368445313,970482626,223493012,930577269,350941294,386737506,385029545,114693180,942354585,848058550,203538580,318621491,190031955,23153895,97381694,330540767,689779210,506524931,34701418,241939786,141304858,386113043,606057314,969732037,224886793,605286403,822636698,889370528,318960141,736060958,127571091,925285757,446855349,122163846,299978307,731242703,435214117,69153850,471775136,192608412,888352595,37687951,804711835,791803263,126672871,895694094,392935873,667073360,494822499,248017860,735288863,272626651,638083884,535513926,238728960,304999461,850089580,476170642,111260823,428560118,330631094,24842419,973692582,5749763,372246598,575193532,542653811,743867180,736401541,349425269,578016885,13952073,690997206,665705446,286148189,655111614,836216645,326596324,452309821,986374732,168338894,362485287,26210102,2251891,870051853,627384359,474941975,938063117,308996281,737077143,851146913,128471363,945857760,108763240,932523127,2206177,5008849,155061461,66964386,28496516,45940156,66826332,332890693,872862456,10761782,101253589,899768343,157532266,906512964,820007586,227074610,460998408,133867788,641535911,462547814,635986988,704103219,371349765,777404992,520558010,643748414,995573622,885124303,833061887,350723690,789189444,905804388,408096808,750584918,46256192,13286039,482425143,413421783,769639102,701448715,715660253,988632221,119032675,121854803,492736170,964164738,689007604,222887841,797586931,189832701,500286645,481548472,697708427,195927795,208446494,730175206,205493509,494755987,184296139,477183136,626096037,482634457,61389704,243278058,166876101,857319172,552358659,26411183,599631368,433596704,596599066,574339001,698643890,688277754,821348742,604685134,63391751,556545649,482416255,399342231,975668939,840123788,619046441,624163197,855117044,522342290,506612776,82933875,754529764,123505569,379629372,446972640,386682523,958828577,165851300,865159690,532786108,967295250,671546045,635778241};
    vl THR = {1000000000000,4000000000000,9000000000000,16000000000000,25000000000000,36000000000000,49000000000000,64000000000000,81000000000000,100000000000000,121000000000000,144000000000000,169000000000000,196000000000000,225000000000000,256000000000000,289000000000000,324000000000000,361000000000000,400000000000000,441000000000000,484000000000000,529000000000000,576000000000000,625000000000000,676000000000000,729000000000000,784000000000000,841000000000000,900000000000000,961000000000000,1024000000000000,1089000000000000,1156000000000000,1225000000000000,1296000000000000,1369000000000000,1444000000000000,1521000000000000,1600000000000000,1681000000000000,1764000000000000,1849000000000000,1936000000000000,2025000000000000,2116000000000000,2209000000000000,2304000000000000,2401000000000000,2500000000000000,2601000000000000,2704000000000000,2809000000000000,2916000000000000,3025000000000000,3136000000000000,3249000000000000,3364000000000000,3481000000000000,3600000000000000,3721000000000000,3844000000000000,3969000000000000,4096000000000000,4225000000000000,4356000000000000,4489000000000000,4624000000000000,4761000000000000,4900000000000000,5041000000000000,5184000000000000,5329000000000000,5476000000000000,5625000000000000,5776000000000000,5929000000000000,6084000000000000,6241000000000000,6400000000000000,6561000000000000,6724000000000000,6889000000000000,7056000000000000,7225000000000000,7396000000000000,7569000000000000,7744000000000000,7921000000000000,8100000000000000,8281000000000000,8464000000000000,8649000000000000,8836000000000000,9025000000000000,9216000000000000,9409000000000000,9604000000000000,9801000000000000,10000000000000000,10201000000000000,10404000000000000,10609000000000000,10816000000000000,11025000000000000,11236000000000000,11449000000000000,11664000000000000,11881000000000000,12100000000000000,12321000000000000,12544000000000000,12769000000000000,12996000000000000,13225000000000000,13456000000000000,13689000000000000,13924000000000000,14161000000000000,14400000000000000,14641000000000000,14884000000000000,15129000000000000,15376000000000000,15625000000000000,15876000000000000,16129000000000000,16384000000000000,16641000000000000,16900000000000000,17161000000000000,17424000000000000,17689000000000000,17956000000000000,18225000000000000,18496000000000000,18769000000000000,19044000000000000,19321000000000000,19600000000000000,19881000000000000,20164000000000000,20449000000000000,20736000000000000,21025000000000000,21316000000000000,21609000000000000,21904000000000000,22201000000000000,22500000000000000,22801000000000000,23104000000000000,23409000000000000,23716000000000000,24025000000000000,24336000000000000,24649000000000000,24964000000000000,25281000000000000,25600000000000000,25921000000000000,26244000000000000,26569000000000000,26896000000000000,27225000000000000,27556000000000000,27889000000000000,28224000000000000,28561000000000000,28900000000000000,29241000000000000,29584000000000000,29929000000000000,30276000000000000,30625000000000000,30976000000000000,31329000000000000,31684000000000000,32041000000000000,32400000000000000,32761000000000000,33124000000000000,33489000000000000,33856000000000000,34225000000000000,34596000000000000,34969000000000000,35344000000000000,35721000000000000,36100000000000000,36481000000000000,36864000000000000,37249000000000000,37636000000000000,38025000000000000,38416000000000000,38809000000000000,39204000000000000,39601000000000000,40000000000000000,40401000000000000,40804000000000000,41209000000000000,41616000000000000,42025000000000000,42436000000000000,42849000000000000,43264000000000000,43681000000000000,44100000000000000,44521000000000000,44944000000000000,45369000000000000,45796000000000000,46225000000000000,46656000000000000,47089000000000000,47524000000000000,47961000000000000,48400000000000000,48841000000000000,49284000000000000,49729000000000000,50176000000000000,50625000000000000,51076000000000000,51529000000000000,51984000000000000,52441000000000000,52900000000000000,53361000000000000,53824000000000000,54289000000000000,54756000000000000,55225000000000000,55696000000000000,56169000000000000,56644000000000000,57121000000000000,57600000000000000,58081000000000000,58564000000000000,59049000000000000,59536000000000000,60025000000000000,60516000000000000,61009000000000000,61504000000000000,62001000000000000,62500000000000000,63001000000000000,63504000000000000,64009000000000000,64516000000000000,65025000000000000,65536000000000000,66049000000000000,66564000000000000,67081000000000000,67600000000000000,68121000000000000,68644000000000000,69169000000000000,69696000000000000,70225000000000000,70756000000000000,71289000000000000,71824000000000000,72361000000000000,72900000000000000,73441000000000000,73984000000000000,74529000000000000,75076000000000000,75625000000000000,76176000000000000,76729000000000000,77284000000000000,77841000000000000,78400000000000000,78961000000000000,79524000000000000,80089000000000000,80656000000000000,81225000000000000,81796000000000000,82369000000000000,82944000000000000,83521000000000000,84100000000000000,84681000000000000,85264000000000000,85849000000000000,86436000000000000,87025000000000000,87616000000000000,88209000000000000,88804000000000000,89401000000000000,90000000000000000,90601000000000000,91204000000000000,91809000000000000,92416000000000000,93025000000000000,93636000000000000,94249000000000000,94864000000000000,95481000000000000,96100000000000000,96721000000000000,97344000000000000,97969000000000000,98596000000000000,99225000000000000,99856000000000000,100489000000000000,101124000000000000,101761000000000000,102400000000000000,103041000000000000,103684000000000000,104329000000000000,104976000000000000,105625000000000000,106276000000000000,106929000000000000,107584000000000000,108241000000000000,108900000000000000,109561000000000000,110224000000000000,110889000000000000,111556000000000000,112225000000000000,112896000000000000,113569000000000000,114244000000000000,114921000000000000,115600000000000000,116281000000000000,116964000000000000,117649000000000000,118336000000000000,119025000000000000,119716000000000000,120409000000000000,121104000000000000,121801000000000000,122500000000000000,123201000000000000,123904000000000000,124609000000000000,125316000000000000,126025000000000000,126736000000000000,127449000000000000,128164000000000000,128881000000000000,129600000000000000,130321000000000000,131044000000000000,131769000000000000,132496000000000000,133225000000000000,133956000000000000,134689000000000000,135424000000000000,136161000000000000,136900000000000000,137641000000000000,138384000000000000,139129000000000000,139876000000000000,140625000000000000,141376000000000000,142129000000000000,142884000000000000,143641000000000000,144400000000000000,145161000000000000,145924000000000000,146689000000000000,147456000000000000,148225000000000000,148996000000000000,149769000000000000,150544000000000000,151321000000000000,152100000000000000,152881000000000000,153664000000000000,154449000000000000,155236000000000000,156025000000000000,156816000000000000,157609000000000000,158404000000000000,159201000000000000,160000000000000000,160801000000000000,161604000000000000,162409000000000000,163216000000000000,164025000000000000,164836000000000000,165649000000000000,166464000000000000,167281000000000000,168100000000000000,168921000000000000,169744000000000000,170569000000000000,171396000000000000,172225000000000000,173056000000000000,173889000000000000,174724000000000000,175561000000000000,176400000000000000,177241000000000000,178084000000000000,178929000000000000,179776000000000000,180625000000000000,181476000000000000,182329000000000000,183184000000000000,184041000000000000,184900000000000000,185761000000000000,186624000000000000,187489000000000000,188356000000000000,189225000000000000,190096000000000000,190969000000000000,191844000000000000,192721000000000000,193600000000000000,194481000000000000,195364000000000000,196249000000000000,197136000000000000,198025000000000000,198916000000000000,199809000000000000,200704000000000000,201601000000000000,202500000000000000,203401000000000000,204304000000000000,205209000000000000,206116000000000000,207025000000000000,207936000000000000,208849000000000000,209764000000000000,210681000000000000,211600000000000000,212521000000000000,213444000000000000,214369000000000000,215296000000000000,216225000000000000,217156000000000000,218089000000000000,219024000000000000,219961000000000000,220900000000000000,221841000000000000,222784000000000000,223729000000000000,224676000000000000,225625000000000000,226576000000000000,227529000000000000,228484000000000000,229441000000000000,230400000000000000,231361000000000000,232324000000000000,233289000000000000,234256000000000000,235225000000000000,236196000000000000,237169000000000000,238144000000000000,239121000000000000,240100000000000000,241081000000000000,242064000000000000,243049000000000000,244036000000000000,245025000000000000,246016000000000000,247009000000000000,248004000000000000,249001000000000000,250000000000000000,251001000000000000,252004000000000000,253009000000000000,254016000000000000,255025000000000000,256036000000000000,257049000000000000,258064000000000000,259081000000000000,260100000000000000,261121000000000000,262144000000000000,263169000000000000,264196000000000000,265225000000000000,266256000000000000,267289000000000000,268324000000000000,269361000000000000,270400000000000000,271441000000000000,272484000000000000,273529000000000000,274576000000000000,275625000000000000,276676000000000000,277729000000000000,278784000000000000,279841000000000000,280900000000000000,281961000000000000,283024000000000000,284089000000000000,285156000000000000,286225000000000000,287296000000000000,288369000000000000,289444000000000000,290521000000000000,291600000000000000,292681000000000000,293764000000000000,294849000000000000,295936000000000000,297025000000000000,298116000000000000,299209000000000000,300304000000000000,301401000000000000,302500000000000000,303601000000000000,304704000000000000,305809000000000000,306916000000000000,308025000000000000,309136000000000000,310249000000000000,311364000000000000,312481000000000000,313600000000000000,314721000000000000,315844000000000000,316969000000000000,318096000000000000,319225000000000000,320356000000000000,321489000000000000,322624000000000000,323761000000000000,324900000000000000,326041000000000000,327184000000000000,328329000000000000,329476000000000000,330625000000000000,331776000000000000,332929000000000000,334084000000000000,335241000000000000,336400000000000000,337561000000000000,338724000000000000,339889000000000000,341056000000000000,342225000000000000,343396000000000000,344569000000000000,345744000000000000,346921000000000000,348100000000000000,349281000000000000,350464000000000000,351649000000000000,352836000000000000,354025000000000000,355216000000000000,356409000000000000,357604000000000000,358801000000000000,360000000000000000,361201000000000000,362404000000000000,363609000000000000,364816000000000000,366025000000000000,367236000000000000,368449000000000000,369664000000000000,370881000000000000,372100000000000000,373321000000000000,374544000000000000,375769000000000000,376996000000000000,378225000000000000,379456000000000000,380689000000000000,381924000000000000,383161000000000000,384400000000000000,385641000000000000,386884000000000000,388129000000000000,389376000000000000,390625000000000000,391876000000000000,393129000000000000,394384000000000000,395641000000000000,396900000000000000,398161000000000000,399424000000000000,400689000000000000,401956000000000000,403225000000000000,404496000000000000,405769000000000000,407044000000000000,408321000000000000,409600000000000000,410881000000000000,412164000000000000,413449000000000000,414736000000000000,416025000000000000,417316000000000000,418609000000000000,419904000000000000,421201000000000000,422500000000000000,423801000000000000,425104000000000000,426409000000000000,427716000000000000,429025000000000000,430336000000000000,431649000000000000,432964000000000000,434281000000000000,435600000000000000,436921000000000000,438244000000000000,439569000000000000,440896000000000000,442225000000000000,443556000000000000,444889000000000000,446224000000000000,447561000000000000,448900000000000000,450241000000000000,451584000000000000,452929000000000000,454276000000000000,455625000000000000,456976000000000000,458329000000000000,459684000000000000,461041000000000000,462400000000000000,463761000000000000,465124000000000000,466489000000000000,467856000000000000,469225000000000000,470596000000000000,471969000000000000,473344000000000000,474721000000000000,476100000000000000,477481000000000000,478864000000000000,480249000000000000,481636000000000000,483025000000000000,484416000000000000,485809000000000000,487204000000000000,488601000000000000,490000000000000000,491401000000000000,492804000000000000,494209000000000000,495616000000000000,497025000000000000,498436000000000000,499849000000000000,501264000000000000,502681000000000000,504100000000000000,505521000000000000,506944000000000000,508369000000000000,509796000000000000,511225000000000000,512656000000000000,514089000000000000,515524000000000000,516961000000000000,518400000000000000,519841000000000000,521284000000000000,522729000000000000,524176000000000000,525625000000000000,527076000000000000,528529000000000000,529984000000000000,531441000000000000,532900000000000000,534361000000000000,535824000000000000,537289000000000000,538756000000000000,540225000000000000,541696000000000000,543169000000000000,544644000000000000,546121000000000000,547600000000000000,549081000000000000,550564000000000000,552049000000000000,553536000000000000,555025000000000000,556516000000000000,558009000000000000,559504000000000000,561001000000000000,562500000000000000,564001000000000000,565504000000000000,567009000000000000,568516000000000000,570025000000000000,571536000000000000,573049000000000000,574564000000000000,576081000000000000,577600000000000000,579121000000000000,580644000000000000,582169000000000000,583696000000000000,585225000000000000,586756000000000000,588289000000000000,589824000000000000,591361000000000000,592900000000000000,594441000000000000,595984000000000000,597529000000000000,599076000000000000,600625000000000000,602176000000000000,603729000000000000,605284000000000000,606841000000000000,608400000000000000,609961000000000000,611524000000000000,613089000000000000,614656000000000000,616225000000000000,617796000000000000,619369000000000000,620944000000000000,622521000000000000,624100000000000000,625681000000000000,627264000000000000,628849000000000000,630436000000000000,632025000000000000,633616000000000000,635209000000000000,636804000000000000,638401000000000000,640000000000000000,641601000000000000,643204000000000000,644809000000000000,646416000000000000,648025000000000000,649636000000000000,651249000000000000,652864000000000000,654481000000000000,656100000000000000,657721000000000000,659344000000000000,660969000000000000,662596000000000000,664225000000000000,665856000000000000,667489000000000000,669124000000000000,670761000000000000,672400000000000000,674041000000000000,675684000000000000,677329000000000000,678976000000000000,680625000000000000,682276000000000000,683929000000000000,685584000000000000,687241000000000000,688900000000000000,690561000000000000,692224000000000000,693889000000000000,695556000000000000,697225000000000000,698896000000000000,700569000000000000,702244000000000000,703921000000000000,705600000000000000,707281000000000000,708964000000000000,710649000000000000,712336000000000000,714025000000000000,715716000000000000,717409000000000000,719104000000000000,720801000000000000,722500000000000000,724201000000000000,725904000000000000,727609000000000000,729316000000000000,731025000000000000,732736000000000000,734449000000000000,736164000000000000,737881000000000000,739600000000000000,741321000000000000,743044000000000000,744769000000000000,746496000000000000,748225000000000000,749956000000000000,751689000000000000,753424000000000000,755161000000000000,756900000000000000,758641000000000000,760384000000000000,762129000000000000,763876000000000000,765625000000000000,767376000000000000,769129000000000000,770884000000000000,772641000000000000,774400000000000000,776161000000000000,777924000000000000,779689000000000000,781456000000000000,783225000000000000,784996000000000000,786769000000000000,788544000000000000,790321000000000000,792100000000000000,793881000000000000,795664000000000000,797449000000000000,799236000000000000,801025000000000000,802816000000000000,804609000000000000,806404000000000000,808201000000000000,810000000000000000,811801000000000000,813604000000000000,815409000000000000,817216000000000000,819025000000000000,820836000000000000,822649000000000000,824464000000000000,826281000000000000,828100000000000000,829921000000000000,831744000000000000,833569000000000000,835396000000000000,837225000000000000,839056000000000000,840889000000000000,842724000000000000,844561000000000000,846400000000000000,848241000000000000,850084000000000000,851929000000000000,853776000000000000,855625000000000000,857476000000000000,859329000000000000,861184000000000000,863041000000000000,864900000000000000,866761000000000000,868624000000000000,870489000000000000,872356000000000000,874225000000000000,876096000000000000,877969000000000000,879844000000000000,881721000000000000,883600000000000000,885481000000000000,887364000000000000,889249000000000000,891136000000000000,893025000000000000,894916000000000000,896809000000000000,898704000000000000,900601000000000000,902500000000000000,904401000000000000,906304000000000000,908209000000000000,910116000000000000,912025000000000000,913936000000000000,915849000000000000,917764000000000000,919681000000000000,921600000000000000,923521000000000000,925444000000000000,927369000000000000,929296000000000000,931225000000000000,933156000000000000,935089000000000000,937024000000000000,938961000000000000,940900000000000000,942841000000000000,944784000000000000,946729000000000000,948676000000000000,950625000000000000,952576000000000000,954529000000000000,956484000000000000,958441000000000000,960400000000000000,962361000000000000,964324000000000000,966289000000000000,968256000000000000,970225000000000000,972196000000000000,974169000000000000,976144000000000000,978121000000000000,980100000000000000,982081000000000000,984064000000000000,986049000000000000,988036000000000000,990025000000000000,992016000000000000,994009000000000000,996004000000000000,998001000000000000,1000000000000000000};
    LL(N);
    mint ans;
    ll cur = 1;
    int id = -1;
    rep(i,1000) {
        if(THR[i] < N) {
            id = i;
            ans = V[i];
            cur = THR[i];
        }
    }
    vector<__int128_t> A(60,1),NA(60);
    vl B(60,1);
    rep(i,2,60) {
        if(i == 2) {
            if(id == -1) {
                A[i] = 1;
                NA[i] = 4;
                B[i] = 1;
            }
            else {
                B[i] = (id + 1) * 1000000;
                A[i] = B[i] * B[i];
                NA[i] = (B[i] + 1) * (B[i] + 1);
            }
        }
        else {
            while(intpow_128(B[i]+1,i) <= cur) B[i]++;
            A[i] = intpow_128(B[i],i);
            NA[i] = intpow_128(B[i]+1,i);
        }
    }
    ll MN = N;
    mint inv2 = mint(2).inverse();
    while(cur <= MN) {
        //debug(cur);
        mint coef = 1;
        rep(i,2,60) coef *= B[i];
        __int128_t MI = MN;
        rep(i,2,60) {
            chmin(MI,NA[i] - 1);
        }
        ll nex = MI;
        ans += mint(nex + cur) * (nex - cur + 1) * inv2 * coef;
        cur = nex + 1;
        rep(i,2,60) {
            if(NA[i] == cur) {
                // if(i == 2 && B[i] % 1000000 == 999999) {
                //     cout << ans << " " << cur << '\n';
                //     debug(ans,B[i]);
                // }
                A[i] = NA[i];
                B[i]++;
                NA[i] = intpow_128(B[i] + 1,i);
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    //INT(TT);
    int TT = 1;
    rep(i,TT) solve();
}