该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

斐波那契数列是一种递推数列，其表达式为

• $f(1) = 1$
• $f(2) = 1$
• $f(n) = f(n-1) + f(n-2),n > 2$

对于久经沙场的 OIer 来说，这未免也太简单了。于是，我们提高一点点难度，我们所需要做的是求出$f(n) \bmod\,2^{31}$ 之后的结果，并将该结果进行质因数分解，注意 $1$ 我们通常不定义为质数。

输入格式

输入一个正整数 $n$，表示所求的第 $n$ 项。

输出格式

输出一行，将斐波那契第 $n$ 项取余后的结果输出，紧接其后输出一个 = 并写出其质因数分解展开式，要求质因数由小到达排列，每个质因数之间由一个 * 号来连接。

样例

6

8=2*2*2

提示说明

对于 $50\%$ 的数据，$3\le N\le 20$。

对于 $80\%$ 的数据，$1\le N\le 40$。

对于 $100\%$ 的数据，$1\le N\le 50$ 。