結果

問題 No.1276 3枚のカード
ユーザー ecotteaecottea
提出日時 2022-09-20 18:16:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 184 ms / 2,000 ms
コード長 18,713 bytes
コンパイル時間 4,505 ms
コンパイル使用メモリ 247,780 KB
実行使用メモリ 9,120 KB
最終ジャッジ日時 2023-08-23 19:37:40
合計ジャッジ時間 12,584 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 160 ms
8,264 KB
testcase_11 AC 83 ms
5,728 KB
testcase_12 AC 103 ms
6,016 KB
testcase_13 AC 107 ms
5,944 KB
testcase_14 AC 13 ms
4,380 KB
testcase_15 AC 88 ms
5,820 KB
testcase_16 AC 172 ms
8,040 KB
testcase_17 AC 100 ms
5,952 KB
testcase_18 AC 78 ms
5,824 KB
testcase_19 AC 120 ms
6,356 KB
testcase_20 AC 74 ms
5,660 KB
testcase_21 AC 77 ms
5,680 KB
testcase_22 AC 174 ms
8,344 KB
testcase_23 AC 13 ms
4,376 KB
testcase_24 AC 115 ms
5,936 KB
testcase_25 AC 45 ms
4,628 KB
testcase_26 AC 139 ms
8,500 KB
testcase_27 AC 155 ms
8,196 KB
testcase_28 AC 150 ms
8,596 KB
testcase_29 AC 92 ms
5,684 KB
testcase_30 AC 22 ms
4,380 KB
testcase_31 AC 12 ms
4,376 KB
testcase_32 AC 47 ms
4,604 KB
testcase_33 AC 5 ms
4,376 KB
testcase_34 AC 34 ms
4,508 KB
testcase_35 AC 32 ms
4,420 KB
testcase_36 AC 4 ms
4,380 KB
testcase_37 AC 30 ms
4,500 KB
testcase_38 AC 21 ms
4,380 KB
testcase_39 AC 48 ms
4,768 KB
testcase_40 AC 168 ms
8,200 KB
testcase_41 AC 142 ms
8,536 KB
testcase_42 AC 154 ms
7,928 KB
testcase_43 AC 137 ms
7,792 KB
testcase_44 AC 184 ms
8,432 KB
testcase_45 AC 168 ms
8,832 KB
testcase_46 AC 168 ms
8,924 KB
testcase_47 AC 143 ms
7,792 KB
testcase_48 AC 138 ms
8,536 KB
testcase_49 AC 152 ms
8,452 KB
testcase_50 AC 165 ms
8,660 KB
testcase_51 AC 147 ms
7,924 KB
testcase_52 AC 129 ms
7,852 KB
testcase_53 AC 147 ms
7,836 KB
testcase_54 AC 166 ms
8,124 KB
testcase_55 AC 134 ms
9,120 KB
testcase_56 AC 129 ms
8,924 KB
testcase_57 AC 160 ms
8,120 KB
testcase_58 AC 164 ms
8,200 KB
testcase_59 AC 148 ms
7,844 KB
testcase_60 AC 183 ms
8,340 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef HIDDEN_IN_VS // 折りたたみ用

// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS

// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;

// 型名の短縮
using ll = long long; // -2^63 ～ 2^63 = 9 * 10^18（int は -2^31 ～ 2^31 = 2 * 10^9）
using pii = pair<int, int>;	using pll = pair<ll, ll>;	using pil = pair<int, ll>;	using pli = pair<ll, 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 vb = vector<bool>;	using vvb = vector<vb>;		using vvvb = vector<vvb>;
using vc = vector<char>;	using vvc = vector<vc>;		using vvvc = vector<vvc>;
using vd = vector<double>;	using vvd = vector<vd>;		using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;

// 定数の定義
const double PI = acos(-1);
const vi DX = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
const vi DY = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004004004004004LL;
double EPS = 1e-12;

// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;

// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0; set < (1 << int(d)); ++set) // d ビット全探索（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了

// 汎用関数の定義
template <class T> inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）

// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }

