构造序列
题号：NC301657
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}加藤翔子想构造一个神秘的序列，所以她给定了正整数 n 和 m。加藤翔子考虑所有长度为 n 的整数序列 a=\{a_1,a_2,\dots,a_n\}，其中每个 a_i 的取值为 1,2,\dots,m。
\hspace{15pt}将序列划分为若干个连续的段，使得每个段内的所有元素都相等，且任意相邻两个段的元素都不相等。我们称这样划分出的段为 R 段。设这些 R 段的长度依次为 l_1,l_2,\dots,l_k。若 l_1 < l_2 < \dots < l_k，则称该序列为「合法」。
\hspace{15pt}现在她想要考考你，请你回答「合法」序列的个数是多少？由于答案可能很大，请将答案对 (10^9+7) 取模后输出。

输入描述:

\hspace{15pt}在一行上输入两个整数 n,m \left ( 1 \le n \le 10^5;\,1 \le m \le 10^9 \right )，表示序列长度、序列的取值大小（取值为 1 到 m）。

输出描述:

\hspace{15pt}输出一个整数，表示长度为 n 且所有 R 长度严格递增的序列个数，对 10^9+7 取模。
示例1

输入

复制 
3 2

输出

复制 
4

说明

\hspace{15pt}在这个样例中，长度为 3，数字来自 \{1,2\} 的合法序列有 \{1,1,1\}，\{2,2,2\}，\{1,2,2\}，\{2,1,1\}，共 4 个。
示例2

输入

复制 
10 114514

输出

复制 
870525937