Description

\(3030\) 年, Macsy 正在火星部署一批机器人.

第 \(1\) 秒, 他把机器人 \(1\) 号运到了火星, 机器人 \(1\) 号可以制造其他的机器人.

第 \(2\) 秒, 机器人 \(1\) 号造出了第一个机器人----机器人 \(2\) 号.

第 \(3\) 秒, 机器人 \(1\) 号造出了另一个机器人----机器人 \(3\) 号.

之后每一秒, 机器人 \(1\) 号都可以造出一个新的机器人. 第 \(m\) 秒造出的机器人编号为 \(m\). 我们可以称它为机器人 \(m\) 号, 或者 \(m\) 号机器人.

机器人造出来后, 马上开始工作.\(m\) 号机器人, 每 \(m\) 秒会休息一次. 比如 \(3\) 号机器人, 会在第 \(6, 9, 12, \ldots\) 秒休息, 而其它时间都在工作.

机器人休息时, 它的记忆将会被移植到当时出生的机器人的脑中. 比如 \(6\) 号机器人出生时,\(2, 3\) 号机器人正在休息, 因此,\(6\) 号机器人会收到第 \(2, 3\) 号机器人的记忆副本. 我们称第 \(2, 3\) 号机器人是 \(6\) 号机器人的老师.

如果两个机器人没有师徒关系, 且没有共同的老师, 则称这两个机器人的知识是互相独立的. 注意:\(1\) 号机器人与其他所有机器人的知识独立 (因为只有 \(1\) 号才会造机器人), 它也不是任何机器人的老师.

一个机器人的独立数, 是指所有编号比它小且与它知识互相独立的机器人的个数. 比如 \(1\) 号机器人的独立数为 \(0\),\(2\) 号机器人的独立数为 \(1\) (\(1\) 号机器人与它知识互相独立),\(6\) 号机器人的独立数为 \(2\) (\(1, 5\) 号机器人与它知识互相独立,\(2, 3\) 号机器人都是它的老师, 而 \(4\) 号机器人与它有共同的老师----\(2\) 号机器人).

新造出来的机器人有 \(3\) 种不同的职业. 对于编号为 \(m\) 的机器人, 如果能把 \(m\) 分解成偶数个不同奇素数的积, 则它是政客, 例如编号 \(15\); 否则, 如果 \(m\) 本身就是奇素数或者能把 \(m\) 分解成奇数个不同奇素数的积, 则它是军人, 例如编号 \(3\), 编号 \(165\). 其它编号的机器人都是学者, 例如编号 \(2\), 编号 \(6\), 编号 \(9\).

第 \(m\) 秒诞生的机器人 \(m\) 号, 想知道它和它的老师中, 所有政客的独立数之和, 所有军人的独立数之和, 以及所有学者的独立数之和. 可机器人 \(m\) 号忙于工作没时间计算, 你能够帮助它吗?

为了方便你的计算, Macsy 已经帮你做了 \(m\) 的素因子分解. 为了输出方便, 只要求输出总和除以 \(10000\) 的余数.

Input

第一行是一个正整数 \(k (1 \leq k \leq 1000)\),\(k\) 是 \(m\) 的不同的素因子个数.

以下 \(k\) 行, 每行两个整数,\(p_i, e_i\), 表示 \(m\) 的第 \(i\) 个素因子和它的指数.\(p_1, p_2, \ldots, p_k\) 是不同的素数,\(m = \prod_{i=1}^{k} p_i^{e_i}\). 所有素因子按照从小到大排列, 即 \(p_1 \lt p_2 \lt \ldots \lt p_k\). 输入文件中,\(2 \leq p_i \lt 10000, 1 \leq e_i \leq 10^6\).

Output

输出包括三行.

第一行是机器人 \(m\) 号和它的老师中, 所有政客的独立数之和除以 \(10000\) 的余数.

第二行是机器人 \(m\) 号和它的老师中, 所有军人的独立数之和除以 \(10000\) 的余数.

第三行是机器人 \(m\) 号和它的老师中, 所有学者的独立数之和除以 \(10000\) 的余数.

Sample Input

3
2 1
3 2
5 1

Sample Output

8
6
75

Explanation

花了一个题目的篇幅介绍了莫比乌斯函数......\[ \mu(n) = \begin{cases} 1 & n = 1\\ (-1)^k & n = p_1 p_2 p_3 \ldots p_k\\ 0 & else \end{cases} \] 题目要求的三个式子分别是:\[ \begin{cases} \sum_{i=1}^{n} \varphi(i) & \mu(i) = 1\\ \sum_{i=1}^{n} \varphi(i) & \mu(i) = 0\\ \sum_{i=1}^{n} \varphi(i) & \mu(i) = -1 \end{cases} \] 虽然 \(n\) 很大...... 所以不要试图暴力...... 线性筛也不是办法

盛翊伦大神给了一个解法, 但我没有记住, 这个坑之后得回来填上

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 1010;
const lli modr = 10000;

lli qpow(lli a, lli b) {
    lli c = 1;
    for (; b > 0; b >>= 1, a = a * a % modr)
        if (b & 1)
            c = c * a % modr;
    return c;
}

struct prime {
    lli p, a;
} arr[maxn];

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &arr[i].p, &arr[i].a);
    // What the ....?
    lli res_1 = 0, res_2 = 0, res_3 = 1;
    for (int i = 1; i <= n; i++) {
        res_3 = res_3 * qpow(arr[i].p, arr[i].a) % modr;
        if (arr[i].p == 2)
            continue;
        lli tmp1 = (res_1 + res_2 * (arr[i].p - 1)) % modr,
            tmp2 = (res_2 + (res_1 + 1) * (arr[i].p - 1)) % modr;
        res_1 = tmp1, res_2 = tmp2;
    }
    res_3 = (res_3 - 1 - res_1 - res_2 + 3 * modr) % modr;
    // That seemed magic.
    printf("%lld\n%lld\n%lld\n", res_1, res_2, res_3);
    return 0;
}