// 手元環境（Visual Studio）
#ifdef _MSC_VER
#include "local.hpp"
// 提出用（gcc）
#else
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define gcd __gcd
#define dump(...)
#define dumpel(v)
#define dump_list(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) while (1) cout << "OLE"; }
#endif

#endif // 折りたたみ用


//--------------AtCoder 専用--------------
#include <atcoder/all>
using namespace atcoder;

using mint = modint1000000007;
//using mint = modint998244353;
//using mint = modint; // mint::set_mod(m);

istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>;
//----------------------------------------


// O(n^3)
mint naive(ll n) {
	mint res = 0;

	repi(a, 1, n) repi(b, 1, n) repi(c, 1, n) {
		if (b % a == 0 || a % b == 0 || c % b != 0 || b == c) continue;
		res++;
	}

	return res;
}


void zikken() {
	int N = 100;
	vm res(N + 1);
	repi(n, 1, N) {
		res[n] = naive(n);
	}
	dump_list(res);
	exit(0);
}
/*
{0, 0, 0, 0, 1, 2, 7, 10, 18, 27, 41, 49, 76, 88, 112, 142, 178, 197, 249, 272, 334, 385, 434, 465, 567, 620, 682, 753, 854, 900, 1044, 1096, 1214, 1310, 1400, 1508, 1709, 1778, 1883, 2002, 2214, 2293, 2518, 2603, 2787, 2993, 3130, 3225, 3544, 3683, 3904, 4076, 4305, 4419, 4724, 4924, 5253, 5453, 5639, 5771, 6278, 6420, 6622, 6939, 7278, 7527, 7924, 8085, 8405, 8658, 9099, 9272, 9904, 10087, 10342, 10732, 11100, 11413, 11898, 12099, 12720, 13094, 13386, 13600, 14365, 14717, 15027, 15367, 15940, 16176, 17015, 17405, 17872, 18244, 18590, 18990, 19878, 20146, 20663, 21220, 21959}
*/


//【素数の列挙】O(n log(log n))
/*
* n 以下の素数を列挙し，ps に昇順に格納する．
*/
void eratosthenes(int n, vi& ps) {
	// verify : https://algo-method.com/tasks/330

	ps.clear();

	// 素数かどうかを記録しておくためのテーブル
	vb is_prime(n + 1, true);
	is_prime[0] = is_prime[1] = false;

	int i = 2;

	// √n 以下の i の処理
	for (; i <= n / i; i++) {
		if (is_prime[i]) {
			ps.push_back(i);

			for (int j = i * i; j <= n; j += i) is_prime[j] = false;
		}
	}

	// √n より大きい i の処理
	for (; i <= n; i++) if (is_prime[i]) ps.push_back(i);
}


//【約数変換，LCM 畳込み】
/*
* Divisor_transform<T>(int n) : O(n log(log n))
*   n までの素数を持って初期化する．
*
* divisor_zeta(vT& a) : O(n log(log n))
*   A[j] = Σ_(i | j) a[i] なる A に上書きする．
*  （約数ゼータ変換，倍数への累積和）
*
* divisor_mobius(vT& A) : O(n log(log n))
*   A[j] = Σ_(i | j) a[i] なる a に上書きする．
*  （約数メビウス変換，約数への差分）
*
* vT lcm_convolution(vT a, vT b) : O(n log(log n))
*   c[k] = Σ_(lcm(i, j) = k) a[i] b[j] なる c を返す．
*   ただし c[n] を含めそれ以降は切り捨てる．
*
* 制約：1-indexed とし，a[0], b[0] は使用しない．
*
* 利用：【素数の列挙】
*/
template <typename T> struct Divisor_transform {
	// 参考 : https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5
	// verify : https://judge.yosupo.jp/problem/lcm_convolution

	vi ps; // 素数のリスト

	Divisor_transform() {}
	Divisor_transform(int n) { eratosthenes(n, ps); }

	void divisor_zeta(vector<T>& f) {
		// 具体例：
		//	A[1] = a[1]
		//	A[2] = a[1] + a[2]
		//	A[3] = a[1]        + a[3]
		//	A[4] = a[1] + a[2]        + a[4]
		//	A[5] = a[1]                      + a[5]
		//	A[6] = a[1] + a[2] + a[3]               + a[6]
		//	A[7] = a[1]                                    + a[7]
		//	A[8] = a[1] + a[2]        + a[4]                      + a[8]

		int n = sz(f);

		// 各素因数ごとに下からの累積和をとる
		repe(p, ps) {
			repi(i, 1, (n - 1) / p) f[p * i] += f[i];
		}
	}

	void divisor_mobius(vector<T>& f) {
		int n = sz(f);

		// 各素因数ごとに上からの差分をとる
		repe(p, ps) {
			repir(i, (n - 1) / p, 1) f[p * i] -= f[i];
		}
	}

	vector<T> lcm_convolution(vector<T> a, vector<T> b) {
		int n = sz(a);

		// 各素因数の max をとったものが lcm なので max 畳込みを行う．
		divisor_zeta(a); divisor_zeta(b);
		rep(i, n) a[i] *= b[i];
		divisor_mobius(a);
		return a;
	}
};


