日が暮れてる 年も暮れてる 途方に暮れちゃってる
黄昏降临，岁暮到来，路途变得一片迷茫
有一张 nnn 个节点组成的无向图，点从 111 至 nnn 编号，图中没有重边和自环。我们不知道它的确切形态，但是它满足以下条件：
- 由任一节点至节点 111 的最短路径（经过边数最少的路径）存在且唯一；
- 令 ℓi\ell_iℓi 表示由节点 iii 至节点 111 的最短路径上边的数目，那么对于所有 2≤i≤n2 \leq i \leq n2≤i≤n，有 ℓi≥ℓi−1\ell_i \geq \ell_{i-1}ℓi≥ℓi−1 成立；
- 节点 iii 的度数给定，为 did_idi，并且所有 did_idi 均等于 222 或 333。
请计算满足条件的不同的图的数目，输出其除以 109+710^9 + 7109+7 的余数。两张无向图不同当且仅当存在点对 (u,v) (1≤u<v≤n)(u, v) \ (1 \leq u < v \leq n)(u,v) (1≤u<v≤n) 使得其中一张图中 (u,v)(u, v)(u,v) 间有边而另一张图中没有。
