Задача №112710. Награды
На одном Очень Важном Предприятии решили наградить некоторых k его работников. Конечно же, решили сделать это в соответствии со следующей Очень Важной Процедурой.
Всех n работников выстроили в один ряд. Причем, получилось так, что каждый работник видит только своих непосредственных соседей в этом ряду. Для повышения уровня производства на Очень Важном Предприятии начальство решило сделать так, чтобы каждый награжденный считал, что наградили именно его и только его. Для этого необходимо, чтобы в ряду не было двух рядом стоящих награжденных работников.
Вам необходимо написать программу, которая будет считать количество способов раздать таким образом k наград среди n стоящих в ряд работников. Так как это число может быть весьма большим, необходимо найти его остаток от деления на простое число m .
В первой и единственной строке входного файла заданы три целых неотрицательных числа n , k и m — количество работников на Очень Важном Предприятии, количество наград и простой модуль ( 1 ≤ k ≤ n ≤ 100000, 1 ≤ m ≤ 10 9 ).
В выходной файл выведите единственное целое число — ответ на задачу, взятый по модулю простого числа m .
3 2 569
1
5 2 673
6