#P6023. 疫苗

疫苗

题目描述

中二病正在危害人类!不知何时爆发的中二病,起初还毫无任何症状,最近却连续出现致命症状,已经成为了一种不治之症。科学家们正在着手研发疫苗。 科学家从患者体内提取出了中二病病原体,并找出了其致病 DNA。这条 DNA 可以被分为 nn 段,第 nn 段和第 11 段相接,呈环形。要制作疫苗的话,需要从中取出若干段 DNA。

然而,中二病的生存和复制能力特别强。如果疫苗中存在两段在原 DNA 中距离小于 kk 的 DNA,这两段就可以复制出整条 DNA。因此,科学家选择的若干段 DNA 彼此之间的距离都应该不小于 kk

这里定义距离为两段 DNA 在原序列中间隔的最少段数 +1+1,如相邻的两段距离为 11。自己与自己的距离不做定义,换言之,不论 kk 的值是多少,总能选出一段 DNA。为了使疫苗对于各种属性的人都有效,科学家想制作尽量多种的疫苗。也就是说,要在满足上面的条件的情况下,选出尽量多组不同的 DNA 段,分别制成疫苗。当然,选出这样若干段的方案数有很多,但是有些方案在旋转之后是相同的,因此在本质上也是相同的。

请你编写一个程序,求出最多能制作的疫苗种数,以及最多能制作的本质不同的疫苗种数。由于答案可能很大,输出答案对 109+710^9+7 取模得到的结果。

输入格式

输入只有一行,包含两个整数 nnkk ,含义如问题描述中所述。

输出格式

输出两行,每行一个非负整数,分别表示所求的两个方案数取模得到的结果。

5 2
10
2
6 1
63
13

数据范围与提示

n100000,k100000,1kn2n\leq100000,k\leq100000,1\leq k \leq \frac{n}{2}

注意一段都不选不是一个合法的方案。