//////////////////////////////////////////////////////////////////////////////// // Give me AC!!! // //////////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include #include using namespace std; namespace mp = boost::multiprecision; using namespace mp; using ull = __int128; using ll = long long; using cll = cpp_int; using Graph = vector>; #define REP(i,n) for(ll i=0;i<(ll)(n);i++) #define REPD(i,n) for(ll i=n-1;i>=0;i--) #define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++) #define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--) //xにはvectorなどのコンテナ #define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい #define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく #define MAX(x) *max_element(ALL(x)) //最大値を求める #define MIN(x) *min_element(ALL(x)) //最小値を求める #define PQ priority_queue,vector>,greater>> #define INF 1000000000000 //10^12:極めて大きい値,∞ #define PB push_back //vectorヘの挿入 #define MP make_pair //pairのコンストラクタ #define F first //pairの一つ目の要素 #define S second //pairの二つ目の要素 #define coutY cout<<"YES"< a(b) #define vl(a,b) vector a(b) #define vs(a,b) vector a(b) #define vll(a,b,c) vector> a(b, vector(c)); #define intque(a) queue a; #define llque(a) queue a; #define intque2(a) priority_queue, greater> a; #define llque2(a) priority_queue, greater> a; #define pushback(a,b) a.push_back(b) #define mapii(M1) map M1; #define cou(v,x) count(v.begin(), v.end(), x) #define mapll(M1) map M1; #define mapls(M1) map M1; #define mapsl(M1) map M1; #define twolook(a,l,r,x) lower_bound(a+l, a+r, x) - a #define sor(a) sort(a.begin(), a.end()) #define rever(a) reverse(a.begin(),a.end()) #define rep(i,a) for(ll i=0;i>n[i] #define vcout(n) for(ll i=0;i>n[i][j] //const ll mod = 998244353; //const ll MOD = 998244353; const ll MOD = 1000000007; const ll mod = 1000000007; constexpr ll MAX = 5000000; //const ll _max = 9223372036854775807; const ll _max = 1223372036854775807; ll fac[MAX],finv[MAX],inv[MAX]; // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int modPow(long long a, long long n, long long p) { if (n == 0) return 1; // 0乗にも対応する場合 if (n == 1) return a % p; if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p; long long t = modPow(a, n / 2, p); return (t * t) % p; } ll clocks(ll a,ll b,ll c){ return a*3600+b*60+c; } ll divup(ll b,ll d){ if(b%d==0){ return b/d; } else{ return b/d+1; } } struct UnionFind { vector par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2 UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化 for(int i = 0; i < N; i++) par[i] = i; } int root(int x) { // データxが属する木の根を再帰で得る:root(x) = {xの木の根} if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(int x, int y) { // xとyの木を併合 int rx = root(x); //xの根をrx int ry = root(y); //yの根をry if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける } bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す int rx = root(x); int ry = root(y); return rx == ry; } }; struct Edge { int to; // 辺の行き先 int weight; // 辺の重み Edge(int t, int w) : to(t), weight(w) { } }; using Graphw = vector>; ll zero(ll a){ return max(ll(0),a); } template< typename T > struct FormalPowerSeries : vector< T > { using vector< T >::vector; using P = FormalPowerSeries; using MULT = function< P(P, P) >; static MULT &get_mult() { static MULT mult = nullptr; return mult; } static void set_fft(MULT f) { get_mult() = f; } void shrink() { while(this->size() && this->back() == T(0)) this->pop_back(); } P operator+(const P &r) const { return P(*this) += r; } P operator+(const T &v) const { return P(*this) += v; } P operator-(const P &r) const { return P(*this) -= r; } P operator-(const T &v) const { return P(*this) -= v; } P operator*(const P &r) const { return P(*this) *= r; } P operator*(const T &v) const { return P(*this) *= v; } P operator/(const P &r) const { return P(*this) /= r; } P operator%(const P &r) const { return P(*this) %= r; } P &operator+=(const P &r) { if(r.size() > this->size()) this->resize(r.size()); for(int i = 0; i < r.size(); i++) (*this)[i] += r[i]; return *this; } P &operator+=(const T &r) { if(this->empty()) this->resize(1); (*this)[0] += r; return *this; } P &operator-=(const P &r) { if(r.size() > this->size()) this->resize(r.size()); for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i]; shrink(); return *this; } P &operator-=(const T &r) { if(this->empty()) this->resize(1); (*this)[0] -= r; shrink(); return *this; } P &operator*=(const T &v) { const int n = (int) this->size(); for(int k = 0; k < n; k++) (*this)[k] *= v; return *this; } P &operator*=(const P &r) { if(this->empty() || r.empty()) { this->clear(); return *this; } assert(get_mult() != nullptr); return *this = get_mult()(*this, r); } P &operator%=(const P &r) { return *this -= *this / r * r; } P operator-() const { P ret(this->size()); for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i]; return ret; } P &operator/=(const P &r) { if(this->size() < r.size()) { this->clear(); return *this; } int n = this->size() - r.size() + 1; return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n); } P pre(int sz) const { return P(begin(*this), begin(*this) + min((int) this->size(), sz)); } P operator>>(int sz) const { if(this->size() <= sz) return {}; P ret(*this); ret.erase(ret.begin(), ret.begin() + sz); return ret; } P operator<<(int sz) const { P ret(*this); ret.insert(ret.begin(), sz, T(0)); return ret; } P rev(int deg = -1) const { P ret(*this); if(deg != -1) ret.resize(deg, T(0)); reverse(begin(ret), end(ret)); return ret; } P diff() const { const int n = (int) this->size(); P ret(max(0, n - 1)); for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i); return ret; } P integral() const { const int n = (int) this->size(); P ret(n + 1); ret[0] = T(0); for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1); return ret; } // F(0) must not be 0 P inv(int deg = -1) const { assert(((*this)[0]) != T(0)); const int n = (int) this->size(); if(deg == -1) deg = n; P ret({T(1) / (*this)[0]}); for(int i = 1; i < deg; i <<= 1) { ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1); } return ret.pre(deg); } // F(0) must be 1 P log(int deg = -1) const { assert((*this)[0] == 1); const int n = (int) this->size(); if(deg == -1) deg = n; return (this->diff() * this->inv(deg)).pre(deg - 1).integral(); } P sqrt(int deg = -1) const { const int n = (int) this->size(); if(deg == -1) deg = n; if((*this)[0] == T(0)) { for(int i = 1; i < n; i++) { if((*this)[i] != T(0)) { if(i & 1) return {}; if(deg - i / 2 <= 0) break; auto ret = (*this >> i).sqrt(deg - i / 2) << (i / 2); if(ret.size() < deg) ret.resize(deg, T(0)); return ret; } } return P(deg, 0); } P ret({T(1)}); T inv2 = T(1) / T(2); for(int i = 1; i < deg; i <<= 1) { ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2; } return ret.pre(deg); } // F(0) must be 0 P exp(int deg = -1) const { assert((*this)[0] == T(0)); const int n = (int) this->size(); if(deg == -1) deg = n; P ret({T(1)}); for(int i = 1; i < deg; i <<= 1) { ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1); } return ret.pre(deg); } P pow(int64_t k, int deg = -1) const { const int n = (int) this->size(); if(deg == -1) deg = n; for(int i = 0; i < n; i++) { if((*this)[i] != T(0)) { T rev = T(1) / (*this)[i]; P C(*this * rev); P D(n - i); for(int j = i; j < n; j++) D[j - i] = C[j]; D = (D.log() * k).exp() * (*this)[i].pow(k); P E(deg); if(i * k > deg) return E; auto S = i * k; for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j]; return E; } } return *this; } T eval(T x) const { T r = 0, w = 1; for(auto &v : *this) { r += w * v; w *= x; } return r; } }; //aはbの何乗以下かを満たす数の内最大の物,(a,10)はaの桁数 ll expless(ll a,ll b){ ll k=0; ll o=1; while(a>=o){ k++; o=o*b; } return k; } //aをb進法で表す //b進法のaを10進法に直す ll tenbase(ll a,ll b){ ll c=expless(a,10); ll ans=0; ll k=1; for(int i=0;i > prime_factorize(long long N) { vector > res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++ex; N /= a; } // その結果を push res.push_back({a, ex}); } // 最後に残った数について if (N != 1) res.push_back({N, 1}); return res; } ll atll(ll a,ll b){ b++; ll c=expless(a,10); ll d=c-b; ll f=1; for(int i=0;i vector smallest_prime_factors(T n) { vector spf(n + 1); for (int i = 0; i <= n; i++) spf[i] = i; for (T i = 2; i * i <= n; i++) { // 素数だったら if (spf[i] == i) { for (T j = i * i; j <= n; j += i) { // iを持つ整数かつまだ素数が決まっていないなら if (spf[j] == j) { spf[j] = i; } } } } return spf; } vector> factolization(ll x, vector &spf) { vector> ret; ll p; ll z; while (x != 1) { p=(spf[x]); z=0; while(x%p==0){ z++; x /= p; } ret.push_back({p, z}); } return ret; } vector is; vector prime_(ll n){ is.resize(n+1, true); is[0] = false; is[1] = false; vector primes; for (int i=2; i<=n; i++) { if (is[i] == true){ primes.push_back(i); for (int j=i*2; j<=n; j+=i){ is[j] = false; } } } return primes; } vector dijkstra(ll f,ll n,vector>>& edge){ //最短経路としてどの頂点が確定済みかをチェックする配列 vector confirm(n,false); //それぞれの頂点への最短距離を保存する配列 //始点は0,始点以外はINFで最短距離を初期化する vector mincost(n,INF);mincost[f]=0; //確定済みの頂点の集合から伸びる辺を伝ってたどり着く頂点の始点からの距離を短い順に保存するPriority queue PQ mincand;mincand.push({mincost[f],f}); //mincandの要素がゼロの時、最短距離を更新できる頂点がないことを示す while(!mincand.empty()){ //最短距離でたどり着くと思われる頂点を取り出す vector next=mincand.top();mincand.pop(); //すでにその頂点への最短距離が確定済みの場合は飛ばす if(confirm[next[1]]) continue; //確定済みではない場合は確定済みにする confirm[next[1]]=true; //その確定済みの頂点から伸びる辺の情報をとってくる(参照の方が速い)、lは辺の本数 vector>& v=edge[next[1]];ll l=SIZE(v); REP(i,l){ //辺の先が確定済みなら更新する必要がない((✳︎2)があれば十分なので(✳︎1)は実はいらない) if(confirm[v[i][0]]) continue; //(✳︎1) //辺の先のmincost以上の場合は更新する必要がない(辺の先が確定済みの時は満たす) if(mincost[v[i][0]]<=next[0]+v[i][1]) continue; //(✳︎2) //更新 mincost[v[i][0]]=next[0]+v[i][1]; //更新した場合はその頂点が(確定済みでない頂点の中で)最短距離になる可能性があるのでmincandに挿入 mincand.push({mincost[v[i][0]],v[i][0]}); } } return mincost; } ll so(ll a){ ll ans=0; if(a==0){ return 0; } while(a%2==0){ a/=2; ans++; } return ans; } ll HOM(ll n,ll r){ return COM(n+r-1,r); } ll binary(ll bina){ ll ans = 0; for (ll i = 0; bina>0 ; i++) { ans = ans+(bina%2)*pow(10,i); bina = bina/2; } return ans; } const int q[6]={1,3,2,6,4,5}; //a桁目にbを追加したときに7の剰余がどれほど増えるかを返す ll seven(ll a,ll b){ a--; a%=6; return (q[a]*b)%7; } ll solve(ll a){ ll ans=0; ll tmp=sqrt(a*1.0); for(ll i=1;i<=tmp;i++){ ans+=a/i; } return ans*2-tmp*tmp; } ll solve2(ll a,ll b){ if(a==0){ return b*(b-1); } else{ return b*(b-1); } } ll solve3(ll a,ll b){ ll ans=b*(a-1); return ans; } int main(){ //ansはa|b,b|c型(a=2,b=4,c=12など) // ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(10); ll ans=0; ll a; cin>>a; ll tmp=sqrt(a*1.0); for(int i=1;i<=tmp;i++){ ans+=solve(a/i); ans+=((a/i)-(a/(i+1)))*solve(i); ans%=mod; } if(tmp*(tmp+1)>a){ ans-=solve(tmp); ans%=mod; } ans-=solve(a)*2; ans+=a; ans%=mod; while(ans<0){ ans+=mod; } // cout<a){ ll tmp2=solve2(a-1,tmp-1); tmp2%=mod; count-=tmp2; count%=mod; while(count<0){ count+=mod; } } // cout<a){ ll tmp2=solve3(a-1,tmp-1); tmp2%=mod; count2-=tmp2; count2%=mod; while(count2<0){ count2+=mod; } } //cout<