提示: 欢迎访问OurACM平台。
Problem 1623 Revival's board

Accept: 28    Submit: 61
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

Oaiei is an outstanding architect. He can do so well now is mainly becase he is always playing building block game in his childhood.

The rule of the game is shown as follows:

  • the chessboard is a rectangular with the height is M and the width is N
  • you can only use some 1*2-size building blocks
  • you should use a number of 1*2-size building blocks, and the blocks should completely covered the chessboard. The chessboard can not have surplus, and the blocks can not cover each other

Oaiei knows that you are very smart, and he would like to know there are how many different methods of coverage.

Input

There are multiple tests. For each test, there are three integers N,M,P, denoting the chessboard is M*N(M<=5,N<=10^9,1<=P<=10000).

Output

For each test, you should output the number of different methods of coverage. Because the result can be very large, output the result MOD P.

Sample Input

11 2 100 11 4 100

Sample Output

44 5

Source

Summer Training Qualification I

Submit  Back  Status  Discuss