#P13666. [ARC144D] AND OR Equation
[ARC144D] AND OR Equation
题目描述
给定正整数 和 。请计算满足以下所有条件的整数序列 的个数,并将答案对 取模后输出。
- 对于任意非负整数 (),都有 。
- 对于任意非负整数 (),都有 $f(x) + f(y) = f(x\ \mathrm{AND}\ y) + f(x\ \mathrm{OR}\ y)$。
其中, 和 分别表示按位与和按位或运算。
输入格式
输入为一行,包含两个整数 和 。
输出格式
输出满足条件的整数序列的个数,对 取模后的结果。
输入输出样例 #1
输入 #1
2 1
输出 #1
6
输入输出样例 #2
输入 #2
2 2
输出 #2
19
输入输出样例 #3
输入 #3
100 123456789123456789
输出 #3
34663745
说明/提示
数据范围
样例解释 1
满足条件的整数序列共有 个: