#P5746. [NOI2002] 机器人M号

[NOI2002] 机器人M号

题目描述

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

11 秒,他把机器人 11 号运到了火星,机器人 11 号可以制造其他的机器人。

22 秒,机器人 11 号造出了第一个机器人——机器人 22 号。

33 秒,机器人 11 号造出了另一个机器人——机器人 33 号。

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

机器人造出来后,马上开始工作。mm 号机器人,每 mm 秒会休息一次。比如 33 号机器人,会在第 66991212\ldots 秒休息,而其它时间都在工作。

机器人休息时,它的记忆将会被移植到当时出生的机器人的脑中。比如 66 号机器人出生时,2233 号机器人正在休息,因此,66 号机器人会收到第 2233 号机器人的记忆副本。我们称第 2233 号机器人是 66 号机器人的老师。

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

一个机器人的独立数,是指所有编号比它小且与它知识互相独立的机器人的个数。比如 11 号机器人的独立数为 0022 号机器人的独立数为 1111 号机器人与它知识互相独立),66 号机器人的独立数为 221155 号机器人与它知识互相独立,2233 号机器人都是它的老师,而 44 号机器人与它有共同的老师——22 号机器人)。

新造出来的机器人有 33 种不同的职业。对于编号为 mm 的机器人,如果能把 mm 分解成偶数个不同奇素数的积,则它是政客,例如编号 1515;否则,如果 mm 本身就是奇素数或者能把 mm 分解成奇数个不同奇素数的积,则它是军人,例如编号 33,编号 165165。其它编号的机器人都是学者,例如编号 22, 编号 66, 编号 99

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

为了方便你的计算,Macsy 已经帮你做了 mm 的素因子分解。为了输出方便,只要求输出总和除以 1000010000 的余数。

输入格式

输入的第一行是一个正整数 kkkkmm 的不同的素因子个数。

以下 kk 行,每行两个整数,pip_i, eie_i,表示 mm 的第 ii 个素因子和它的指数 (i=1,2,,k)(i=1,2,\ldots,k)p1,p2,,pkp_1,p_2,\ldots,p_k 是不同的素数,i=1kpiei\prod_{i=1}^kp_i^{e_i}。所有素因子按照从小到大排列,即 p1<p2<<pkp_1<p_2<\ldots<p_k

输出格式

输出包括三行。

  • 第一行是机器人 mm 号和它的老师中,所有政客的独立数之和除以 1000010000 的余数。
  • 第二行是机器人 mm 号和它的老师中,所有军人的独立数之和除以 1000010000 的余数。
  • 第三行是机器人 mm 号和它的老师中,所有学者的独立数之和除以 1000010000 的余数。
3
2 1
3 2
5 1
8
6
75

提示

样例解释

m=2×32×5=90m = 2\times 3^2\times 5=909090 号机器人有 1010 个老师,加上它自己共 1111 个。其中政客只有 1515 号;军人有 33 号和 55 号;学者有 88 个,它们的编号分别是:2,6,9,10,18,30,45,902,6,9,10,18,30,45,90

数据范围

对于全部的数据,1k10001\le k\le 10002pi<10,0002\le p_i<10,0001ei1,000,0001\le e_i\le 1,000,000

评分规则

你在一个测试点的得分与你正确解决的问题数 xx 有关。

请注意:对每一行,即使不会解决该问题,也请在该行输出一个数字,否则 checker 将无法正确评分。

xx 得分
3 10
2 7
1 4
0