QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB
[-7]

# 8761. 另一个计数问题

Statistics

题目描述

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

(n1u=2nv=u+1f(u,v)uv)mod

输入格式

从标准输入读入数据。

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

输出格式

输出到标准输出。

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

样例

输入

4

输出

8

解释

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

样例

输入

6

输出

80

解释

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

样例

输入

127

输出

23573971