一个骰子由六个面组成,每一个面上的数字分别是 。投出骰子后,顶上面的数字即为投掷结果。可以视作投出每一个数字的概率都是相等的,为 。 小歪有 个骰子,每一轮他会投掷所有骰子,然后记录下所有骰子投掷结果的和。 小歪可以投掷若干轮,并累加投掷结果,他想知道,投掷任意多轮,总点数之和为 的概率是多少。你需要将答案对 取模后输出。 提示:本题中,在进行除法的取模时,即计算 ,其中, 可以使用公式 得到:例如,在计算 时,根据公式 ,得到 。
输入描述:
第一行输入两个正整数 代表骰子数量、目标点数。


输出描述:
输出一个整数,代表小歪投出总点数之和为  的概率。可以证明答案可以表示为一个不可约分数 ,为了避免精度问题,请直接输出整数 作为答案,其中 , 是满足 的整数。更具体地,你需要找到一个整数 满足 对 取模等于 ,您可以查看样例解释得到更具体的说明。
示例1

输入

5 5

输出

490869345

说明

\hspace{15pt}在这个样例中,唯一一种可以投掷出 5 点的情况为,投掷一轮,且每一个骰子的点数均为 1,因此概率为 \tfrac{1}{6^5}=\tfrac{1}{7776}
\hspace{15pt}我们可以找到,490\,869\,345 \times 7776 = 3\,817\,000\,026\,720,对 M 取模后为 1。所以输出即为 490\,869\,345
示例2

输入

1 3

输出

893518525

说明

\hspace{15pt}在这个样例中,有且仅有以下四种投掷方法:
\hspace{23pt}\bullet\,投掷一轮,且投出 3 点;
\hspace{23pt}\bullet\,投掷两轮,第一轮投出 1 点,第二轮投出 2 点;
\hspace{23pt}\bullet\,投掷两轮,第一轮投出 2 点,第二轮投出 1 点;
\hspace{23pt}\bullet\,投掷三轮,第一轮投出 1 点,第二轮投出 1 点,第三轮投出 1 点。
\hspace{15pt}总概率为 \tfrac{1}{6} + \tfrac{1}{6^2} + \tfrac{1}{6^2} + \tfrac{1}{6^3}
示例3

输入

2 3

输出

55555556

说明

\hspace{15pt}在这个样例中,有且仅有以下两种投掷方法:
\hspace{23pt}\bullet\,投掷一轮,第一个筛子投出 1 点,第二个筛子投出 2 点;
\hspace{23pt}\bullet\,投掷一轮,第一个筛子投出 2 点,第二个筛子投出 1 点。
\hspace{15pt}总概率为 \tfrac{1}{6} + \tfrac{1}{6}
加载中...