Junior üçün sadələşdirilməyən çoxhədli ifadələr
Bir sadə ədəd p verilib. Z_p = {0, 1, ..., p-1} - qalıqlar sahəsini modul p üzrə götürək. Bu sahədə vurma və toplama əməliyyatları modul p üzrə aparılır. İndi bu sahə üzərində aşağıdakı formada normallaşdırılmış çoxhədli funksiyaları nəzərdən keçirək:
f(x)= x^n + a_{n-1}x^{n-1} + ... + a_1x + a_0,
burada n çoxhədlinin dərəcəsidir, x dəyişəndir, a_i isə Z_p sahəsindən olan əmsallardır.
Məsələn, x^2 + x + 1 çoxhədli Z_2 sahəsində ayrılmazdır. Normallaşdırılmış çoxhədli ayrılmaz adlanır, əgər onu f(x)= p(x) · q(x) şəklində təqdim etmək mümkün deyilsə, burada p(x) və q(x) - f(x)-dən kiçik dərəcəli çoxhədli funksiyalardır. Və bu, Z_2 sahəsində ikinci dərəcəli yeganə ayrılmaz çoxhədlidir.
Sizin vəzifəniz Z_p sahəsində n dərəcəli ayrılmaz çoxhədlərin sayını hesablamaktır.
Giriş verilənləri
Giriş faylının yeganə sətiri iki ədəd p, n (1 ≤ p, n ≤ 10^9, 1 ≤ p^n < 10^18) ehtiva edir.
Çıxış verilənləri
Çıxış faylında Z_p sahəsində n dərəcəli ayrılmaz çoxhədlərin sayını göstərin.