Description

In the year 3030, Macsy is deploying a batch of robots on Mars.

At the $1$st second, he shipped robot No. $1$ to Mars. Robot No. $1$ can manufacture other robots.

At the $2$nd second, robot No. $1$ built the first robot—robot No. $2$.

At the $3$rd second, robot No. $1$ built another robot—robot No. $3$.

After that, every second, robot No. $1$ can build one new robot. The robot built at the $m$-th second has index $m$. We call it robot No. $m$, or the $m$-th robot.

After a robot is built, it starts working immediately. Robot No. $m$ rests once every $m$ seconds. For example, robot No. $3$ rests at the $6$th, $9$th, $12$th, $\ldots$ seconds, and works at all other times.

When a robot rests, its memory will be transplanted into the brain of the robot born at that moment. For example, when robot No. $6$ is born, robots No. $2$ and No. $3$ are resting, so robot No. $6$ receives copies of the memories of robots No. $2$ and No. $3$. We call robots No. $2$ and No. $3$ the teachers of robot No. $6$.

If two robots do not have a teacher-student relationship, and they do not share any common teacher, then we say the knowledge of these two robots is mutually independent. Note: the knowledge of robot No. $1$ is independent of all other robots (because only robot No. $1$ builds robots), and it is not any robot’s teacher.

The independence number of a robot is the number of robots with smaller indices whose knowledge is mutually independent from it. For example, the independence number of robot No. $1$ is $0$; the independence number of robot No. $2$ is $1$ (robot No. $1$ is mutually independent from it); the independence number of robot No. $6$ is $2$ (robots No. $1$ and No. $5$ are mutually independent from it; robots No. $2$ and No. $3$ are its teachers; and robot No. $4$ shares a common teacher—robot No. $2$—with it).

Newly built robots have $3$ different professions. For a robot with index $m$, if $m$ can be factored into a product of an even number of distinct odd primes, then it is a politician, for example index $15$; otherwise, if $m$ itself is an odd prime, or $m$ can be factored into a product of an odd number of distinct odd primes, then it is a soldier, for example index $3$ and index $165$. Robots with other indices are scholars, for example index $2$, index $6$, and index $9$.

Robot No. $m$, born at the $m$-th second, wants to know: among itself and its teachers, the sum of the independence numbers of all politicians, the sum of the independence numbers of all soldiers, and the sum of the independence numbers of all scholars. But robot No. $m$ is busy working and has no time to compute. Can you help it?

To make computation easier, Macsy has already factored $m$ into primes for you. To make output easier, you only need to output the remainder after dividing each sum by $10000$.

Input Format

The first line contains a positive integer $k$, where $k$ is the number of distinct prime factors of $m$.

The next $k$ lines each contain two integers $p_i$, $e_i$, representing the $i$-th prime factor of $m$ and its exponent $(i=1,2,\ldots,k)$. $p_1,p_2,\ldots,p_k$ are distinct primes, and $m=\prod_{i=1}^k p_i^{e_i}$. All prime factors are given in increasing order, i.e. $p_1<p_2<\ldots<p_k$.

Output Format

Output consists of three lines.

• The first line is the remainder after dividing by $10000$ the sum of the independence numbers of all politicians among robot No. $m$ and its teachers.
• The second line is the remainder after dividing by $10000$ the sum of the independence numbers of all soldiers among robot No. $m$ and its teachers.
• The third line is the remainder after dividing by $10000$ the sum of the independence numbers of all scholars among robot No. $m$ and its teachers.

3
2 1
3 2
5 1

8
6
75

Hint

Sample Explanation

$m = 2\times 3^2\times 5=90$. Robot No. $90$ has $10$ teachers; together with itself there are $11$ robots. Among them, the only politician is robot No. $15$; the soldiers are robot No. $3$ and robot No. $5$; there are $8$ scholars, with indices: $2,6,9,10,18,30,45,90$.

Constraints

For all testdata, $1\le k\le 1000$, $2\le p_i<10,000$, $1\le e_i\le 1,000,000$.

Scoring Rules

Your score on a test point depends on the number of subproblems you solve correctly, denoted by $x$.

Please note: for each line, even if you cannot solve that part, you must still output a number on that line; otherwise the checker cannot score correctly.

Translated by ChatGPT 5