Szachownica

Limit pamięci: 64 MB

Bajtazar jest miłośnikiem szachowych zagadek i długoletnim prenumeratorem Kwartalnika niedzielnego szachisty. W ostatnim numerze znalazł takie oto zadanie:

Dana jest szachownica o wymiarach . Na ile sposobów można na niej ustawić wież tak, by żadne dwie wieże się nie atakowały, oraz by -ta wieża nie stała w -tej kolumnie ani w -tym wierszu? Wieże, wiersze i kolumny numerujemy liczbami od 1 do . Wynik wystarczy podać modulo .

Z zadaniami typu "mat w trzynastu posunięciach" Bajtazar radził sobie nie najgorzej, a tutaj biedak utknął. Poprosił Cię zatem o pomoc.

Wejście

W jedynym wierszu wejścia znajdują się dwie liczby całkowite i (, ).

Wyjście

W jedynym wierszu wyjścia należy wypisać szukaną liczbę ustawień wież.

Przykład

Dla danych wejściowych:

3 120

poprawną odpowiedzią jest:

4

Autor zadania: Tomasz Idziaszek.