You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

下面两个问题你都要解决：

• 在一个 $1*N$ 的棋盘上放置 $K$ 枚棋子，任意两枚棋子不能相邻，有多少种摆放方法？答案对 1e9+7 取模。
• 在一个 $1*N$ 的棋盘上放置任意多枚棋子，任意两枚棋子不能相邻，有多少种摆放方法？答案对 1e9+7 取模。
• 在一个 $1*N$ 的环形棋盘上放置 $K$ 枚棋子，任意两枚棋子不能相邻，有多少种摆放方法？答案对 1e9+7 取模。

格式

输入

$N,K$

输出

输出三行，第一行是第一个问题的答案，第二行是第二个问题的答案（当然，第二个问题和 $K$ 没有关系）, 第三行是第三个问题的答案。

样例

4 2

3
8
2

数据范围

$N,K≤10^6$