結果
| 問題 | No.3505 Sum of Prod of Root |
| コンテスト | |
| ユーザー |
 2251799813685248
|
| 提出日時 | 2026-04-18 16:49:08 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 37,121 bytes |
| 記録 | |
| コンパイル時間 | 3,159 ms |
| コンパイル使用メモリ | 257,528 KB |
| 実行使用メモリ | 52,188 KB |
| 最終ジャッジ日時 | 2026-04-18 16:49:17 |
| 合計ジャッジ時間 | 7,192 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 6 WA * 7 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>
#include <random>
#include <bitset>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = array<int,2>;
using pll = array<ll,2>;
#define vall(A) A.begin(), A.end()
template<typename T> inline void vin(vector<T>& A){for (int i = 0, sz = A.size(); i < sz; i++){cin >> A[i];}}
template<typename T> inline void vout(const vector<T>& A){for (int i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}}
template<typename T> inline void vout2d(const vector<vector<T>>& A){for (int i = 0, H = A.size(); i < H; i++){vout(A[i]);}}
template<typename T> inline void adjvin(vector<T>& A){for (int i = 1, sz = A.size(); i < sz; i++){cin >> A[i];}}
template<typename T> inline void adjvout(const vector<T>& A){for (int i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}}
template<typename T> inline void adjvout2d(const vector<vector<T>>& A){for (int i = 1, H = A.size(); i < H; i++){adjvout(A[i]);}}
template<typename T> inline bool btest(T K, int i){return K&(1ull<<i);}
template<typename T> void print(T object){cout << (object) << "\n";}
template<typename T, typename U> void print(T object1, U object2){cout << (object1) << " " << (object2) << "\n";}
template<typename T, typename U, typename V> void print(T object1, U object2, V object3){cout << (object1) << " " << (object2) << " " << (object3) << "\n";}
template<typename T, typename U, typename V, typename W> void print(T object1, U object2, V object3, W object4){cout << (object1) << " " << (object2) << " " << (object3) << " " << (object4) << "\n";}
const vector<ull> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904, 9223372036854775808ull};
const vector<ull> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000, 10000000000000000000ull};
const vector<ll> di{0,1,0,-1};
const vector<ll> di8{0,1,1,1,0,-1,-1,-1};
const vector<ll> dj{1,0,-1,0};
const vector<ll> dj8{1,1,0,-1,-1,-1,0,1};
namespace a1073741824{
//library
namespace math{
//math.hpp
/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。
/// @param a
/// @param b
/// @param m
/// @return a^b%m
ll modpow(ll a, ll b, const ll m){
ll t = a%m;
ll ans = 1;
while (b > 0){
if (b%2){
ans = (ans*t)%m;
}
b /= 2;
t = (t*t)%m;
}
return ans;
}
/// @brief a^nを返す。bに関して線形時間で計算できる。
/// @param a
/// @param n
/// @param m
/// @return a^n
ll powll(ll a, ll n){
ll r = 1;
for (int i = 1; i <= n; i++){
r *= a;
}
return r;
}
/// @brief floor(sqrt(N))を返す
ll isqrt(ll N){
if (N){
ll ok = 1;
ll ng = min(N,2000000000LL);
while (ng - ok >= 2){
ll mid = (ok+ng)/2;
if (mid*mid <= N){
ok = mid;
}
else{
ng = mid;
}
}
return ok;
}
else{return 0;}
}
/// @brief floor(log_a(L))を返す
/// @param a
/// @param L
ll ilog(ll a, ll L){
__int128_t t = 1;
ll ans = 0;
while (t <= L){
ans++;
t *= a;
}
return ans-1;
}
/// @brief 正の整数Nを素因数分解する
/// @param N
/// @return vector<vector<ll> {{素因数1,個数}, {素因数2,個数}, {素因数3,個数}...}
vector<pll> p_fact(ll N){
if (N == 1){
return vector<pll> {{1,0}};
}
vector<pll> R;//戻り値用リスト
const int M = isqrt(N);
for (int i = 2; i <= M; i++){
if (N % i == 0){
ll divide_count = 0;
while (N % i == 0){
divide_count++;
N /= i;
}
R.push_back({i,divide_count});
}
}
if (N != 1){
R.push_back({N,1});
}
return R;
}
/// @brief 素因数分解リストを受け取って約数関数の値を求める
template<typename T>
ll divisor_function(const vector<array<T,2>>& vv, ll K){
if (vv[0][0] == 1){
return 1;
}
ll R = 1;
if (K == 0){
for (auto x : vv){
R *= x[1]+1;
}
}
else{
for (auto x : vv){
ll r = powll(x[0],K);
R *= (powll(r,x[1]+1) - 1)/(r - 1);
}
}
return R;
}
/// @brief 素因数分解の結果pを受け取って、約数リストを生成する。
template<typename T>
vector<T> enumerate_divisor(const vector<array<T,2>>& p){
vector<T> d{1};
if (p[0][0] == 1){
return d;
}
for (auto &v : p){
int t = d.size();
ll temp = 1;
for (int w = 0; w < v[1]; w++){
temp *= v[0];
for (int i = 0; i < t; i++){
d.push_back(d[i]*temp);
}
}
}
sort(vall(d));
return d;
}
/// @brief 有理数のfloorを求める
/// @param y
/// @param x
/// @return floor(y/x)
inline ll floor2(ll y, ll x){
if ((x^y) > 0){
x = abs(x);
y = abs(y);
return y/x;
}
else if ((x^y) < 0){
x = abs(x);
y = abs(y);
return -((y+x-1)/x);
}
else{
return y/x;
}
}
/// @brief 有理数のceilを求める
/// @param y
/// @param x
/// @return
inline ll ceil2(ll y, ll x){
if ((x^y) > 0){
x = abs(x);
y = abs(y);
return (y+x-1)/x;
}
else if ((x^y) < 0){
x = abs(x);
y = abs(y);
return -(y/x);
}
else{
return y/x;
}
}
/// @brief 線形篩
/// @attention コンストラクタに整数Nを渡すことでN以下の整数を扱うことができる。
struct LinearSieve{
vector<int> p_list;
vector<int> lpf;
//Nを渡すことで1以上N以下の整数を扱うことができる
LinearSieve(int N): lpf(N+1,-1){
lpf[1] = 1;
int p_list_size = 0;
for (int i = 2; i <= N; i++){
if (lpf[i] < 0){
p_list.push_back(i);
p_list_size++;
lpf[i] = i;
}
for (int j = 0; j < p_list_size && p_list[j] <= lpf[i] && p_list[j]*i <= N; j++){
lpf[p_list[j]*i] = p_list[j];
}
}
}
vector<pii> p_fact(int x){
if (x == 1){return {{1,0}};}
vector<pii> r;
do{
if (r.empty() || lpf[x] != r.back()[0]){
r.push_back({lpf[x], 1});
}
else{
r.back()[1]++;
}
x /= lpf[x];
}while(x > 1);
return r;
}
vector<vector<pii>> p_fact_all(int N){
vector<vector<pii>> r(N+1);
r[1].push_back({1,0});
for (int i = 2; i <= N; i++){
r[i] = p_fact(i);
}
return r;
}
};
/// @brief 一次不定方程式ax+by=1の解を1つ見つける
/// @param a `a>=0`である必要がある
/// @param b `b>=0`である必要がある
/// @return {x,y,gcd(x,y)}
template<typename T>
array<T,3> axby1(T a, T b){
T x = 1, y = 0;
T z = 0, w = 1;
T tmp;
while (b){
T p = a/b, q = a%b;
tmp = x - y * p; x = y; y = tmp;
tmp = z - w * p; z = w; w = tmp;
a = b; b = q;
}
return {x, z, a};
}
/// @brief 1/a mod Mを求める
/// @param a
/// @param M
/// @return 1/a mod M
template<typename T, typename U>
T inverse_mod(T a, U M){
auto temp = axby1(a,(T)M);
assert(temp[2] == 1);
return (M+temp[0])%M;
}
/// @brief modint
template<const int M>
struct mint{
int val = 0;
mint(const ll x){
val = x%M;
}
mint(const mint &m){
val = m.val;
}
mint(){}
mint inv(){
val = math::inverse_mod(val, M);
return *this;
}
mint pow(ll N){
val = math::modpow(val, N, M);
return *this;
}
// 入出力用オーバーロード
friend std::ostream& operator<<(std::ostream& os, const mint m){
return os << m.val;
}
friend std::istream& operator>>(std::istream& is, mint &m){
ll a;
is >> a;
m = a;
return is;
}
void operator=(const ll x){
val = x%M;
}
void operator=(const mint &a){
val = a.val;
}
bool operator==(const ll x) const{
return val == x;
}
bool operator==(const mint &a) const{
return val == a.val;
}
bool operator!=(const ll x) const{
return val != x;
}
bool operator!=(const mint &a) const{
return val != a.val;
}
mint operator+(){
return *this;
}
mint operator-(){
if (val != 0) val = M-val;
return *this;
}
mint operator+(const mint &a) const{
return mint(val+a.val);
}
void operator+=(const mint &a){
val += a.val;
if (val >= M) val -= M;
}
mint operator+(const ll b) const{
return mint(val+b%M);
}
void operator+=(const ll b){
val += b%M;
if (val >= M) val -= M;
}
mint operator-(const mint &a) const{
return mint(M+val-a.val);
}
void operator-=(const mint &a){
val += M-a.val;
if (val >= M) val -= M;
}
mint operator-(const ll b) const{
return mint(val+M-b%M);
}
void operator-=(const ll b){
val += M-b%M;
if (val >= M) val -= M;
}
mint operator*(const mint &a) const{
return mint((ll)val*a.val);
}
void operator*=(const mint &a){
val = ((ll)val*a.val)%M;
}
mint operator*(const ll b) const{
return mint(val*(b%M));
}
void operator*=(const ll b){
val = (val*(b%M))%M;
}
mint operator/(const mint &a) const{
return mint((ll)val*inverse_mod(a.val,M));
}
void operator/=(const mint &a){
val = ((ll)val*inverse_mod(a.val,M))%M;
}
mint operator/(const ll b) const{
return mint(val*inverse_mod(b%M,M));
}
void operator/=(const ll b){
val = (val*inverse_mod(b%M,M))%M;
}
};
struct dynamic_mint{
int val = 0;
int M = -1;
dynamic_mint(const ll x){
val = x;
}
dynamic_mint(const ll x, const ll MOD){
M = MOD;
val = x%M;
}
dynamic_mint(const dynamic_mint &m){
update_and_check_mod(m.M);
val = m.val;
}
dynamic_mint(){}
void update_and_check_mod(const int new_MOD){
if (M == -1 && new_MOD == -1){
//cerr << "M is invalid" << endl;
//assert(false);
}
M = max(M, new_MOD);
}
dynamic_mint inv(){
val = math::inverse_mod(val, M);
return *this;
}
dynamic_mint pow(ll N){
val = math::modpow(val, N, M);
return *this;
}
// 入出力用オーバーロード
friend std::ostream& operator<<(std::ostream& os, const dynamic_mint m){
return os << m.val;
}
friend std::istream& operator>>(std::istream& is, dynamic_mint &m){
ll a;
is >> a;
m = a;
return is;
}
void operator=(const ll x){
val = x;
}
void operator=(const dynamic_mint &a){
update_and_check_mod(a.M);
val = a.val;
}
bool operator==(const ll x) const{
return val == x;
}
bool operator==(const dynamic_mint &a) const{
return val == a.val;
}
bool operator!=(const ll x) const{
return val != x;
}
bool operator!=(const dynamic_mint &a) const{
return val != a.val;
}
dynamic_mint operator+(){
return *this;
}
dynamic_mint operator-(){
if (val != 0) val = M-val;
return *this;
}
dynamic_mint operator+(const dynamic_mint &a){
update_and_check_mod(a.M);
return dynamic_mint(val+a.val, M);
}
void operator+=(const dynamic_mint &a){
update_and_check_mod(a.M);
val += a.val;
if (val >= M) val -= M;
}
dynamic_mint operator+(const ll b){
update_and_check_mod(-1);
return dynamic_mint(val+b%M, M);
}
void operator+=(const ll b){
update_and_check_mod(-1);
val += b%M;
if (val >= M) val -= M;
}
dynamic_mint operator-(const dynamic_mint &a){
update_and_check_mod(a.M);
return dynamic_mint(M+val-a.val, M);
}
void operator-=(const dynamic_mint &a){
update_and_check_mod(a.M);
val += M-a.val;
if (val >= M) val -= M;
}
dynamic_mint operator-(const ll b){
update_and_check_mod(-1);
return dynamic_mint(val+M-b%M, M);
}
void operator-=(const ll b){
update_and_check_mod(-1);
val += M-b%M;
if (val >= M) val -= M;
}
dynamic_mint operator*(const dynamic_mint &a){
update_and_check_mod(a.M);
return dynamic_mint((ll)val*a.val, M);
}
void operator*=(const dynamic_mint &a){
update_and_check_mod(a.M);
val = ((ll)val*a.val)%M;
}
dynamic_mint operator*(const ll b){
update_and_check_mod(-1);
return dynamic_mint(val*(b%M), M);
}
void operator*=(const ll b){
update_and_check_mod(-1);
val = (val*(b%M))%M;
}
dynamic_mint operator/(const dynamic_mint &a){
update_and_check_mod(a.M);
return dynamic_mint((ll)val*inverse_mod(a.val,M), M);
}
void operator/=(const dynamic_mint &a){
update_and_check_mod(a.M);
val = ((ll)val*inverse_mod(a.val,M))%M;
}
dynamic_mint operator/(const ll b){
update_and_check_mod(-1);
return dynamic_mint(val*inverse_mod(b%M,M), M);
}
void operator/=(const ll b){
update_and_check_mod(-1);
val = (val*inverse_mod(b%M,M))%M;
}
};
//階乗前計算による二項係数mod998244353
struct factorialncr{
vector<ll> factorialmod;
vector<ll> factorialmodinv;
ll N_MAX_N_MAX;
ll MOD;
factorialncr(const ll N_MAX, const ll M){
N_MAX_N_MAX = max(1ll, N_MAX);
MOD = M;
factorialmod = vector<ll>(N_MAX+1);
factorialmodinv = vector<ll>(N_MAX+1);
factorialmod[0] = 1;
factorialmod[1] = 1;
factorialmodinv[0] = 1;
factorialmodinv[1] = 1;
for (int i = 2; i <= N_MAX; i++){
factorialmod[i] = (i*factorialmod[i-1])%M;
factorialmodinv[i] = (M-factorialmodinv[M%i]*(M/i)%M)%M;
}
for (int i = 1; i <= N_MAX; i++){
factorialmodinv[i] = (factorialmodinv[i]*factorialmodinv[i-1])%M;
}
}
ll nCr(ll n, ll r){
if (r < 0 || n < r || n > N_MAX_N_MAX){
return 0;
}
return factorialmod[n]*factorialmodinv[r]%MOD*factorialmodinv[n-r]%MOD;
}
};
//表の前計算による二項係数modM
struct tablencr{
vector<vector<ll>> ncrmodlist;
ll N_MAX_N_MAX;
public:
tablencr(const ll N_MAX, const ll M){
N_MAX_N_MAX = N_MAX;
ncrmodlist = vector<vector<ll>> (N_MAX+1, vector<ll>(N_MAX+1,0));
ncrmodlist[0][0] = 1;
for (int i = 1; i <= N_MAX; i++){
for (int j = 0; j <= i; j++){
if (j == 0 || j == i){
ncrmodlist[i][j] = 1;
}
else{
ncrmodlist[i][j] = (ncrmodlist[i-1][j-1] + ncrmodlist[i-1][j])%M;
}
}
}
}
ll nCr(ll n, ll r){
if (r < 0 || n < r || n > N_MAX_N_MAX){
return 0;
}
return ncrmodlist[n][r];
}
};
//matrix.hpp
/// @brief 行列
/// @attention 行,列共に0-indexed
/// @attention コンストラクタにHとWを渡すと、[0][0]~[H-1][W-1]までできる。
/// @attention コンストラクタ1 matrix(N)...N次単位行列
/// @attention コンストラクタ2 matrix(h,w,v)...全成分がvの行列
/// @attention コンストラクタ3 matrix(vecvec)...2次元vectorで初期化
/// @tparam T 数を表す型
template<typename T>
struct matrix{
vector<vector<T>> M;
size_t H,W;
/// @brief N次単位行列を生成
/// @param N
matrix(size_t N){
H = N;W = N;
M = vector<vector<T>>(N,vector<T>(N,0));
for (int i = 0; i < N; i++){
M[i][i] = 1;
}
}
/// @brief h×w型の、全要素がvの行列を生成
/// @param h
/// @param w
/// @param v
matrix(int h, int w, T v){
H = h;
W = w;
M = vector<vector<T>>(H,vector<T>(W,v));
}
/// @brief 2次元配列を用いて行列を生成
/// @param A
matrix(const vector<vector<T>> &A){
M = A;
H = A.size();
W = A[0].size();
}
matrix operator+(const matrix &A)const{
if (H != A.H || W != A.W){
cerr << "size error(operator+)" << endl;
assert(false);
}
matrix ans(M);
for (int i = 0; i < H; i++){
for (int j = 0; j < W; j++){
ans.M[i][j] += A.M[i][j];
}
}
return ans;
}
void operator+=(const matrix &A){
if (H != A.H || W != A.W){
cerr << "size error(operator+=)" << endl;
assert(false);
}
for (int i = 0; i < H; i++){
for (int j = 0; j < W; j++){
M[i][j] += A.M[i][j];
}
}
}
matrix operator-(const matrix &A)const{
if (H != A.H || W != A.W){
cerr << "size error(operator-)" << endl;
assert(false);
}
matrix ans(M);
for (int i = 0; i < H; i++){
for (int j = 0; j < W; j++){
ans.M[i][j] -= A.M[i][j];
}
}
return ans;
}
void operator-=(const matrix &A){
if (H != A.H || W != A.W){
cerr << "size error(operator-=)" << endl;
assert(false);
}
for (int i = 0; i < H; i++){
for (int j = 0; j < W; j++){
M[i][j] -= A.M[i][j];
}
}
}
matrix operator*(const matrix &A)const{
if (W != A.H){
cerr << "size error(operator*)" << endl;
assert(false);
}
matrix ans(H,A.W,0);
for (int i = 0; i < H; i++){
for (int k = 0; k < W; k++){
T constval = M[i][k];
for (int j = 0; j < A.W; j++){
ans.M[i][j] += constval*A.M[k][j];
}
}
}
return ans;
}
void operator*=(const matrix &A){
if (W != A.H){
cerr << "size error(operator*=)" << endl;
assert(false);
}
matrix ans(H,A.W,0);
for (int i = 0; i < H; i++){
for (int k = 0; k < W; k++){
T constval = M[i][k];
for (int j = 0; j < A.W; j++){
ans.M[i][j] += constval*A.M[k][j];
}
}
}
W = A.W;
M = ans.M;
}
matrix operator*(const T c)const{
matrix ans(H,W,0);
for (int i = 0; i < H; i++){
for (int j = 0; j < W; j++){
ans.M[i][j] = M[i][j] * c;
}
}
return ans;
}
void operator*=(const T c){
for (int i = 0; i < H; i++){
for (int j = 0; j < W; j++){
M[i][j] *= c;
}
}
}
/// @brief i行目を1/c倍
/// @param i
/// @param c
void row_transformation_division(size_t i, T c){
for (int j = 0; j < W; j++){
M[i][j] /= c;
}
}
/// @brief i行目のc倍を、j行目から減算
/// @param i
/// @param j
/// @param c
void row_transformation_sub_row(size_t i, T c, size_t j){
for (int k = 0; k < W; k++){
M[j][k] -= M[i][k]*c;
}
}
/// @brief 行の数を返す
size_t size(){return H;}
bool empty(){return H == 0;}
vector<T>& operator[](const int row){
return M[row];
}
/// @brief 行列を2次元累積和テーブルに変換する。
void cumulative2d(){
for (int i = 0; i < H; i++){
for (int j = 1; j < W; j++){
M[i][j] += M[i][j-1];
}
}
for (int i = 1; i < H; i++){
for (int j = 0; j < W; j++){
M[i][j] += M[i-1][j];
}
}
}
T sum_from_origin(int r, int c){
if (r < 0 || c < 0){return 0;}
return M[r][c];
}
/// @brief r1<=行番号<=r2, c1<=列番号<=c2を満たすような部分の総和を求める。
/// @param r1
/// @param r2
/// @param c1
/// @param c2
/// @return 和
T rectangle_sum(int r1, int r2, int c1, int c2){
if (r1 > r2 || c1 > c2){return 0;}
return M[r2][c2] - M[r2][c1-1] - M[r1-1][c2] + M[r1-1][c1-1];
}
};
/// @brief A^Nを返す。
/// @param A
/// @param N
/// @return A^N
template<typename T>
matrix<T> matrixpow(matrix<T> M, ll N){
matrix<T> R(M.H);
if (N){
while (N){
if (N%2){
R *= M;
}
M *= M;
N /= 2;
}
return R;
}
else{
return R;
}
}
/// @brief 与えられた行列を行簡約化する
/// @tparam T
/// @param M
/// @return
template<typename T>
matrix<T> row_simplification(matrix<T> M){
int non_zero_column = 0;
for (int i = 0; i < M.H; i++){
bool finished = false;
while (!finished){
if (non_zero_column == M.W){
return M;
}
for (int k = i; k < M.H; k++){
if (M[k][non_zero_column] != 0){
swap(M[i],M[k]);
M.row_transformation_division(i, M[i][non_zero_column]);
for (int l = 0; l < M.H; l++){
if (l == i){continue;}
M.row_transformation_sub_row(i, M[l][non_zero_column]/M[i][non_zero_column], l);
}
finished = true;
break;
}
}
non_zero_column++;
}
}
return M;
}
template<typename T>
pair<bool, matrix<T>> inverse_matrix(matrix<T> M){
if (M.H != M.W){
cerr << "This is not a square matrix" << endl;
assert(false);
}
for (int i = 0; i < M.H; i++){
for (int j = 0; j < M.W; j++){
M[i].push_back(0);
}
M[i][M.W+i] = 1;
}
M.W *= 2;
M = row_simplification(M);
M.W /= 2;
bool regular = true;
for (ll i = 0; i < M.H; i++) if (M[i][i] == 0) regular = false;
for (int i = 0; i < M.H; i++){
M[i].erase(M[i].begin(), M[i].begin()+M.W);
}
return make_pair(regular, M);
}
ll internal_floor_sum(ll A, ll B, ll C){
if (C < 0){return 0;}
if (A > B){return internal_floor_sum(B,A,C);}
if (B%A == 0){
return (1+floor2(C,A))*(1+floor2(C,B)) - (B/A)*floor2(C,B)*(floor2(C,B)+1)/2;
}
ll k = floor2(C-B*floor2(C,B),A);
return (1+k)*(1+floor2(C,B)) + floor2(B,A)*floor2(C,B)*(floor2(C,B)+1)/2 + internal_floor_sum(A, B%A, C-A*(floor2(B,A)*floor2(C,B)+k+1));
}
/// @brief `\sum_{i=0}^{N} \lfloor\frac{Ci+D}{B}\rfloor`を求める。
/// @param N
/// @param M
/// @param A
/// @param B
/// @return
ll floor_sum(ll N, ll B, ll C, ll D){
if (N < 0){
return 0;
}
if (B < 0){//Bを負にする。
B *= -1;
C *= -1;
D *= -1;
}
if (C > 0){//Cを負にするが、Cを-Cに置き換えてC>0として扱う。
D += N*C;
}
else{
C *= -1;
}
if (C == 0){
return (N+1)*floor2(D,B);
}
ll k = floor2(D-C*N,B);
return (N+1)*k + internal_floor_sum(B,C,D-B*(k+1));
}
ll internal_floor_max(ll A, ll B, ll C, ll D, ll E, ll F){
if (D < 0){return -1000000000000000000;}
if (B <= 0){return -1000000000000000000;}
if (E > 0){
if (B > C){return internal_floor_max(E,C,B,D,A,F);}
ll M = floor2(D-C*floor2(D, C), B);
ll tempans = max(A*M+E*floor2(D, C), A*floor2(D, B)) + F;
return max(tempans, A*(1+M)+internal_floor_max(A, B, C%B, D-B*(1+M+floor2(C, B)*floor2(D, C)), E-A*floor2(C, B), F+A*floor2(C, B)*floor2(D, C)));
}
else return A*floor2(D, B) + F;
}
/// @brief `0<=x<=N`の下で、`A*floor2(C*x+D, B)+E*x+F`の最大値を求める。もし何かがおかしいなら`-10^18`が返される。
/// @param N
/// @param A
/// @param B
/// @param C
/// @param D
/// @param E
/// @param F
/// @return `max`
ll floor_max(ll N, ll A, ll B, ll C, ll D, ll E, ll F){
if (N < 0){
return -1000000000000000000;
}
assert(B != 0);
//マイナスを処理
if (B < 0){
B *= -1;
C *= -1;
D *= -1;
}
if (A < 0){
A *= -1;
C *= -1;
D *= -1;
D += B-1;
}
//自明なケース
if (C == 0 or A == 0){
return A*floor2(D, B) + F + max(0LL, E*N);
}
if (E == 0){
return A*floor2(max(0LL, C*N)+D, B) + F;
}
//Cの係数を調整
if (C > 0){
F += E*N;
E *= -1;
D += C*N;
}
else{
//`A*floor2(D-C*x, B)+E*x+F`, `A,B,C>0`にする
C *= -1;
}
//自明なケースを処理
if (E < 0){
return A*floor2(D, B) + F;
}
ll x_offset = floor2(D-C*N, B)+1;
D -= B*x_offset;
return A*x_offset + max(internal_floor_max(A,B,C,D,E,F), -A+E*N+F);
}
//convolution.hpp
vector<ll> powroot998244353{1LL, 998244352LL, 911660635LL, 372528824LL, 69212480LL, 381091786LL, 515872972LL, 273395035LL, 469477650LL, 503794470LL, 464513504LL, 558899782LL, 504969456LL, 840897051LL, 539927980LL, 417009993LL, 725461291LL, 456548895LL, 712494065LL, 542639453LL, 768214923LL, 303507821LL, 438914733LL, 761881641};
vector<ll> powrootinv998244353{1LL, 998244352LL, 86583718LL, 509520358LL, 661054123LL, 863921598LL, 323451984LL, 689146517LL, 379690232LL, 240519260LL, 899368279LL, 920065956LL, 588792270LL, 118574449LL, 847593593LL, 858760106LL, 987418793LL, 177938570LL, 753608159LL, 786906984LL, 331540181LL, 655706071LL, 268754442LL, 191076546};
vector<ll> powroot1224736769{1LL, 1224736768LL, 24506215LL, 992888437LL, 853017291LL, 235319402LL, 269744380LL, 157861287LL, 894223137LL, 600648668LL, 1091208103LL, 382541006LL, 12818149LL, 149218560LL, 746299392LL, 405692663LL, 633223136LL, 672327338LL, 992917013LL, 758198491LL, 1079610480LL, 1056667043LL, 1039331205LL, 1026803890LL, 449603200};
vector<ll> powrootinv1224736769{1LL, 1224736768LL, 1200230554LL, 961581489LL, 796105727LL, 1023008969LL, 406386483LL, 251411652LL, 655108271LL, 1145368249LL, 780593535LL, 38041180LL, 816166160LL, 659160240LL, 1200430513LL, 392462252LL, 15561184LL, 893027826LL, 928760284LL, 497993173LL, 529117122LL, 637457654LL, 931394937LL, 823596420LL, 55047034};
vector<ll> DFT998244353(vector<ll> X, ll K, bool inverse = false){
if (K == 1){
return vector<ll>{(X[0]+X[1])%998244353, (998244353+X[0]-X[1])%998244353};
}
vector<ll> even(1<<(K-1));
vector<ll> odd(1<<(K-1));
for (int i = 0; i < (1<<(K-1)); i++){
even[i] = (X[i] + X[(1<<(K-1))+i])%998244353;
}
ll temp = 1;
if (inverse){
for (int i = 0; i < (1<<(K-1)); i++){
odd[i] = (temp*(998244353 + X[i] - X[(1<<(K-1))+i]))%998244353;
temp = (temp*powrootinv998244353[K])%998244353;
}
}
else{
for (int i = 0; i < (1<<(K-1)); i++){
odd[i] = (temp*(998244353 + X[i] - X[(1<<(K-1))+i]))%998244353;
temp = (temp*powroot998244353[K])%998244353;
}
}
even = DFT998244353(even,K-1,inverse);
odd = DFT998244353(odd,K-1,inverse);
for (int i = 0; i < (1<<K); i++){
if (i%2){
X[i] = odd[i/2];
}
else{
X[i] = even[i/2];
}
}
return X;
}
vector<ll> DFT1224736769(vector<ll> X, ll K, bool inverse = false){
if (K == 1){
return vector<ll>{(X[0]+X[1])%1224736769, (1224736769+X[0]-X[1])%1224736769};
}
vector<ll> even(1<<(K-1));
vector<ll> odd(1<<(K-1));
for (int i = 0; i < (1<<(K-1)); i++){
even[i] = (X[i] + X[(1<<(K-1))+i])%1224736769;
}
ll temp = 1;
if (inverse){
for (int i = 0; i < (1<<(K-1)); i++){
odd[i] = (temp*(1224736769 + X[i] - X[(1<<(K-1))+i]))%1224736769;
temp = (temp*powrootinv1224736769[K])%1224736769;
}
}
else{
for (int i = 0; i < (1<<(K-1)); i++){
odd[i] = (temp*(1224736769 + X[i] - X[(1<<(K-1))+i]))%1224736769;
temp = (temp*powroot1224736769[K])%1224736769;
}
}
even = DFT1224736769(even,K-1,inverse);
odd = DFT1224736769(odd,K-1,inverse);
for (int i = 0; i < (1<<K); i++){
if (i%2){
X[i] = odd[i/2];
}
else{
X[i] = even[i/2];
}
}
return X;
}
vector<ll> convolution998244353(vector<ll> A, vector<ll> B){
if (min(A.size(), B.size()) <= 60) {
if (A.size() < B.size()) {
swap(A, B);
}
std::vector<ll> ans(A.size() + B.size() - 1);
for (size_t i = 0; i < A.size(); i++) {
for (size_t j = 0; j < B.size(); j++) {
ans[i+j] += A[i] * B[j];
ans[i+j] %= 998244353;
}
}
return ans;
}
ll N = A.size()+B.size()-1;
ll log2N = 0;
while ((1LL<<log2N) < N){
log2N++;
}
while (A.size() < (1ULL<<log2N)){
A.push_back(0);
}
while (B.size() < (1ULL<<log2N)){
B.push_back(0);
}
A = DFT998244353(A,log2N);
B = DFT998244353(B,log2N);
vector<ll> C((1LL<<log2N),0);
for (int i = 0; i < (1<<log2N); i++){
C[i] = (A[i]*B[i])%998244353;
}
C = DFT998244353(C,log2N,1);
ll invpow2log2N = inverse_mod((1LL<<log2N),998244353);
for (int i = 0; i < (1<<log2N); i++){
C[i] = (C[i]*invpow2log2N)%998244353;
}
return C;
}
vector<ll> convolution1224736769(vector<ll> A, vector<ll> B){
if (min(A.size(), B.size()) <= 60) {
if (A.size() < B.size()) {
swap(A, B);
}
std::vector<ll> ans(A.size() + B.size() - 1);
for (size_t i = 0; i < A.size(); i++) {
for (size_t j = 0; j < B.size(); j++) {
ans[i+j] += A[i] * B[j];
ans[i+j] %= 1224736769;
}
}
for (auto &v : ans){
v %= 1224736769;
}
return ans;
}
ll N = A.size()+B.size()-1;
ll log2N = 0;
while ((1LL<<log2N) < N){
log2N++;
}
while (A.size() < (1ULL<<log2N)){
A.push_back(0);
}
while (B.size() < (1ULL<<log2N)){
B.push_back(0);
}
A = DFT1224736769(A,log2N);
B = DFT1224736769(B,log2N);
vector<ll> C((1LL<<log2N),0);
for (int i = 0; i < (1<<log2N); i++){
C[i] = (A[i]*B[i])%1224736769;
}
C = DFT1224736769(C,(1<<log2N),1);
ll invpow2log2N = inverse_mod((1LL<<log2N),1224736769);
for (int i = 0; i < (1<<log2N); i++){
C[i] = (C[i]*invpow2log2N)%1224736769;
}
return C;
}
/// @brief [x^N](P(x)/Q(x))をmod998244353で求める。
/// @param N
/// @param P
/// @param Q
/// @return
ll Bostan_Mori998244353(const ll N, vector<ll> P, vector<ll> Q){
assert(N >= 0);
if (N == 0){
return P[0]*math::inverse_mod(Q[0], 998244353);
}
vector<ll> Q_minus;
const int maxloop = (N == 1 ? 1 : 65-__builtin_clzll(N-1));
for (int _i_ = 0; _i_ < maxloop; _i_++){
Q_minus.resize(Q.size());
for (size_t i = 0; i < Q_minus.size(); i += 2){
Q_minus[i] = Q[i];
}
for (size_t i = 1; i < Q_minus.size(); i += 2){
Q_minus[i] = 998244352*Q[i]%998244353;
}
auto A = math::convolution998244353(P,Q_minus);
auto B = math::convolution998244353(Q,Q_minus);
Q.resize((B.size()+1)/2);
for (size_t i = 0; i < B.size(); i += 2){
Q[i/2] = B[i];
}
P.resize((A.size()+!btest(N,_i_))/2);
for (size_t i = btest(N,_i_); i < A.size(); i += 2){
P[i/2] = A[i];
}
}
return P[0]*math::inverse_mod(Q[0], 998244353);
}
}
}
using namespace a1073741824;
using namespace math;
using mll = math::mint<998244353>;
using dmll = math::dynamic_mint;
#define lll __int128_t
ll fast_isqrt(ll x){
ll ret = sqrt(x);
while (ret*ret > x){
ret--;
}
while ((ret+1)*(ret+1) <= x){
ret++;
}
return ret;
}
long long safe_pow(long long a,long long b){
long long res=1;
for(long long i=0;i<b;i++){
long double dres=res;
dres*=a;
if(dres>2e18){return 2e18;}
res*=a;
}
return res;
}
ull kth_root(ull a,ull b){
if(a==0)return 0;
if(b==1)return a;
if(b>=64)return 1;
auto my_pow=[&](ull A,ull B)->ull{
ull res=1;
while(B){
if(B%2){
if(lll(res)*A>a)return 0;
res*=A;
}
B/=2;
if(B){
if(lll(A)*A>a)return 0;
A*=A;
}
}
return res;
};
ull ac=1,wa=(ull(1)<<(64/b+1))+1;
while(wa-ac>1){
ull wj=ac+wa>>1;
auto res=my_pow(wj,b);
if(res&&res<=a){
ac=wj;
}else wa=wj;
}
return ac;
}
ll sum_iisqrti(ll N){
if (N <= 0){return 0;}
lll M = fast_isqrt(N);
lll ans = 0;
ans += 149736653*(M*M%998244353*M%998244353-M)%998244353*(8*M*M%998244353-5*M%998244353-2)%998244353;
ans += (499122177*M%998244353)*(N%998244353*(N%998244353+1)%998244353-M*M%9998244353*(M*M%998244353-1)%998244353)%998244353;
return (998244353+ans%998244353)%998244353;
}
void solve(){
ll N;
cin >> N;
vector<pll> transitions;
transitions.push_back({N+1, -1});
for (ll i = 60; i >= 3; i--){
vector<pll> temp;
for (ll j = 2;; j++){
ll temp2 = safe_pow(j,i);
if (temp2 > N){break;}
temp.push_back({temp2, j});
}
reverse(vall(temp));
vector<pll> transitions2;
while (true){
if (temp.empty()){
for (ll i = (ll)transitions.size()-1; i >= 0; i--){
transitions2.push_back(transitions[i]);
}
break;
}
if (transitions.empty()){
for (ll i = (ll)temp.size()-1; i >= 0; i--){
transitions2.push_back(temp[i]);
}
break;
}
if (temp.back()[0] < transitions.back()[0]){
transitions2.push_back(temp.back());
temp.pop_back();
}
else{
transitions2.push_back(transitions.back());
transitions.pop_back();
}
}
reverse(vall(transitions2));
transitions = transitions2;
}
sort(vall(transitions));
reverse(vall(transitions));
lll temp = 1;
lll prev = 1;
lll ans = 0;
for (ll i = (ll)transitions.size()-1; i >= 0; i--){
auto& now = transitions[i];
if (prev < now[0]){
ans += temp*(sum_iisqrti(now[0]-1)-sum_iisqrti(prev-1))%998244353;
ans %= 998244353;
}
temp = temp*inverse_mod((now[1]-1)%998244353, 998244353)%998244353*(now[1]%998244353)%998244353;
prev = now[0];
}
print((ll)(998244353+ans%998244353)%998244353);
//ans = 0;
//for (ll i = 0; i <= N; i++){
// temp = i;
// for (ll j = 2; j <= 60; j++){
// temp = temp*kth_root(i,j)%998244353;
// }
// ans += temp;
// ans %= 998244353;
//}
//print((ll)ans);
}
//1000000000000000000
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll T = 1;
//cin >> T;
while (T--){
solve();
}
//print(sum_iisqrti(1000000000000000001) - sum_iisqrti(1000000000000000000)+998244353);
//print((pow10ll[18]%998244353+1)*pow10ll[9]%998244353);
}