问题描述

Hanoi塔由 N 个大小不同中间有孔的圆盘和一字排开的三根柱子 A, B, C 组成。开始时，这 N 个圆盘自下而上由大到小依次套在 A 柱上。

现在要求把 A 柱上的 N 个圆盘按下述规则移到 C 柱上：

(1)一次只能移一个圆盘；

(2)圆盘只能在相邻的柱子间移动；

(3)在移动过程中，不允许大盘压小盘。

问将这 N 个盘子从 A 柱移动到 C 柱上，最少需要移动多少次盘子？答案可能很大，你需要将其 mod (10^9+7) 后输出。你还需要输出前 M 次移动方案，格式见输出格式说明及样例。

输入格式

两个整数 N, M

输出格式

第一行：一个整数，表示最少移动次数 mod (10^9+7)

接下来 M 行：输出前 M 次移动方案，格式见样例输出，注意大小写，每行中间有 7 个空格。数据保证至少存在 M 次移动。

样例输入

2 8

样例输出

8
Step 1: move 1 from A to B
Step 2: move 1 from B to C
Step 3: move 2 from A to B
Step 4: move 1 from C to B
Step 5: move 1 from B to A
Step 6: move 2 from B to C
Step 7: move 1 from A to B
Step 8: move 1 from B to C

数据规模：

20% 的数据：1 ≤ N ≤ 10

40% 的数据：1 ≤ N ≤ 10^7

100% 的数据：1 ≤ N ≤ 10^18, 1 ≤ M ≤ 100