もし空間の概念が曖昧であると感じるならば、ここで本問における空間の厳密な数学的概念を定義する。

ある「断面」とは、ユークリッド空間 $\mathbb R^k$ における $k$ 次元ベクトル $\mathbf a \neq \mathbf 0$ と実数 $\lambda$ の組 $(\mathbf a, \lambda)$ であり、その「断面」上の点の集合は $H_i = \left\{ \mathbf x \in \mathbb R^k \middle\vert \mathbf a \cdot \mathbf x = \lambda \right\}$ である。これは空間の残りの部分を $(L_i, R_i)$ という二つの領域に分割する。ここで $L_i = \left\{ \mathbf x \in \mathbb R^k \middle\vert \mathbf a \cdot \mathbf x < \lambda \right\}$、$R_i = \left\{ \mathbf x \in \mathbb R^k \middle\vert \mathbf a \cdot \mathbf x > \lambda \right\}$ である。

このとき、空間全体が分割された「領域」の集合族は以下の通りである。

$$\left\{ \bigcap_{i = 1}^n B_i \neq \emptyset \middle\vert B \in \{L_1, R_1\} \times \{L_2, R_2\} \times \cdots \times \{L_n, R_n\} \right\}$$

直線はいくつかの点によって二つの半直線といくつかの線分に分割される。平面はいくつかの直線によっていくつかの領域に分割される。3次元空間はいくつかの平面によっていくつかの空間領域に分割される……。

今、$k$ 次元空間において、合計 $n$ 個の $k-1$ 次元の「断面」が空間を最大でいくつの部分に分割できるかを計算せよ。

答えは $P = 10^9 + 7$ で割った余りを出力せよ。

入力

一行に二つの正整数 $k, n$ が与えられる。これらはそれぞれ次元数と断面の数を表す。

出力

答えを出力せよ。

入出力例

入力 1

2 3

出力 1

7

入力 2

3 3

出力 2

8

入力 3

123 321

出力 3

833554445

入力 4

999800 1000000

出力 4

32983392

小課題

$100\%$ のデータにおいて、$k, n \le 10^6$ を満たす。