Chess
Petryk has developed an interest in chess, but he quickly grew tired of traditional play after winning first place in a junior chess competition. Now, he's fascinated by different configurations of chess pieces on various boards. Currently, Petryk is curious about how many ways he can place any number (including zero) of knights on a 4×n board such that no two knights can attack each other. However, Petryk isn't fond of dealing with large numbers, so he only needs to find the remainder when this count is divided by a given number p. Assist him in solving this intriguing problem.
Your task is to compute the remainder when the number of non-attacking knight placements on a 4×n board is divided by p.
Input
The input consists of a single line containing two integers: the board's length n (2 ≤ n ≤ 10^9) and the divisor p (2 ≤ p ≤ 10^9).
Output
Output the remainder when the number of possible non-attacking knight placements on a 4×n board is divided by p.