Количество различных подстрок
Hard
Execution time limit is 0.5 seconds
Runtime memory usage limit is 256 megabytes
Вам задана строка 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.
Input
В первой строке заданы два целых числа n и p (1 ≤ n ≤ 10^5, 2 ≤ p ≤ 10^9). Число p - простое.
Output
Выведите единственное целое число — количество различных подстрок строки s.
Examples
Input #1
Answer #1
Submissions 304
Acceptance rate 5%