### 问题描述 很久很久以前，在一个神奇的王国里，有一位年轻的数学家，他的名字叫做阿尔贝特。阿尔贝特对数学充满了热情，他对数字和模式的研究让他声名远扬。 有一天，王国的国王得知了阿尔贝特的才华，他召见了阿尔贝特，并向他提出了一个问题： 只能使用小于 $n$ 的数字，构造一个长为 $m$ 的数组，使得数组满足相邻元素之间均互质。你的任务是计算能够造出的不同数组的数量，并将结果告诉我。 阿尔贝特思考了一会儿，然后充满热情地接受了挑战。请你帮助阿尔贝特一起解决这个问题。 ### 输入描述 输入两个数字 $n$ 和 $m$ ，两个数字分别的意义如题面所述。 数据保证： $1 \leq n \leq 66，1 \leq m \leq 10^{18}$ 。 ### 输出描述 输出一个数字，表示不同数组的数量对 $10^9+7$ 取余的结果。 ### 样例输入 ``` 2 4 ``` ### 样例输出 ``` 8 ``` ### 说明 八个数组分别是： $[1,1,1,1][2,1,1,1][1,2,1,1][1,1,2,1][1,1,1,2][2,1,2,1][1,2,1,2][2,1,1,2]$ 。