【题目描述】

pechpo很喜欢数列。现在他新定义了一个数列S，其中s₀=0，s₁=1，s_i=2s_i-1+s_i-2，请你求出数列中第n个数mod（或%）p之后的值，并把它分解质因数。

【输入格式】

一行两个整数n，p。

【输出格式】

一行，将第n个数列的数mod p之后，输出这个数，然后用等式的形式按照从小到大的顺序输出所有质因数。

【样例输入1】

4 100

【样例输出1】

12=2*2*3

【样例输入2】

7 100

【样例输出2】

69=3*23

【数据范围】

对于100%的数据，n>1，p<=2^31。

对于20%的数据，n<5，p>n。

对于40%的数据，n<=50，p=2^31。

对于100%的数据，n<=50。