//【約数関数 σ_k(n)】O(n log(log n))
/*
* i = [1..n] について約数関数 σ_k(i) = (i の約数の k 乗和) を s[i] に格納する．
* 特に k = 0 なら約数の個数，k = 1 なら約数の総和と等価である．
*
* 利用：【約数変換，LCM 畳込み】
*/
template <class T> void divisor_sigma(int k, int n, vector<T>& s) {
	// 参考 : https://maspypy.com/%E6%95%B0%E5%AD%A6-%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF%E5%85%A5%E9%96%80%EF%BC%9Adirichlet%E7%A9%8D%E3%81%A8%E3%82%BC%E3%83%BC%E3%82%BF%E5%A4%89%E6%8F%9B%E3%83%BB%E3%83%A1%E3%83%93%E3%82%A6
	// verify : https://atcoder.jp/contests/arc068/tasks/arc068_c

	s.resize(n + 1);
	s[0] = 0;
	repi(i, 1, n) s[i] = T(pow(i, k));

	Divisor_transform<T> dt(n);
	dt.divisor_zeta(s);
}


// O(n log(log n))
mint TLE(ll n) {
	vm s;
	divisor_sigma(0, n, s);

	mint res = 0;
	repi(b, 1, n) {
		res += mint(n / b - 1) * (n - (n / b) + 1 - s[b]);
	}

	return res;
}


//【商列挙】O(√n)
/*
* i=[1..n] に対し，n/i の商が q となる i の範囲が [i1..i2) であることを
* {q, i1, i2} として q について降順に qi に格納する．
* 各範囲においては余りは公差 -q の等差数列を成す．
*/
void quotient_range(ll n, vector<tuple<ll, ll, ll>>& qi) {
	// verify : https://atcoder.jp/contests/abc230/tasks/abc230_e

	//【方法】
	// n/i の商が q となるような i の範囲を考える．条件を i について整理すると
	//		q = floor(n / i)
	//		⇔ q <= n / i < q + 1
	//		⇔ i q <= n < i(q + 1)
	//		⇔ n / (q + 1) < i <= n / q
	// となる．
	//
	// この幅が 1 以下であれば，q に対応する i は高々 1 個である．その条件は
	//		n / q - n / (q + 1) <= 1
	//		⇔ (q + 1)n - q n <= q(q + 1)
	//		⇔ n <= q(q + 1)
	// である．条件をやや弱めて
	//		n <= q^2
	//		⇔ √n <= q
	// としてもオーダーに影響はない．

	//（例）
	// 例えば n = 15 のときは以下のように分類できる：
	//		商 n/i	i の範囲		余り n%i
	//		15		[1..2)		[0]
	//		7		[2..3)		[1]
	//		5		[3..4)		[0]
	//		3		[4..6)		[3, 0]
	//		2		[6..8)		[3, 1]
	//		1		[8..16)		[7, 6, 5, 4, 3, 2, 1, 0]

	ll m = (ll)(sqrt(n) + EPS);

	// q に対応する i が高々 1 個の部分は i ごとに愚直に考える．
	for (int i = 1; n / i > m; i++) {
		qi.push_back({ n / i, i, i + 1 });
	}

	// そうでない部分は q ごとにまとめて考える．
	repir(q, m, 1) {
		ll i0 = n / (q + 1LL) + 1;
		ll i1 = n / q + 1;
		qi.push_back({ q, i0, i1 });
	}
}


