时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
> “如果您愿意的话，让我带您去吧，这座小镇，愿望实现的地方……”
《Clannad》是一款载入史册的galgame，在游戏中有一种名为光玉的道具，收集光玉是进入该游戏精华部分AFTER STORY篇的关键，揭开《CLANNAD》的真正結局，必須集齐全部13颗“光玉”。在游戏剧情的发展中，光玉也扮演着非常重要的角色。
刚刚学了游戏开发的滑滑蛋，制作了一款改版《Clannad》，并对光玉进行了修改。
在他的游戏里，有
个游戏高潮点，在每一个高潮点玩家能获得一颗光玉，每颗光玉有一个在整数范围的愿望值，根据不同的选择，获得光玉的愿望值也有所不同，但范围都在 ![[1,x]](https://www.nowcoder.com/equation?tex=%5B1%2Cx%5D)
之间，并且不会获得相同愿望值的光玉，如果在通过所有高潮点之后，存在两个光玉的愿望值的差的绝对值为 
的倍数，那么玩家就能进入AFTER STORY篇。
由于每个玩家都可能在游戏中做出不同选择，最后进入AFTER STORY篇的选择有很多种，我们如果把所有光玉的愿望值看成一个集合，那么不同集合就是不同的结局。两个集合不同，当且仅当存在某个元素在一个集合中而不在另一个集合中。
作为游戏内测玩家，滑滑蛋想问你，在知道了 和 
的情况下，有多少种结局能够进入AFTER STORY篇，或告诉他不可能。
如果不可能进入AFTER STORY篇，请输出
。
否则输出一共有多少种结局能够进入，由于答案很大，结果需要对
取模。
《Clannad》是一款载入史册的galgame，在游戏中有一种名为光玉的道具，收集光玉是进入该游戏精华部分AFTER STORY篇的关键，揭开《CLANNAD》的真正結局，必須集齐全部13颗“光玉”。在游戏剧情的发展中，光玉也扮演着非常重要的角色。
刚刚学了游戏开发的滑滑蛋，制作了一款改版《Clannad》，并对光玉进行了修改。
在他的游戏里，有
由于每个玩家都可能在游戏中做出不同选择，最后进入AFTER STORY篇的选择有很多种，我们如果把所有光玉的愿望值看成一个集合，那么不同集合就是不同的结局。两个集合不同，当且仅当存在某个元素在一个集合中而不在另一个集合中。
作为游戏内测玩家，滑滑蛋想问你，在知道了
如果不可能进入AFTER STORY篇，请输出
否则输出一共有多少种结局能够进入，由于答案很大，结果需要对
输入描述:
每个测试包含多个测试用例。第一行一个整数，代表有
。
接下来和
，代表一次测试用例。
。
输出描述:
输出
对于每组用例，如果不可能进入AFTER STORY篇，请输出。
否则输出一共有多少种结局能够进入，由于答案很大，结果需要对取模。