Кількість різних підрядків

Вам задано рядок s = s_1s_2... s_n, довжини n. Знайдіть кількість його різних підрядків.

Рядок генерується незвичним способом. А саме, вам задано просте число p (2 ≤ p ≤ 10^9), символ s_i дорівнює букві під номером (((p^i) mod (10^9+7)) mod 26)+1 у англійському алфавіті. Вважайте, що регістр усіх букв рядка однаковий.

Операція a mod b позначає взяття залишку при діленні числа a на число b.

Вхідні дані

У першому рядку задано два цілих числа n та p (1 ≤ n ≤ 10^5, 2 ≤ p ≤ 10^9). Число p - просте.

Вихідні дані

Виведіть єдине ціле число — кількість різних підрядків рядка s.

Приклади