[NOI2002Day2-C]机器人M号

内存限制：256 MB 时间限制：2000 ms

3030年，Macsy正在火星部署一批机器人。

第1秒，他把机器人1号运到了火星，机器人1号可以制造其他的机器人。

第2秒，机器人1号造出了第一个机器人——机器人2号。

第3秒，机器人1号造出了另一个机器人——机器人3号。

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

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

机器人休息时，它的记忆将会被移植到当时出生的机器人的脑中。比如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的余数。

第一行是一个正整数$k(1 \le k \le 1000)$，$k$是$m$的不同的素因子个数。

以下$k$行，每行两个整数，$p_i, e_i$，表示$m$的第$i$个素因子和它的指数$(i = 1, 2, …, k)$。$p_1, p_2, …, p_k$是不同的素数，$m=\prod_{i=1}^k p_i^{e_i}$。所有素因子按照从小到大排列，即$p_1<p_2<…<p_k$。

输入中，$2 \le p_i<10,000, 1 \le e_i \le 1,000,000$。

包括三行。

第一行是机器人m号和它的老师中，所有政客的独立数之和除以10000的余数。

第二行是机器人m号和它的老师中，所有军人的独立数之和除以10000的余数。

第三行是机器人m号和它的老师中，所有学者的独立数之和除以10000的余数。

8
6
75

【样例说明】

$m=2 \times 3^2 \times 5=90$。90号机器人有10个老师，加上它自己共11个。其中政客只有15号；军人有3号和5号；学者有8个，它们的编号分别是：2,6,9,10,18,30,45,90。

【评分标准】（comet 暂不支持部分分）

输出包含三个数。如果你的程序算对了三个数，该测试点得10分；如果你的程序算对了两个数，该测试点得7分；如果你的程序算对了一个数，该测试点得4分；如果你的程序一个数也没算对，该测试点得0分。

C0301 [NOI2002Day2-C]机器人M号