If you find the concept of space to be vague, here is the strict mathematical definition of space for this problem.

You can consider such a "hyperplane" in Euclidean space $\mathbb R^k$ to be defined by a $k$-dimensional vector $\mathbf a \neq \mathbf 0$ and a real number $\lambda$, denoted as $(\mathbf a, \lambda)$. The set of points on the "hyperplane" is $H_i = \left\{ \mathbf x \in \mathbb R^k \middle\vert \mathbf a \cdot \mathbf x = \lambda \right\}$, and this pair creates a partition $(L_i, R_i)$ of the remaining space, where $L_i = \left\{ \mathbf x \in \mathbb R^k \middle\vert \mathbf a \cdot \mathbf x < \lambda \right\}$ and $R_i = \left\{ \mathbf x \in \mathbb R^k \middle\vert \mathbf a \cdot \mathbf x > \lambda \right\}$.

Then, the family of "regions" into which the entire space is divided is:

$$\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\}$$

A line can be cut by points into two rays and several line segments. A plane can be divided by several lines into several regions. A 3D space can be divided by several planes into several regions...

Now, please help calculate the maximum number of regions into which $n$ $(k-1)$-dimensional "hyperplanes" can divide a $k$-dimensional space.

The answer should be taken modulo $P = 10^9 + 7$.

Input

A single line containing two positive integers $k$ and $n$, representing the dimension and the number of "hyperplanes", respectively.

Output

Output the answer.

Examples

Input 1

2 3

Output 1

7

Input 2

3 3

Output 2

8

Input 3

123 321

Output 3

833554445

Input 4

999800 1000000

Output 4

32983392

Subtasks

For $100\%$ of the data, it is guaranteed that $k, n \le 10^6$.