Jeśli uważasz, że pojęcie przestrzeni jest niejasne, poniżej przedstawiamy ścisłą definicję matematyczną używaną w tym zadaniu.

Można przyjąć, że „przekrój” w przestrzeni euklidesowej $\mathbb R^k$ jest określony przez niezerowy wektor $k$-wymiarowy $\mathbf a \neq \mathbf 0$ oraz liczbę rzeczywistą $\lambda$. Oznaczmy go jako $(\mathbf a, \lambda)$. Zbiór punktów leżących na tym „przekroju” to $H_i = \left\{ \mathbf x \in \mathbb R^k \middle\vert \mathbf a \cdot \mathbf x = \lambda \right\}$. Przekrój ten dzieli pozostałą część przestrzeni na dwie części $(L_i, R_i)$, gdzie $L_i = \left\{ \mathbf x \in \mathbb R^k \middle\vert \mathbf a \cdot \mathbf x < \lambda \right\}$ oraz $R_i = \left\{ \mathbf x \in \mathbb R^k \middle\vert \mathbf a \cdot \mathbf x > \lambda \right\}$.

Wówczas rodzina „obszarów”, na które dzielona jest cała przestrzeń, wyraża się wzorem:

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

Prosta może zostać podzielona przez punkty na dwie półproste i pewną liczbę odcinków. Płaszczyzna może zostać podzielona przez pewną liczbę prostych na wiele obszarów. Przestrzeń 3-wymiarowa może zostać podzielona przez pewną liczbę płaszczyzn na wiele części...

Oblicz, na maksymalną liczbę części można podzielić przestrzeń $k$-wymiarową za pomocą $n$ „przekrojów” $(k-1)$-wymiarowych.

Wynik podaj modulo $P = 10^9 + 7$.

Wejście

W jednym wierszu znajdują się dwie dodatnie liczby całkowite $k, n$, oznaczające wymiar przestrzeni oraz liczbę „przekrojów”.

Wyjście

Wypisz wynik.

Przykład

Przykład 1

Wejście

2 3

Wyjście

7

Przykład 2

Wejście

3 3

Wyjście

8

Przykład 3

Wejście

123 321

Wyjście

833554445

Przykład 4

Wejście

999800 1000000

Wyjście

32983392

Podzadania

Dla $100\%$ danych wejściowych spełnione są warunki $k, n \le 10^6$.