Euleonora Pt. 1
Лятна Школа по Информатика, 2009
Time Limit: 0.8s, Memory Limit: 64MiB
Сблъсквали ли сте се някога с продавачка в магазин, която не може да сметне колко ресто трябва да ви върне, когато й давате 42 лева при сметка 37? Ако не сте, то Елеонора със сигурност е – най-вече поради честите си посещения в моловете (където продавачките мислят, че "логаритъм" е вид крем за лице, а Форд-Белман и Форд-Фулкерсон могат да се намерят в салоните на Мото-Пфое).

От друга страна Ели е значително по-интелигентна. Докато продавачката се справя със "сложните" сметки, тя е измислила начин да запълва времето си. За всяко положително цяло число N тя смята колко на брой по-малки или равни на него положителни цели числа има, които са взаимно-прости с N - тоест за колко различни AiN е изпълнено GCD(Ai, N) = 1. Например, за числото 9 нейната функция би върнала 6, тъй като 1, 2, 4, 5, 7 и 8 са взаимно-прости с 9. Тя е нарекла функцията, която връща този брой, "функция на Ойлеонора" и я бележи като phi(N).

Да смята тези числа на ум за нея не е проблем, но понякога сметките на продавачката се бавят твърде много (я си представете, че има и стотинки!), за това тя изчислява цели интервали от числа наведнъж. Това, всъщност, не е толкова лесно, но намирането на phi(N) може да се сведе до намиране на простите множители на N.

Вие, естествено, искате да впечатлите Ели като напишете програма, която да може да се конкурира дори с нейните способности. Като първа стъпка за тази програма трябва да намерите произведението на простите делители на числата в интервала. Например за интервала [5, 12] имаме (5)*(2*3)*(7)*(2)*(3)*(2*5)*(11)*(2*3) = 831,600. Тъй като това число може да стане доста голямо, от вас ще се иска да го изведете по модул M.
Вход
На единствения ред на стандартния вход ще бъдат зададени три цели числа A, B и M, задаващи границите на интервала, от който Ели се интересува, както и модула, по който трябва да изпечатате отговора.
Изход
На стандартния изход изведете полученото число по дадения модул.
Ограничения
  • 1 ≤ AB ≤ 10,000,000
  • 1 ≤ M ≤ 231
Примерен Вход Примерен Изход
5 12 666 432
831,600 mod 666 = 432
Мрън!