Florin 又来到了 Drobeta-Turnu Severin。不幸的是，他还是没能甩掉那些让他烦恼不已的扒手！他们甚至跟到了这座美丽的城市！但 Florin 非常聪明，他想出了摆脱他们的方法。Drobeta-Turnu Severin 这座城市可以用一个包含 $n$ 个顶点和 $m$ 条边的有向无环图来表示。为了最终甩掉那些讨厌的扒手，Florin（最初位于顶点 $1$）必须沿着某条路径到达顶点 $n$。他设法获得了一个包含 $p$ 个顶点的列表。在从顶点 $1$ 到顶点 $n$ 的过程中，他必须按给定的顺序经过这 $p$ 个节点，否则他将无法甩掉扒手，我们的英雄也会非常难过。
题目描述
求出从顶点 $1$ 到顶点 $n$ 且按给定顺序经过列表中所有 $p$ 个顶点的路径数量。由于结果可能非常大，你需要将答案对 $1.000.000.007$ 取模。
输入格式
第一行包含三个整数 $n, m$ 和 $p$。 第二行包含 Florin 必须按给定顺序经过的 $p$ 个顶点。 接下来的 $m$ 行包含图中的边，每行由两个整数 $x$ 和 $y$ 表示，意味着存在一条从顶点 $x$ 到顶点 $y$ 的有向边。
输出格式
第一行仅包含一个整数，表示路径数量对 $1.000.000.007$ 取模后的结果。
子任务
- 警告！！！两个顶点之间可能存在多条边！！！！
- 警告！！！可以观察到，在子任务 3 中，$m$ 比其他子任务中的要大。
- 你必须将答案对 $1.000.000.007$ 取模。
- 我们给这道题起名为 SHELL 并没有什么特别好的理由。
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 10 分 | $n \le 20, m \le 190, p \le 11$ |
| 2 | 45 分 | $n \le 1000, m \le 30000, p \le 1000$ |
| 3 | 20 分 | $n \le 1500, p \le 1500$，且对于任意 $x < y$，从顶点 $x$ 到顶点 $y$ 只有唯一的一条边，除此之外没有其他边 |
| 4 | 25 分 | $n, m, p \le 1.000.000$ |
样例
输入 1
6 9 3 3 5 6 1 3 1 3 1 2 2 3 2 4 3 4 3 5 4 5 5 6
输出 1
6
说明
这 6 条路径分别是： 1-3-5-6 1-3-4-5-6 1-3-5-6 1-3-4-5-6 1-2-3-5-6 1-2-3-4-5-6
可以观察到 1-3-4-5-6 出现了 2 次，这是因为从 1 到 3 有 2 条边。其中一条路径使用第一条边，另一条路径使用第二条边。1-3-5-6 的情况也是如此。
