#P4916. 神犇和蒟蒻

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

神犇和蒟蒻

题目描述

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

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

输入格式

请你读入一个整数N;

1<=N<=1E9

求A、B模1E9+7;

输出格式

请你输出一个整数A=\sum_{i=1}^N{\mu (i^2)};

请你输出一个整数B=\sum_{i=1}^N{\varphi (i^2)};

样例

样例输入

1

样例输出

1
1