牛牛xor牛妹
题号:NC21620
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

牛牛有一个集合{1,2,...,N}

牛妹有一个集合{1,2,...,M}

牛牛要从自己的集合里面选出一个子集,牛妹也一样

要求两个人选出的子集交集为空并且牛牛的子集的xor和小于牛妹的子集的xor和

求他们一共可以选择多少不同对的子集,模1e9+7

输入描述:

输入一行包含两个整数n,m (1<=n,m<=2000)

输出描述:

输出一个整数
示例1

输入

复制
2 2

输出

复制
4
示例2

输入

复制
47 74

输出

复制
962557390

备注:

子任务一30分:n,m<=20

子任务二30分:n,m<=100

子任务三40分:n,m<=2000