露薇娅和芦苇鸭是一体两面的好朋友。
她们住在环形小镇的两端。环形小镇从 $1$ 到 $n$ 顺序编号，共有 $n$ 条双向道路，露薇娅住在 $s$，而卤味鸭住在 $t$。
这天，露薇娅收掉了定数最高的魔王曲「Contrasty Angeles」，想要去和芦苇鸭炫耀一下。
但是天空依然在下着雨。虽然她并不会被雨淋湿，也不会因为淋雨而陷入梦境，但经过水坑仍是很麻烦的事情。
于是她把这个问题交给了你，想要知道：假设每个道路的长度在整数区间 $[1,m]$ 中随机选取且已知，从 $s$ 到 $t$ 最短路径的长度期望是多少？
同时，她发现你可能不会分数的模运算，于是她为了让你能够输出整数，你可以输出期望值乘以 $m^n$。
同时由于答案可能非常大，你的答案应该对 $10^9+7$ 取模。
与上文题目背景等价。
给定一个 $n$ 个节点的环，节点依次编号为 $1,2,3,\cdots,n$。
很明显该环有双向边 $(1,2),(2,3),(3,4),\cdots(n-1,n),(n,1)$，共有 $n$ 条边。
通过这些边可以从一个节点走到相邻的节点上。显然任意两个节点之间可以互相到达。
给定正整数 $m$，这 $n$ 条边的距离可能在 { ${1,2,3,\cdots,m-1,m}$ } 中等概率随机选取。
显然，这 $n$ 条边各有 $m$ 种可能，所以一共有 $m^n$ 种可能的不同选取方案。
给定起点 $s$ 和终点 $t$，求从 $s$ 到 $t$ 最短路径在这 $m^n$ 种情况下的和。
答案对 $10^9+7$ 取模。
与上文题目描述等价。
我们令从 $v$ 到 $v+1$ 的边 $(v,v+1)$ 的长度设为 $e_v$。特别地，边 $(n,1)$ 的长度为 $e_n$。
求：
$answer=\displaystyle \sum\limits_{e_1=1}^m\displaystyle \sum\limits_{e_2=1}^m \cdots\displaystyle \sum\limits_{e_n=1}^m{distance}(s,t)\mod{10^9+7}=\displaystyle \sum\limits_{(e_1,e_2, \cdots ,e_n) \in {1,2, \cdots ,m}^n}\min{\lbrace e_s+ \cdots +e_{t-1},e_t+ \cdots +e_n+e_1+ \cdots +e_{s-1} \rbrace }\mod{10^9+7}$
共两行，第一行为两个由空格分隔的正整数$n,m$，第二行为两个由空格分隔的正整数 $s,t$。
一行一个整数，代表答案。
3 2
1 212这是一个节点数为 $3$ 的环，共 $3$ 条边，每条边长度在{ ${1,2}$ } 间随机，共 $2^3=8$ 种情况。要找的路径从 $1$ 到 $2$。
当边 $(1,2)$ 长度为 $1$ 时，最短路径长度一定是 $1$，共 $4$ 种情况。
当边 $(1,2)$ 长度为 $2$ 时，最短路径长度一定是 $2$，共 $4$ 种情况。
答案为 $1\times4+2\times4=12$。
4 3
2 4272这是一个节点数为 $4$ 的环，共 $4$ 条边，每条边长度在 { ${1,2,3}$ } 间随机，共 $3^4=81$ 种情况。要找的路径从 $2$ 到 $4$。
可以发现有两条路可走：$A:2\to3\to4$ 或 $B:2\to1\to4$。
可以证明，路径 $A,B$ 均有 $3^2=9$ 种可能，长度为 $2,3,4,5,6$ 的可能分别为 $1,2,3,2,1$。
因此，路径 $A,B$ 长度最小值可能是 $2,3,4,5,6$，可能为 $17,28,27,8,1$。
答案为 $2\times17+3\times28+4\times27+5\times8+6\times1=272$。
8 6
2 41175531040 50
20 30536456982对于 $30\%$ 的数据，$n\leq5,m\leq5,s=1,t=n$。
对于 $80\%$ 的数据，$n\leq50,m\leq50$。
对于 $100\%$ 的数据，$1\leq s\leq t\leq n\leq500,m\leq500$。
一个方便理解的样例：
当 $n=6,s=1,t=5,e_1=1,e_2=2,e_3=3,e_4=4,e_5=5,e_6=6$ 时：
从起点 $s=1$ 到终点 $t=5$ 的最短路径长度为 $1+2+3+4=10$。另一条路的长度为 $5+6=11$，不是最短路径。
哎音游人真的是