在ICPC比赛训练期间,“Jee You See”团队偶然发现了一个非常基本的计数问题。经过多次“答案错误”的判决后,他们最终决定放弃并销毁关闭电脑。现在他们需要你的帮助来解决这个问题。
给你 4 个整数 $$$n$$$、$$$l$$$、$$$r$$$ 和 $$$z$$$。计算长度为 $$$n$$$ 且包含非负整数的数组 $$$a$$$ 的数量,如下所示:
- $$$l\le a_1+a_2+\ldots+a_n\le r$$$,以及
- $$$a_1\oplus a_2 \oplus \ldots\oplus a_n=z$$$,其中 $$$\oplus$$$ 表示按位异或运算。
由于答案可能很大,请打印 $$$10^9+7$$$ 的模。
输入
唯一的一行包含四个整数 $$$n$$$、$$$l$$$、$$$r$$$、$$$z$$$ ($$$1 \le n \le 1000$$$、$$$1\le l\le r\le 10^{18}$$$、$$$1\le z\le 10^{18}$$$)。
输出
打印满足所有要求的数组 $$$a$$$ 模 $$$10^9+7$$$ 的数量。
示例
输入 #1
3 1 5 1
输出 #1
13
输入 #2
4 1 3 2
输出 #2
4
输入 #3
2 1 100000 15629
输出 #3
49152
输入#4
100 56 89 66
输出#4
981727503
注意
以下数组满足第一个样本的条件:
- $$$[1, 0, 0]$$$;
- $$$[0, 1, 0]$$$;
- $$$[3, 2, 0]$$$;
- $$$[2, 3, 0]$$$;
- $$$[0, 0, 1]$$$;
- $$$[1, 1, 1]$$$;
- $$$[2, 2, 1]$$$;
- $$$[3, 0, 2]$$$;
- $$$[2, 1, 2]$$$;
- $$$[1, 2, 2]$$$;
- $$$[0, 3, 2]$$$;
- $$$[2, 0, 3]$$$;
- $$$[0, 2, 3]$$$.
以下数组满足第二个示例的条件:
- $$$[2, 0, 0, 0]$$$;
- $$$[0, 2, 0, 0]$$$;
- $$$[0, 0, 2, 0]$$$;
- $$$[0, 0, 0, 2]$$$.