题目描述

今天是五一劳动节的放假期间，小算却始终没有闲着，他一直都在刷算法题，可能是他认为老师出的题太简单了，没有意思 ~，于是他自己给自己出了了个 问题：

一条手链，可以穿两种颜色的珠子进去，分别是 灰色和白色。可是呢，小算个人不太喜欢灰色，可能是因为它的颜色不是太突出（他希望让灰色来衬拖白色）。为了让白色使得手链更加显眼，每两颗白色珠子之间必定不能相邻，这样使得白色珠子更加的分散，而灰色珠子是可以相邻的，现在他不想考虑太多，手链的首尾由于还需要用铁质加工（ 假设不算相邻 ），一串手链上尽量保证符合以上条件即可，无论穿多少颗白色珠子。

现在假设有灰白色珠子无数颗，长度为 N 的手链有 S 穿接方法（注意数据范围哦~）,同时针对所有的穿接方法，小算想知道任意选取 K 种穿接方法的组合总数（ 无关顺序 ）。

例如 [1, 2, 3] 表示选取 3 种不同的穿接方法:

组合为：[1]，[2]，[3]，[1, 2]， [1, 3]， [2, 3]，[1, 2, 3] ，共 8 种组合。

输入格式

输入包含一行，第一行包含 2 个整数 n ， k ，表示手链的长度和选择的穿接方法数。（数据保证 k 小于等于穿接方法的种数）

输出格式

输出两个整数代表穿接方法的种数和组合总数，答案可能非常大，请将答案 模 10^9 + 7。

数据范围

1 ≤ n, k ≤ 10^6

样例

样例输入

2 2

样例输出

3
9

解释

长度为 n=2 的手链可行方案： 灰灰 ， 灰白 ， 白灰 ，共 3 种穿接方法。

由于不限制顺序，对于所有穿接方法（编号为 [1, 2, 3] ）选择 k=2 种穿接方法为一组有： 1，2一组；1，3一组，2，3一组共三组。

对于每组（编号为 [k1, k2] ）组合方案有： [k1], [k2], [k1, k2] 共三种组合。

所以组合总数为 3 * 3 = 9 种

样例输入

98996 2

样例输出

821534814
602065504

时限： 500 ms
出题人： dreamy-xay