#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(__int128_t 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,590259375,968638466,303978748,26206291,164389147,922438246,590262573,404614954,470568127,836972037,750313417,476461472,754818127,407739202,102921501,857892697,418257587,686849910,14184362,835411899,707362213,5803417,10934980,713852438,279445078,482452347,944203380,323516630,171360434,702509971,657081491,116226935,584615712,913920104,27197266,334730720,95986969,916274661,337951751,866094552,877352074,10736147,631722687,409495184,960481863,678487886,712544062,871534215,879942395,582315133,974748537,525699246,171173493,229462852,176532015,416762453,825828868,723325562,887250749,818695597,78527364,276735757,239163504,136599602,945527394,852626991,847680712,660966260,498128948,875307245,483142495,364599158,765475665,961115445,815021280,725310956,512355526,313026251,945038909,59314552,511538038,38551944,170081409,921599538,326771802,357593303,52649162,89218819,616380035,91531177,387885936,299603938,243312266,311338224,541718798,223043455,317010102,468696480,903128466,151071750,786921948,452968181,694691450,871349137,270351752,384123867,295764439,625290878,757605737,636893618,561322132,862304464,742140220,594294389,914587660,830239221,347884152,823812848,600766355,247441584,588901597,103121873,678574566,896171533,430293589,554853869,315683886,698540208,482168754,205364636,470761569,702786164,775286558,138554957,674419024,190724037,448005480,349430819,509142912,814688874,650806435,32237218,908698287,469351328,522083857,464100390,859436780,975223970,255806601,101759607,359758340,880116362,54552495,632002681,526652426,411658879,133841940,218678479,698973433,472117781,928752288,448769381,57301645,681463810,965344085,684369307,551914109,189236036,632561564,991281629,841918755,313102436,533493984,221733876,489242126,641120805,723616678,416807551,971934784,447823340,737742010,227652539,44997115,380353696,545436590,619062954,293565221,274686555,400754214,873411249,690547152,172059734,778814567,616491831,284643685,249357017,88342572,421741001,877033761,41494739,742141759,973710018,692286063,662332777,333106992,682448701,814816189,231881147,612413838,512225574,3178917,446268740,715008418,486757439,359026261,185095654,970803323,395612408,468840712,255313153,607046281,51398700,572839450,485384685,778518450,159068736,620517432,498063627,82531171,77353927,440625319,885774784,404325574,906906340,494756487,698363225,901757397,851391954,961197887,852279187,394780409,992840056,22958188,57909504,464012052,137944869,265200496,961740251,480382425,365020762,521642806,295577218,506255533,132270402,826878328,437649467,649531197,934711135,898508171,767641404,159128192,780215647,867341068,281643810,777209436,271431354,378841678,788170719,487480748,991858425,799001336,567528866,158025899,840304425,540325185,456720574,711479643,588978739,402532610,846906616,864721808,115144754,948230,590616134,891090985,379017260,724697127,246118493,121193721,494604285,75141961,641813236,242321404,245407682,50344512,517316757,581104335,685591932,519190318,347750697,775898954,106758663,670258791,275933908,927075905,242994732,564359165,37281340,127972839,288019687,703070402,92990182,561004060,51728454,408353975,308256324,550145044,203458336,154497587,672574880,586424403,5323264,474195779,264089353,186317155,582309267,393177498,733381370,667058983,917827984,173542995,175558566,423194760,732631717,92292994,984847182,921350579,48165407,733487708,619247098,44016952,579177664,817414866,767582460,800431217,84455703,426533535,409698978,877396611,597145531,384146187,963868959,908360566,506526639,911726236,215360680,181719652,340429081,78835583,59543356,378609276,540881494,772615594,338793615,186477415,68618600,169449313,948167789,215532999,727759817,475252355,922364286,209658959,327606654,564888879,526459067,526915633,261965738,782090103,172011199,454086228,321468953,470028504,190771887,623581277,913331992,332261139,236623855,387923842,514633242,167726128,908272528,84518062,99867637,307156153,27793621,796482135,280245073,301792908,302115559,376064518,408344965,327561852,436275848,78026994,229096389,406446166,858542573,532477884,542277858,213325032,900162643,280706278,68080127,582510110,408374804,301056719,543511758,659478364,881510347,747761305,161918937,458432499,756430260,597094460,497796882,747275118,215968687,365398835,441398985,671460558,759472953,415034139,30195194,485839730,855355792,873261440,360608069,519427343,451643022,188121845,960124947,450944451,367032439,575497144,899277556,116520075,321371687,630233634,178277279,75945976,981111933,619033380,967876130,377809877,892001053,694868002,263348673,613114582,318430977,138818702,679287123,416734344,872202533,181171815,471544381,508988191,115985202,163695532,601442632,818560005,908565559,658761170,592612602,991176395,442268480,247634410,244298227,956950937,76116531,3537263,304088644,53321572,198921832,671062406,68589449,238581609,767579602,850221444,46844703,790124268,708654477,537400847,808485135,133436070,590679325,445087438,584116507,757876576,698723805,378765598,296975585,846929518,349769665,42781154,314895486,264533910,883985871,204423073,281545485,537497663,340666118,218050491,123644426,554836663,535062110,451891060,872000891,976383957,652335555,963347991,625187077,790404983,346597981,846823249,302307015,219278277,249062886,180076706,85589824,63147669,455978405,581600370,814990802,156793374,645201412,226411649,686972362,462051623,852957935,373210985,679788514,908253599,156633491,667301695,375679805,332547980,573720009,723050455,168113207,42601761,598067524,513956438,992370004,621538362,856706772,372258229,150039986,426519688,304170500,291815797,479312721,339170040,50972968,8042429,987684628,175519970,647946939,994461619,87206384,775295898,959764940,2720303,113399066,668884076,942874029,847440641,491821512,523386982,767652368,14684043,644590970,158214152,321290192,437585740,458888838,820694769,94472850,853911717,333378979,966782415,984771843,82887325,440968137,941088459,631672810,869860322,906590650,615046316,121105993,933520397,449814007,117668781,178585380,912778758,349335380,397004658,431535461,639588704,476171356,398496106,847886217,260019000,882324097,177552174,460926914,509979352,474619380,924111404,931943421,39875051,726136992,944949974,938188857,607966179,80675626,957744544,615707258,487160107,461621802,203488432,323357929,47982616,300809511,374573990,662518400,485583420,310542209,755582194,913772426,602324942,625881511,381591693,866120369,802171994,300337421,851281900,799828493,648889138,831678627,717021383,808014400,573645296,330010949,919514793,603875912,312360367,381552940,722896218,847588252,756917845,448321225,832079426,868872844,664414960,899196010,927278945,114693774,713249189,66380242,377168151,513594536,735920714,731494785,466849531,868221145,403027349,970685560,746001087,764537309,949652792,599043589,704525805,672532572,877624065,195366683,664845847,757854039,152410161,385498665,450430122,432658983,211773667,519040548,215749057,663071744,332453976,614395277,440434777,595327451,453867592,52946283,472999670,670556056,66118675,767555621,835960918,439411466,686350611,240534489,772637290,497983332,380211052,326548006,975832769,223027418,493256617,26053521,648927833,543557741,789998736,632032367,652216857,329160761,296760891,447268818,816683154,971665359,49139001,162023998,865329439,933012922,122276076,599669965,966597858,790756401,284215071,326765368,422682737,145934034,298606306,309238970,611487993,375915958,797086381,348285318,171850698,873195839,98307371,403346930,144485677,747736586,461431363,448352677,606162478,390876973,251954757,3952467,603549963,360984154,111205583,740176489,40728810,828078710,382691823,26719005,356145055,685190700,49529535,961884463,807718667,130720190,566311179,912636409,632390362,12906612,541081022,865040536,89876844,614630864,12280991,930427561,19555937,682886151,849005458,544508065,309582574,445037468,608745407,615260931,489125225,288209361,480895558,476157006,236980688,917883649,125540530,160377863,425979007,310867184,540937923,640403988,819066705,302098674,115937758,596190070,343282126,726056790,528612212,563998635,90029554,344163407,609528073,255201547,466228571,320755658,975186535,589974412,425973190,907775653,765572841,290022002,600141668,18081373,624906781,587893915,977990574,950258224,188228516,485055725,830529178,235237795,775044368,630784790,968431670,866445480,994105755,359588741,801501418,974252622,407575019,395637531,425029943,619215190,826717496,653561033,711988254,42458813,237592688,911263614,500024896,190661708,867523805,406967339,921668237,879916677,108465134,763223297,362084736,239639133,862241475,258300620,107379229,508834504,524749396,762449441,886358299,417233304,937105375,34142243,305385708,60412905,886838263,591661689,696239083,824855886,611921834,902587273,232560610,983923757,493949279,48060930,825493376,609304176,437326570,946679715,193306710,222114370,609412173,824008645,448719690,488601045,373793802,106345203,678972888,68020813,912532070,477842090,853974164,85537311,932207654,826887033,156258837,379756795,818097460,951089263,563628115,496051399,708401527,818280971,781616591,319085866,690748896,205721642,795807669,648916774,729071247,678317840,710300793,489344789,267769104,152055869,374618110,747568827,729024772,179603473,190996486,786881517,110518295,502840423,998167954,106469458,409104791,137049846,483642789,977857734,442503510,540203042,291620165,309545467,672124748,846052611,541651582,92859106,917481781,613683676,51726286,821866597,957657948,478269426,169200699,711679941,620212978,318807893,277697153,727350581,384662120};
    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();
}