Background

⚡超越一切 震慑凡人⚡

⚡带来终结 机械降神⚡

⚡风暴之力 充满全身⚡

⚡最后一击 核心共振⚡

请注意数据范围！😡

Description

定义函数 $f$，$g$，$h$，$i$：

$$\begin{cases} f(x)=2 \times f(x-1)+1,&x \geq 2; \\ f(1)=1 . \end{cases}$$

$$\begin{cases} g(x)=42 \times 4^{x}-5 \times g(x-1)-6 \times g(x-2),&x \geq 2;\\ g(0)=g(1)=0. \end{cases}$$

$$\begin{cases} h(x)=7 \times h(x-1) -15 \times h(x-2) + 9 \times h(x-3),&x \geq 3;\\ h(x)=x,&x \leq 2. \end{cases}$$

$$\begin{cases}i(x)=4^{x} \times (2x+1)+3 \times i(x-1),&x \geq 2;\\i(0)=1;i(1)=12.\end{cases}$$

分别求 $f(n)$，$g(n)$，$h(n)$ ，$i(n)$对 $p$ 取模后的结果。

Format

Input

一行两个正整数 $n$ 和 $p$。

Output

四行每行一个整数，分别表示 $f(n)\mod p$，$g(n)\mod p$，$h(n)\mod p$，$i(n)\mod p$。

Samples

114514 1145141919810

260299089933
547385670972
984140623736
781607029662

1145141919810 1145141919810

906584675913
1132553909172
1007304200378
661050880630

Prompt

对于 $10\%$ 的测试点，$n \leq 10^{2},p \leq 10^{10}$；

对于 $40\%$ 的测试点，$n \leq 10^{9},p \leq 10^{15}$；

对于 $70\%$ 的测试点，$n \leq 10^{100},p \leq 10^{50}$；

对于 $100\%$ 的测试点，$n \leq 10^{1000},p \leq 10^{1000}$。不保证 $p$ 为质数。

别抄我代码了，除非你能说明通项公式是怎么计算出来的（

⚡️神龟虽寿 犹有竟时⚡️

⚡️腾蛇乘雾 终为土灰⚡️

⚡️老骥伏枥 志在千里⚡️

⚡️烈士暮年 壮心不已⚡️