Tənlik

Verilmiş tənlik növü X^N + Y^N ≡ Z^N mod M.

Sabit N və M üçün bu tənliyin müxtəlif həllərinin sayını tapmaq lazımdır. Həll, belə bir təbii ədədlər üçlüyü (X, Y, Z) adlanır ki, aşağıdakılar yerinə yetirilir:

• 1 ≤ X ≤ Y < M

• 1 ≤ Z < M

• X^N + Y^N ≡ Z^N mod M

Giriş verilənləri

Giriş faylının yeganə sətirində N və M ədədləri verilmişdir (1 ≤ N, M ≤ 7^7).

Çıxış verilənləri

Çıxış faylına bir ədəd yazın — məsələnin cavabı.

Nümunələr