[NOI2002]机器人M号

题目描述

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$ 的余数。

输入输出格式

输入格式


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

输出格式


输出包括三行。 - 第一行是机器人 $m$ 号和它的老师中,所有政客的独立数之和除以 $10000$ 的余数。 - 第二行是机器人 $m$ 号和它的老师中,所有军人的独立数之和除以 $10000$ 的余数。 - 第三行是机器人 $m$ 号和它的老师中,所有学者的独立数之和除以 $10000$ 的余数。

输入输出样例

输入样例 #1

3
2 1
3 2
5 1

输出样例 #1

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$。 #### 数据范围 对于全部的数据,$1\le k\le 1000$,$2\le p_i<10,000$,$1\le e_i\le 1,000,000$。 #### 评分规则 你在一个测试点的得分与你正确解决的问题数 $x$ 有关。 请注意:**对每一行,即使不会解决该问题,也请在该行输出一个数字,否则 checker 将无法正确评分。** | $x$ | 得分 | | :--: | :--: | | 3 | 10 | | 2 | 7 | | 1 | 4 | | 0 | 0 |