Background

You are right, but a certain four-character game is indeed fun.

Problem Description

You have a rooted tree with root $1$.

At node $i$, there is a non-negative integer $c_i$ and a positive integer $d_i$. You may perform the following operation any number of times:

• Choose a node $u$ such that $c_u$ is not a multiple of $d_u$. Then increase $c_i$ by $1$ for all nodes $i$ on the path from $u$ to the root (including both $u$ and the root).

After performing these operations, find the number of essentially different arrays $c$, modulo $998244353$.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers $c_i, d_i$.

The next $n - 1$ lines each contain two integers $u_i, v_i$, indicating an edge.

Output Format

Output a single integer, representing the number of essentially different arrays $c$ modulo $998244353$.

2
0 2
1 2
1 2

3

Hint

Let $m$ be the distance from the farthest node to the root.

Special Property A: It is guaranteed that for $2 \le i \le n$, the parent of node $i$ in the rooted tree is generated uniformly at random from $1 \sim i - 1$.

Constraints: For all testdata, $1 \le n \le 2000$, $0 \le c_i \le 10^9$, $1 \le d_i \le 10^9$.

Translated by ChatGPT 5