A lot has changed since the previous task was written. Pretty patterns (for what they are – see the "Pretty Patterns" problem) have become very popular all over the world, so people are willing to maintain a very large piece of land, just to have a pattern on it that is not found anywhere else.
BrokenTiles is now the world's leading manufacturer of cute patterns! To make a plan, CEO Vasya still needs to know how many customers can expect a given size pattern.
Since the scales are literally global, N <= 10100. However, Vasya doesn't like big numbers, so he asks for the answer modulo P.
Input
The first line of input contains three positive integers separated by a space – N, M and P (1 <= N <= 10100, 1 <= M <= 5, 1 <= P <= 10,000).
Imprint
Print the number of different nice patterns N x M modulo P .