#arc107d. [arc107_d]Number of Multisets
[arc107_d]Number of Multisets
题目描述
给定两个正整数 和 。有多少个有理数的多重集合满足以下条件?
- 多重集合恰好有 个元素,它们的和等于 。
- 多重集合中的每个元素是 $1, \\frac{1}{2}, \\frac{1}{4}, \\frac{1}{8}, \\dots$ 中的一个。换句话说,每个元素可以表示为 。
由于答案可能很大,因此对 取模后输出。
约束条件
- 输入中的所有数字均为整数。
输入
从标准输入读入输入数据的格式如下:
输出
打印满足所有给定条件的有理数多重集合的数量,对 取模。
示例输入 1
4 2
示例输出 1
2
以下两个多重集合满足所有给定条件:
- ${\\frac{1}{2}, \\frac{1}{2}, \\frac{1}{2}, \\frac{1}{2}}$
示例输入 2
2525 425
示例输出 2
687232272