void TLE2() {
	ll n0;
	cin >> n0;

	vector<tuple<ll, ll, ll>> qis;
	quotient_range(n0, qis);

	int m0 = (int)(sqrt(n0) + EPS);

	vm s_small;
	divisor_sigma(0, (int)1e6, s_small);

	// inv[i] : i の逆数
	vm inv(msb(n0) + 10);
	repi(i, 1, sz(inv) - 1) inv[i] = mint(i).inv();

	// 1 と素数の昇順リスト
	vl ps{ 1 };

	// cnt0_p[v] : [2..v] 内の p 以下の素数で篩い終えた後残っている数の個数
	// cnt1_p[v] : [2..n/v] 内の p 以下の素数で篩い終えた後残っている数の個数
	vl cnt0(m0 + 1), cnt1(m0 + 1);

	repi(v, 1, m0) {
		cnt0[v] = v - 1;
		cnt1[v] = n0 / v - 1;
	}

	repi(p, 2, m0) {
		ll c = cnt0[p - 1];

		// p が素数でなければ次の p へ
		if (cnt0[p] == c) continue;
		ps.push_back(p);

		// cnt1 の更新
		repi(v, 1, m0) {
			// p^2 > n/v なら更新不要
			if (p > n0 / v / p) break;

			if (v <= m0 / p) {
				cnt1[v] -= cnt1[v * p] - c;
			}
			else {
				cnt1[v] -= cnt0[n0 / v / p] - c;
			}
		}

		// cnt0 の更新
		repir(v, m0, 1) {
			// p^2 > v なら更新不要
			if (p > v / p) break;

			cnt0[v] -= cnt0[v / p] - c;
		}
	}

	mint res = 0; mint s1 = 0;

	repe(qi, qis) {
		ll q, i1, i2;
		tie(q, i1, i2) = qi;

		if (i2 - i1 == 1) {
			res += mint(q - 1) * (n0 - q + 1 - s_small[i1]);
			s1 += s_small[i1];
			//			dump(q, i1, i2, s1);
			continue;
		}

		ll n = i2 - 1;
		int m = (int)(sqrt(n) + EPS);

		mint s2 = 1;

		// s : 注目頂点, i_gpf : s の最大素因数が何番目の素数か, sg : σ_0(s), c : s の最大素因数の指数
		function<void(ll, int, mint, int)> dfs = [&](ll s, int i_gpf, mint sg, int c) {
			//			dump("dfs:", s, ps[i_gpf], sg, c);
			ll p = ps[i_gpf];

			// s の最小の子 s * p からの寄与を加算する．
			if (s != 1) s2 += sg * inv[c + 1] * (c + 2);

			// その他の s の子からの寄与をまとめて加算する．
			if (n / s <= m0) s2 += sg * ((2 * cnt0[n / s]) - (2 * cnt0[p]));
			else s2 += sg * ((2 * cnt1[n0 / n * s]) - (2 * cnt0[p]));

			// s の最小の子 s * p を探索する．
			if (s != 1 && s <= n / (p * p)) dfs(s * p, i_gpf, sg * inv[c + 1] * (c + 2), c + 1);

			// その他の s の子を探索する．
			for (int i = i_gpf + 1; i < sz(ps) && s <= n / (ps[i] * ps[i]); i++) {
				dfs(s * ps[i], i, sg * 2, 1);
			}
		};

		dfs(1, 0, 1, 0);

		res += mint(q - 1) * (mint(n0 - q + 1) * (i2 - i1) - (s2 - s1));
		//		dump(q, i1, i2, s1, s2);
		s1 = s2;
	}

	cout << res << endl;
}


void zikken2() {
	int N = 20;
	vm res(N + 1);
	repi(n, 1, N) {
		repi(a, 1, n) repi(b, 1, n) repi(c, 1, n) {
			if (b % a == 0 && c % b == 0) res[n]++;
		}
	}
	dump_list(res);
	exit(0);
}
/*
{0, 1, 4, 7, 13, 16, 25, 28, 38, 44, 53, 56, 74, 77, 86, 95, 110, 113, 131, 134, 152}

http://oeis.org/A061201
To compute a(n) for huge n (see A180365) in sublinear use
	a(n) = 3*Sum_{i=1..n3} A006218(n/i) - Sum_{j=1..n3} floor(n/(i*j)) + n3^3,
where n3 = floor(n^(1/3)). - Andrew Lelechenko, Apr 15 2011

http://oeis.org/A006218
a(n) = Sum_{k=1..n} floor(n/k); also Sum_{k=1..n} d(k), where d = number of divisors (A000005);
also number of solutions to x*y = z with 1 <= x,y,z <= n.
a(n) = 2*(Sum_{i=1..floor(sqrt(n))} floor(n/i)) - floor(sqrt(n))^2. - Benoit Cloitre, May 12 2002
*/


//【長さ 2 の倍数鎖の数え上げ】O(√n)
/*
* 1 <= x | y <= n を満たす組 (x, y) の個数を返す．
* 
* 利用：【商列挙】
*/
template<class T> T count_multiple_2chain(ll n) {
	// 参考：http://oeis.org/A006218

	//【方法】
	// x を固定すれば，条件を満たす y は n 以下の x の倍数全てなので，その個数は floor(n/x) である．
	// よって求めるべき値は
	//		Σx∈[1..n] floor(n/x)
	// である．
	// これは floor(n/x) の値が等しいところをまとめて計算することにより高速化できる．

	vector<tuple<ll, ll, ll>> qis;
	quotient_range(n, qis);

	T res = 0;

	repe(qi, qis) {
		ll q, i1, i2;
		tie(q, i1, i2) = qi;

		res += q * T(i2 - i1);
	}

	return res;
}


void check_count_multiple_2chain() {
	int N = 20;

	repi(n, 1, N) {
		ll res1 = 0;
		repi(a, 1, n) repi(b, 1, n) {
			if (b % a == 0) res1++;
		}
		
		ll res2 = count_multiple_2chain<ll>(n);

		dump(n, res1, res2);
	}

	exit(0);
}
/*
1 1 1
2 3 3
3 5 5
4 8 8
5 10 10
6 14 14
7 16 16
8 20 20
9 23 23
10 27 27
11 29 29
12 35 35
13 37 37
14 41 41
15 45 45
16 50 50
17 52 52
18 58 58
19 60 60
20 66 66
*/


//【めぐる式二分探索】O(log|ok - ng|)
/*
* 条件 okQ() を満たす要素 ok と満たさない要素 ng との境界を二分探索する．
* 境界に隣り合うような条件を満たす要素（ok 側）の位置を返す．
*/
template <typename T> T meguru_search(T ok, T ng, function<bool(T)>& okQ) {
	// 参考 : https://twitter.com/meguru_comp/status/697008509376835584
	// verify : https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_4_D

	// 境界が決定するまで
	while (abs(ok - ng) > 1) {
		// 区間の中間
		T mid = (ok + ng) / 2;

		// 中間が OK かどうかに応じて区間を縮小する．
		if (okQ(mid)) ok = mid;
		else ng = mid;
	}
	return ok;

	/* okQ の定義の雛形
	function<bool(ll)> okQ = [&](ll x) {
		return true || false;
	};
	*/
}


