Mieszkańcy kraju R żyją w mieście z $k$ ulicami, przy każdej z których znajduje się $n$ domów, ułożonych w uporządkowany sposób w formie kwadratowej siatki. Początkowo każde dwa sąsiadujące domy (zarówno wzdłuż ulicy, jak i między ulicami) są połączone drogą. Krótko mówiąc, domy te są połączone siecią dróg w kształcie siatki. Jednak ostatnio władze miejskie borykają się z brakiem funduszy i nie są w stanie utrzymać tak dużej liczby dróg, dlatego muszą zredukować ich liczbę do minimum, zachowując jednocześnie spójność sieci (dowolne dwa domy muszą być połączone drogami). Należy zauważyć, że drogi wzdłuż ulic również mogą być częściowo usunięte. Nietrudno zauważyć, że ostatecznie pozostanie dokładnie $kn - 1$ dróg. Oblicz, na ile sposobów można wybrać drogi, aby spełnić ten warunek.
Wynik podaj modulo $P = 10^9 + 7$.
Wejście
Jedna linia zawierająca dwie liczby całkowite $k, n$.
Wyjście
Wypisz jedną liczbę oznaczającą wynik.
Przykład
Przykład 1
Wejście
2 2
Wyjście
4
Podzadania
| Test | $k \le $ | $n \le $ |
|---|---|---|
| $1$ | $2$ | $5$ |
| $2$ | $3$ | |
| $3$ | $2$ | $10^5$ |
| $4$ | $10^9$ | |
| $5$ | $3$ | $10^4$ |
| $6$ | $4$ | |
| $7$ | $5$ | |
| $8$ | $10^9$ | |
| $9$ | $6$ | $10^3$ |
| $10$ | $10^9$ |
Dla $100\%$ danych wejściowych gwarantuje się, że $2 \le k \le 6$ oraz $1 \le n \le 10^9$.