题解

前缀和优化DP

对于这种计数类问题，而且还需要取模的情况下，往 DP 方面想准没错了。

朴素DP

题目描述

给定两个整数 $n$ 和 $m$，询问满足如下条件的序列 $a$ 的数量：

• 序列 $a$ 的长度为 $n$ ；
• 序列 $a$ 的值均大于等于 0 且小于等于 $m$，形式化地说，$0 \leq a_i \leq m \ (1 \leq i \leq m)$；
• $a_1 \leq a_2 \leq a_3 \leq \cdots \leq a_n$，表示序列 $a$ 是一个非递减序列；
• 序列 $a$ 所有元素的异或值为 $m$。

输入描述

在一行上输入两个整数 $n,m$ ($1 \leq n \leq 300; 0 \leq m \leq 300$) 表示序列的长度和序列的取值范围。

输出描述

在一行上输出一个整数，表示满足条件的不同的序列 $a$ 的数量；由于答案可能很大，请将最后的结果对 $10^9 + 7$ 取模。

示例 1

输入

2 3

输出

2

说明

其中序列 $[0,3]$ 和 $[1,2]$ 满足条件

示例 2

输入

4 7

输出

40

示例 3

输入

200 200

输出

391022064