Гармонический ряд
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
16 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Гармоническим рядом в математике называется следующая сумма:

.

Данный ряд обладает многими замечательными свойствами. Он расходится, а сумма первых 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.