有一棵有根的圣诞树，叶子节点都在第 $d$ 层，其中第 $i$ 层的每个节点都有 $a_i$ 棵子节点。

BTJ 觉得这棵树太大了，要从中选出若干个节点，每个节点都在同一颗树里即在同一个连通块中，其他的都砍掉。

有 $n$ 种颜料，假定每种颜料都有无穷桶。每个选中的节点都要染色，但两个直接连接的节点不能染相同的颜色。

第一行两个整数 $d,n$。

第二行 $d-1$ 个整数 $a_i$。

一行一个整数，表示方案数。由于可能很大，对 $10^9+7$ 取模。

$d \le 10^5,n \le 10^5,a_i \le 10^9$