//【整数累乗根】O(n log a)
/*
* 非負の数 a の n 乗根（a^(1/n)）の切り捨て値を返す．
*
* 利用：【めぐる式二分探索】
*/
ll integer_root(ll a, int n) {
	// verify : https://atcoder.jp/contests/abc166/tasks/abc166_d

	if (a <= 1 || n == 1) return a;

	// x^k を返す．ただし a を超えた場合は a + 1 を返す．
	auto pow = [&](ll x, int k) {
		ll v = 1;
		rep(i, k) {
			if (v > a / x) return a + 1;
			v *= x;
		}
		return v;
	};

	// x^n <= a かを返す．
	function<bool(ll)> okQ = [&](ll x) {
		return pow(x, n) <= a;
	};

	ll res = meguru_search(1LL, a + 1, okQ);

	return res;
}


//【長さ 3 の倍数鎖の数え上げ】O(n^(2/3)) ?
/*
* 1 <= x | y | z <= n を満たす組 (x, y, z) の個数を返す．
*
* 利用：【整数累乗根】,【長さ 2 の倍数鎖の数え上げ】
*/
template<class T> T count_multiple_3chain(ll n) {
	// 参考：http://oeis.org/A061201

	int m = (int)integer_root(n, 3);

	T res = T(m) * m * m;

	repi(i, 1, m) {
		res += 3 * count_multiple_2chain<T>(n / i);
		repi(j, 1, m) {
			res -= 3 * (n / ((ll)i * j));
		}
	}

	return res;
}


void check_count_multiple_3chain() {
	int N = 20;

	repi(n, 1, N) {
		ll res1 = 0;
		repi(a, 1, n) repi(b, 1, n) repi(c, 1, n) {
			if (b % a == 0 && c % b == 0) res1++;
		}

		ll res2 = count_multiple_3chain<ll>(n);

		dump(n, res1, res2);
	}

	exit(0);
}
/*
1 1 1
2 4 4
3 7 7
4 13 13
5 16 16
6 25 25
7 28 28
8 38 38
9 44 44
10 53 53
11 56 56
12 74 74
13 77 77
14 86 86
15 95 95
16 110 110
17 113 113
18 131 131
19 134 134
20 152 152
*/


template<class T> T count_multiple_2Vchain(ll n) {
	vector<tuple<ll, ll, ll>> qis;
	quotient_range(n, qis);

	T res = 0;

	repe(qi, qis) {
		ll q, i1, i2;
		tie(q, i1, i2) = qi;

		res += T(q) * T(q) * T(i2 - i1);
	}

	return res;
}


void check_count_multiple_2Vchain() {
	int N = 20;

	repi(n, 1, N) {
		ll res1 = 0;
		repi(a, 1, n) repi(b, 1, n) repi(c, 1, n) {
			if (a % b == 0 && c % b == 0) res1++;
		}

		ll res2 = count_multiple_2Vchain<ll>(n);

		dump(n, res1, res2);
	}

	exit(0);
}
/*
1 1 1
2 5 5
3 11 11
4 22 22
5 32 32
6 52 52
7 66 66
8 92 92
9 115 115
10 147 147
11 169 169
12 219 219
13 245 245
14 289 289
15 333 333
16 390 390
17 424 424
18 496 496
19 534 534
20 612 612
*/


int main() {
//	input_from_file("input.txt");
//	output_to_file("output.txt");
	
	ll n;
	cin >> n;

	mint c2 = count_multiple_2chain<mint>(n);
	mint c2V = count_multiple_2Vchain<mint>(n);
	mint c3 = count_multiple_3chain<mint>(n);

	mint cnt1111 = n;
	mint cnt1110 = c2 - cnt1111;
	mint cnt1011 = cnt1110;
	mint cnt0111 = cnt1110;
	mint cnt0011 = mint(n) * n - (cnt1111 + cnt1011 + cnt0111);
	mint cnt0110 = c2V - (cnt1111 + cnt0111+ cnt1110);
	mint cnt1010 = c3 - (cnt1111 + cnt1011 + cnt1110);
	mint cnt0010 = n * c2 - (cnt1111 + cnt1110 + cnt1011 + cnt0111 + cnt0011 + cnt0110 + cnt1010);

	cout << cnt0010 << endl;
}
0