Counting Spanning Trees

题号：NC209434
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Bobo has a bipartite graph with (n + m) vertices $x_1, x_2, \dots, x_n$ and $y_1, y_2, \dots, y_m$ .
The vertex $x_i$ is connected to the first $a_i$ vertices in Y, namely $y_1, \dots, y_{a_i}$ .

Given n, m, $a_1, \dots, a_n$ and $\mathrm{mod}$ , find the number of spanning trees of the graph modulo $\mathrm{mod}$ .

输入描述:

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains three integers n, m and .
The second line contains n integers .

* 
* 
* 
* The sum of n does not exceed .

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

复制

2 1 1000000000
1 1
2 2 1000000000
2 2
3 3 1000000000
1 2 3

输出

复制

1
4
4