ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Winter 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Salary for Robots

Time limit: 2.0 second
Memory limit: 64 MB
There are n robots on planet PTZZZ. Each robot has its own unique rank—an integer from 1 to n, and should execute all orders from robots with a higher rank.
Once a month all robots get their salary: a positive integer number of credits, not exceeding k. The salary is paid by an accountant-robot. Salary is so important for robots that the first month when all the robots got their salary was named the First month of the First year. There are p months in the year on PTZZZ, so the robots get their salary p times a year.
The salary paid to each robot can be different in different months. If it turns out that all the robots get exactly the same salary as in any month earlier, the accountant-robot will rust of sadness. What is more, the law doesn't allow the accountant-robot to pay salary in such a way that there will be a triple of robots (a, b, c) with rank of a higher than rank of b, rank of b higher than rank of c and the salary of a less than the salary of b and the salary of b less than the salary of c.
The accountant-robot doesn't want to rust, so since the First month of the First year he tries to pay salary in different ways. However, the accountant-robot will rust sooner or later. Your task is to calculate the month number when this will happen.


The only input line contains three space-separated integers n, k and p—the number of robots on PTZZZ, the maximal possible salary and the number of months in a year, respectively (1 ≤ n ≤ 1000; 1 ≤ k ≤ 200; 2 ≤ p ≤ 109).


Output the month number the accountant-robot will rust in. Months are numerated 1 to p.


3 3 20
Problem Author: Igor Chevdar
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009
To submit the solution for this problem go to the Problem set: 1696. Salary for Robots