×

# 计蒜客

1. 题库
2. Tree
3. 问答
• 14.27%
• 262144K

There is a tree with $n$ nodes, at which attach a binary $64*64$ matrix $M_i (1 \le i \le n)$. There are $q$ queries for matrix multiplication on the path from node $a$ to node $b$ modulo $2$. To avoid massive input dataset, $M_i(1\le i \le n)$ is attained by the following algorithm:

Input a random $seed$ (unsigned long long)

for(int i = 1; i <= n; ++i) {
for(int p = 1; p <= 64; ++p) {
seed ^= seed * seed + 15;
for(int q = 1; q <= 64; ++q) {
M[i][p][q] = (seed >> (q - 1)) & 1;
}
}
}

To avoid massive output, you should output$$\displaystyle (\displaystyle \sum_{i=1}^{64} \sum_{j=1}^{64} M_{ij}*19^i*26^j) \mod 19260817$$

### Input Format

There are multi datasets. $(\sum n \le 3000, \sum q \le 30000)$.

For each dataset:

In the first $n-1$ lines, there are to integers $u,v$, indicates there is an edge connects node $u$ and node $v$.$(1\le u,v \le n)$.

In the next line there is an integer $seed(0 \le seed < 2^{64})$.

In the next $q$ lines, there is to integers $a,b$, indicates a query on path from node $a$ to node $b$.$(1 \le a,b \le n)$.

### Output Format

For each query, output an integer in one line without any additional space.

#### 样例输入

6 5
4 1
3 4
6 4
5 3
2 3
19260817
4 5
5 6
4 4
2 1
2 2

#### 样例输出

4855239
2667906
277543
14478924
1173682

• main.c