在 NOIP2020 之前，Clamee 给 Awcotn 寄去了一朵鲜花。如今，宇宙第一快递公司成功地将这朵花送到了 XTU。Clamee 已记不清这朵花长什么样了，但他还记得这朵花的制作流程，现在他把流程告诉了你，他想知道他送给 Awcotn 的花有多少种。 这朵花可以看成一个 $$$n(3\le n \le 10^7)$$$ 个点的菊花图(星形图)，这 $$$n$$$ 个节点从 $$$1$$$ 到 $$$n$$$ 编号，它是按以下方法制作的：

菊花图一开始所有节点都未被染色。

Clamee 有 $$$n-1$$$ 种颜料，他为每个叶子节点指定了一种颜料。

然后他进行了多次(可以是任意次)操作，每次操作是以下两种之一：

1.选择一个叶子节点，将它染成它所对应的颜料的颜色，

2.选择两个相邻的节点 $$$u,v$$$，将其中 $$$u$$$ 节点染成 $$$v$$$ 节点的颜色，该操作需要保证 $$$v$$$ 节点已被染色。

请输出 Clamee 可以生成的合法菊花图总数，答案对 $$$10^9+7$$$ 取模。

两张菊花图不同当且仅当两张菊花图存在一个编号相同的点，满足这个点在两张图中的的颜色不同。

一张菊花图合法当且仅当它的所有节点均被染色，并且可以由以上的两种染色操作染成。