Задачи
Количество различных подстрок
Количество различных подстрок
Вам задана строка \textbf{s = s_1s_2... s_n}, длины \textbf{n}. Найдите количество ее различных подстрок.
Строка генерируется необычным способом. А именно, вам задано простое число \textbf{p} (\textbf{2} ≤ \textbf{p} ≤ \textbf{10^9}), символ \textbf{s}_\{i \}равен букве с номером \textbf{(((p^i) mod (10^9+7)) mod 26)+1} в английском алфавите. Считайте, что регистр всех букв строки одинаковый.
Операция \textbf{a mod b} обозначает взятие остатка от деления числа \textbf{a} на число \textbf{b}.
\InputFile
В первой строке заданы два целых числа \textbf{n} и \textbf{p} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^5}, \textbf{2} ≤ \textbf{p} ≤ \textbf{10^9}). Число \textbf{p} - простое.
\OutputFile
Выведите единственное целое число --- количество различных подстрок строки \textbf{s}.
Входные данные #1
5 2
Выходные данные #1
15