Podzbiory względnie pierwsze

Limit pamięci: 64 MB

Ile jest podzbiorów zbioru , które są względnie pierwsze? Zbiór liczb całkowitych nazywamy względnie pierwszym, gdy jego każde dwa elementy są względnie pierwsze. Dwie liczby są względnie pierwsze, jeśli ich największy wspólny dzielnik wynosi .

Wejście

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

Wyjście

Na wyjściu należy wypisać liczbę względnie pierwszych podzbiórów zbioru modulo .

Przykład

Dla danych wejściowych:

4 7

poprawną odpowiedzią jest:

5

\paragraph{Wyjaśnienie do przykładu:} Względnie pierwsze podzbiory zbioru to , , , , , , , , , , , . modulo to .

Ograniczenia

W testach wartych co najmniej punktów zachodzi . W testach wartych co najmniej punktów zachodzi .

Autor zadania: Jakub Łącki.