P12392 「RiOI-6」Re:帝国少女

 小萝卜是远近闻名的军师呢（自豪脸）。 不过最近，如果你要找她请教，那么她就会大喊一声：那！我！问！你！ 你愿意和他（她）一直在一起吗？你能接受被拒绝被分手吗？你能为了他付出多少呢？你能保证完成自己许下的诺言吗？ ——不过萝卜还是很愿意帮忙的，尽管她已经见证了若干自己促成的人们分手了……生气啊啊啊啊啊！

> 萝卜有 $m$ 件衣服，计划表为长为 $n$ 的序列 $a$，则 $a_i$ 为 $[1,m]$ 中的整数，表示当天穿的是哪一件衣服。 > 现在给定 $a$，萝卜每次修改可以将 $a_i$ 修改为 $[1,m]$ 中任何一个整数，要求在使得序列中相邻的两个数都不同的前提下，让修改次数最少。 小萝卜的朋友很多，她们也希望和自己的意中人出去玩，她要以此为切入点评判这些情感问题。 具体的，对于一个表示计划表的序列 $a$，令**困难程度** $f(a,n,m)$ 表示以上问题的答案，$g(a,n,m)$ 表示使答案最优的修改方案数。其中两个方案不同当且仅当修改后的序列不同。 在所有长为 $n$ 值域为 $[1,m]$ 的整数序列中，对于每个 $i\in[0,\lfloor\frac{n}2\rfloor]$，小萝卜想知道困难程度为 $i$ 的序列的最优修改方案数之和是多少。 形式化的，给定 $n,m$，令所有长为 $n$ 值域为 $[1,m]$ 的整数序列的集合为 $S$，则对每个 $i\in[0,\lfloor\frac{n}2\rfloor]$ 求： $$ \sum\limits_{a\in S}[f(a,n,m)=i]g(a,n,m) $$ 答案对 $10^9+7$ 取模。

无

无

#### 【样例解释】 对于样例 $1$，所有可能的序列以及对应的 $f,g$ 函数值如下： - $[1,1,1]$：$1,1$。 - $[1,1,2]$：$1,1$。 - $[1,2,1]$：$0,1$。 - $[1,2,2]$：$1,1$。 - $[2,1,1]$：$1,1$。 - $[2,1,2]$：$0,1$。 - $[2,2,1]$：$1,1$。 - $[2,2,2]$：$1,1$。 故 $i=0$ 时答案为 $2$，$i=1$ 时答案为 $6$。 对于样例 $2,3$，暂时不能给你一个明确的答复。 #### 【数据范围】 **本题开启捆绑测试。** |子任务|分数|$n\le$|$m\le$| |:-:|:-:|:-:|:-:| |$1$|$7$|$9$|$5$| |$2$|$10$|$5\times10^3$|$2$| |$3$|$13$|$50$|$50$| |$4$|$15$|$200$|$200$| |$5$|$20$|$200$|$10^9$| |$6$|$35$|$5\times10^3$|$10^9$| 对于 $100\%$ 的数据，$1\le n\le 5\times10^3$，$2\le m\le 10^9$。