F-任意模数NTT_牛客挑战赛67

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有 $n$ 个随机变量，令第 $i$ 个为 $a_{i}$ ，每个变量均从 $[1,m]$ 之间的整数均匀随机。
定义 $S = \max_{i = 1}^{n - 1}{\lbrace a_{i} + a_{i+1}\rbrace }$ ，请你对所有的 $m^n$ 种情况，求出对应的 $S$ 的和。
答案模 $10^9 + 7$ 输出。

输入描述:

一行两个整数。

输出描述:

一行一个整数表示答案。

示例1

输入

复制

3 3

输出

复制

示例2

输入

复制

5 12

输出

复制