小 C 喜欢序列，某一天他随手写下了一个长度为 n 的序列 A，其中 \forall 1\le i\le n，A_i \ge 0。

可惜小 C 不小心弄丢了这个序列，但是他保存下了序列 A 的一些特征。

• l\le \sum_{i=1}^n A_i\le r。

• \bigoplus_{i=1}^n A_i=z。

其中 \bigoplus 为二进制下的异或运算符号，l,r,z 都为常数。

现在小 C 想要知道多少种可能的序列 A 满足他所给出的特征，由于答案可能很大，你只需要告诉小 C 答案对 10^9+7 取模后的值。

输入只有一行，包含四个整数，分别表示 n,l,r,z。

输出只有一行，包含一个整数。

样例 1 解释

所有可能的序列 A 如下：

[2,0,0,0]，[0,2,0,0]，[0,0,2,0]，[0,0,0,2]。

数据规模与约定

• 对于 20\% 的数据，保证 r\le 30。

• 对于 40\% 的数据，保证 n\le 20，r\le 500。

• 对于另 20\% 的数据，保证 n=2。

• 对于另 20\% 的数据，保证 n\le 50。

• 对于 100\% 的数据，保证 1\le n\le 10^{3}，1\le l\le r\le 10^{18}，1\le z\le 10^{18}。