Pretty Patterns - 3#4809
The company BrokenTiles is planning to design black and white tile patterns for the yards of affluent clients, with each tile being 1 \times 1 meter in size. All these clients have yards in the currently trendy shape of a rectangle measuring n \times m meters.
While preparing the financial plan, the director of the company faced two significant challenges: first, each new client will naturally want a unique pattern that differs from those of all other clients; second, the pattern must be visually appealing.
Research indicates that a pattern is considered attractive if it does not contain any 2 \times 2 meter square entirely filled with tiles of the same color.
To finalize the financial plan, the director needs to determine how many clients can be served before the supply of attractive patterns of this size is exhausted. Your task is to assist him in this calculation.
The first line of the input file contains three natural numbers , , and (1 \leq n \leq 10^{100}, 1 \leq m \leq 5, 1 \leq p \leq 10000).
Output a single number in the output file — the number of distinct attractive patterns that can be arranged in a yard of size n \times m, calculated modulo . Patterns that are transformations of each other through shifting, rotation, or reflection are considered different.
Example 1