#P9593. 神犇和蒟蒻

    ID: 6212 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-杜教筛狄利克雷卷积整除分块线性筛欧拉函数莫比乌斯函数记忆化搜索交换求和顺序等差数列求和模逆元

神犇和蒟蒻

题目背景

很久很久以前,有一只神犇叫 yzy。

很久很久之后,有一只蒟蒻叫 lty。

题目描述

求 ∑i=1Nμ(i2)\sum_{i=1}^N{\mu (i^2)} 与 ∑i=1Nφ(i2)\sum_{i=1}^N{\varphi (i^2)} 模 109+710^9+7 的值。

输入格式

仅一个整数 nn。

输出格式

输出两个数,分别表示 ∑i=1Nμ(i2)\sum_{i=1}^N{\mu (i^2)} 与 ∑i=1Nφ(i2)\sum_{i=1}^N{\varphi (i^2)}。

样例

1
1
1

数据范围

对于全部数据,保证 1≤n≤1091\le n\le 10^9。