题目描述
给定长为 $n$ 的序列 $p_1, p_2, \cdots , p_n$，构造一个包含 $p_1 ×p_2 ×\cdots×p_n$ 个点的有向图，对于点 $X = (x_1, x_2, \cdots , x_n)$, $1 ≤ x_i ≤ p_i$ 和点 $Y = (y_1, y_2, \cdots , y_n)$, $1 ≤ y_i ≤ p_i$，若 $x_i ≤ y_i$ 且 $(y_1 − x_1) + (y_2 − x_2) + \cdots + (y_n − x_n) = 1$，则存在一条由 $X$ 至 $Y$ 的有向边。
选择尽量少的路径，使得所有 $p_1 × p_2 × \cdots × p_n$ 个点都被经过至少一次，这里路径是点的序列 $S_1, S_2, \cdots ,S_k$ 满足对于 $1 ≤ i < k$，存在一条由 $S_i$ 至 $S_{i+1}$ 的有向边。
由于所需的路径数可能很大，你只需要输出最少需要的路径数除以 $10^9 + 7$ 的余数。
输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数，第 $i$ 个整数表示 $p_i$。
输出格式
一行一个整数，表示答案除以 $10^9 + 7$ 的余数。
样例 1 输入
1 3
2 4 3 3样例 1 输出
1 8样例 2,3
数据范围
保证 $1 ≤ n ≤ 40, 1 ≤ p_i ≤ 10^9$。
子任务 $1$（$15$ 分）：$n ≤ 2$。
子任务 $2$（$10$ 分）：$n ≤ 16$。
子任务 $3$（$20$ 分）：$n ≤ 24$。
子任务 $4$（$35$ 分）：$n ≤ 32$。
子任务 $5$（$20$ 分）：无特殊限制。