2107. 另一个计数问题 / Yet another counting problem

给定一个 n1n - 1 个点的无向图,点的编号为 2n2 \sim n。对于所有的 2u<vn2 \le u < v \le n,边 (u,v)(u, v) 存在当且仅当 vvuu 的正整数倍。定义 f(u,v)f(u, v) 表示 uuvv 是否连通:当 u,vu, v 连通时 f(u,v)=1f(u, v) = 1,否则 f(u,v)=0f(u, v) = 0。求:

(u=2n1v=u+1nf(u,v)uv)mod998244353\left(\sum_{u = 2} ^ {n - 1} \sum_{v = u + 1} ^ n f(u, v) \cdot u \cdot v\right) \bmod {998244353}

输入

输入一行一个正整数 nn。保证 4n10114 \le n \le 10 ^ {11}

输出

输出一行一个非负整数表示答案。

样例

标准输入 复制文本
4
标准输出 复制文本
8
标准输入 复制文本
6
标准输出 复制文本
80
标准输入 复制文本
127
标准输出 复制文本
23573971

提示

f(u,v)=1f(u, v) = 1 当且仅当 u=2,v=4u = 2, v = 4,故答案为 2×4=82 \times 4 = 8

所有满足 f(u,v)=1f(u, v) = 1(u,v)(u, v) 为:(2,3),(2,4),(2,6),(3,4),(3,6),(4,6)(2, 3), (2, 4), (2, 6), (3, 4), (3, 6), (4, 6)

登录以提交代码。
单点时限 2 秒
内存限制 512 MB
提交 1
通过 1