Müxtəlif alt sətirlərin sayı

Sizə uzunluğu n olan s = s_1s_2... s_n sırası verilib. Bu sıranın müxtəlif alt sıracıklarının sayını tapın.

Sıra qeyri-adi bir üsulla yaradılır. Sizə sadə ədəd p (2 ≤ p ≤ 10^9) verilir və s_i simvolu ingilis əlifbasında (((p^i) mod (10^9+7)) mod 26)+1 nömrəli hərfə uyğun gəlir. Bütün hərflərin eyni registrdə olduğunu qəbul edin.

a mod b əməliyyatı a ədədinin b ədədinə bölünməsindən qalanı göstərir.

Giriş verilənləri

Birinci sətirdə iki tam ədəd n və p (1 ≤ n ≤ 10^5, 2 ≤ p ≤ 10^9) verilib. p ədədi sadədir.

Çıxış verilənləri

Tək bir tam ədəd çıxarın — s sırasının müxtəlif alt sıracıklarının sayı.

Nümunələr