Гармоническим рядом в математике называется следующая сумма:
.
Данный ряд обладает многими замечательными свойствами. Он расходится, а сумма первых n его членов стремится к (где γ — константа Эйлера — Маскерони) при стремлении n к бесконечности.
Тор не очень любит математический анализ, поэтому его не очень интересуют факты про замечтельные свойства гармонического ряда. Зато Тор от скуки придумал новый математический объект и назвал его гармоническим рядом по простому модулю p.
Гармоническим рядом по простому модулю p Тор называет следующую сумму:
.
Числом для целого
по простому модулю p Тор называет такое целое число
, что x·y ≡ 1 ± od p. Можно доказать, что если p — простое число, то для любого x, удовлетворяющего ограничению выше, найдётся ровно один подходящий y.
Тору стало интересно, чему равна сумма членов ряда от l до r, то есть чему равна сумма .
В первой строке задано три целых числа l, r и p (1 ≤ l ≤ r < p, r - l < 2·107, p ≤ 109, p — простое).
Выведите одно целое число — ответ на задачу. Обратите внимание, что все арифметические операции в данной задаче выполняются по модулю p.
1 5 7
1
3 10 31
4
Натуральное число x называется простым, если оно не равно 1 и у него нет делителей, отличных от 1 и x.