题目描述

给定一棵以 $1$ 为根的树，共有 $N$ 个节点。每个节点都有一个 $1$ 到 $M$ 之间的自然数作为权值，但有些节点的权值尚未确定。

对于每个节点，Ana 会写下从根节点到该节点路径上所有节点权值组成的序列，顺序为从根到该节点。这样一共得到 $N$ 个序列，然后将这 $N$ 个序列按字典序排序。

现在给定一个长度为 $K$ 的序列

其中每个 $S_i$ 也在 $1$ 到 $M$ 之间。Portocal 会从排序后的第一个序列开始每天检查一个序列，直到找到一个等于 $S$ 的序列。

Portocal 可以在 Ana 写序列之前，为所有尚未确定权值的节点赋值，赋值也必须在 $1$ 到 $M$ 之间。他希望尽可能早地找到序列 $S$。

需要回答以下两个问题之一：

1. Portocal 最少需要多少天才能找到序列 $S$；
2. 有多少种给缺失权值赋值的方式，可以达到这个最少天数。答案对 $1000000009$ 取模。

题目保证至少存在一种赋值方式，使得某个根到节点路径序列等于 $S$。

输入格式

第一行输入一个整数 $C$：

• 若 $C=1$，要求回答第一个问题；
• 若 $C=2$，要求回答第二个问题。

第二行输入三个整数 $N,M,K$。

第三行输入 $N$ 个整数 $val_1,val_2,\ldots,val_N$，表示节点权值。若 $val_i=-1$，表示节点 $i$ 尚未确定权值。

第四行输入 $K$ 个整数，表示序列 $S$。

接下来 $N-1$ 行，每行输入两个整数 $u,v$，表示树上的一条边。

输出格式

输出一个整数，表示根据 $C$ 的值对应的答案。

数据范围与约束

• $C\in\{1,2\}$；
• $1\le K\le N\le 500000$；
• $1\le M\le 500000$；
• 对所有 $1\le i\le N$，$1\le val_i\le M$ 或 $val_i=-1$；
• 对所有 $1\le i\le K$，$1\le S_i\le M$。

子任务

样例 1

输入

1
8 3 3
-1 -1 2 -1 -1 -1 1 2
1 2 2
1 2
2 3
2 4
4 5
1 6
6 7
1 8

输出

4

解释

一种最优赋值为：

1 2 2 2 1 3 1 2

此时按字典序最靠前的几个序列为：

1       对应节点 1
1 2     对应节点 2
1 2     对应节点 8
1 2 2   对应节点 3，等于 S

因此最少第 $4$ 天找到 $S$。

注意，虽然节点 $4$ 对应的序列也等于 $S$，但 Portocal 会在找到第一个等于 $S$ 的序列时停止。

样例 2

输入

2
8 3 3
-1 -1 2 -1 -1 -1 1 2
1 2 2
1 2
2 3
2 4
4 5
1 6
6 7
1 8

输出

6

解释

共有 $6$ 种赋值方式可以让 Portocal 在第 $4$ 天找到序列 $S$：

1 2 2 2 1 3 1 2
1 2 2 3 1 3 1 2
1 2 2 2 2 3 1 2
1 2 2 3 2 3 1 2
1 2 2 2 3 3 1 2
1 2 2 3 3 3 1 2