有一棵有根的圣诞树，叶子节点都在第 d 层，其中第 i 层的每个节点都有 a_i 棵子节点。
BTJ 觉得这棵树太大了，要从中选出若干个节点，每个节点都在同一颗树里即在同一个连通块中，其他的都砍掉。
有 n 种颜料，假定每种颜料都有无穷桶。每个选中的节点都要染色，但两个直接连接的节点不能染相同的颜色。
第一行两个整数 d,n。
第二行 d-1 个整数 a_i。
一行一个整数，表示方案数。由于可能很大，对 10^9+7 取模。
4 2 2 3 1
1712
3 3 2 2
1640
d \le 10^5,n \le 10^5,a_i \le 10^9
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |