UOJ Logo

NOI.AC

1S 512MB

#148. set

统计

集合(set)

【题目描述】

已知两个整数N与M,你需要构造两个整数集合X与Y,且需要满足以下要求:

(1)对所有的xi∈X,满足1<=xi<=N;对所有的yj∈Y,满足1<=yj<=M; (X与Y可以为空集)

(2)X∩Y=Φ;(但不要求集合X与Y的元素个数,只要两者没有交集即可)

不妨设构造后的集合X含有n个元素,而集合Y有m个元素,令 A=x1 xor x2 xor x3 xor ... xor xn, B=y1 xor y2 xor y3 ... xor ym。其中,xor 为异或运算,并且 称A与B分别是集合X与集合Y的异或和。如果一个集合为空集,那它的异或和被认为是0。

求对于给定的N与M符合要求(1)、(2)且满足A < B的集合X、Y的不同构造方法个数,输出结果 mod 10^9 + 7。其中,两种构造方案被认为是不同的,当且仅当两种方案中的集合X或集合Y包含的元素集不完全相同。

【输入格式】

一行两个整数N,M

【输出格式】

一个整数,即方案个数取mod 1,000,000,007后的结果。

【样例输入1】

2 2

【样例输出1】

4

【样例解释1】

X={}   and Y={1}
X={}   and Y={2}
X={}   and Y={1, 2}
X={1}  and Y={2}

【数据范围】

对于 20 % 的数据,n,m ≤ 10。

对于 40 % 的数据,n,m ≤ 40。

对于 60 % 的数据,n,m ≤ 200。

对于 100 % 的数据,n,m ≤ 2000。