题目描述

小 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 输入

4 1 3 2

样例 1 输出

4

样例 1 解释

所有可能的序列 $A$ 如下：

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

样例 2 输入

5 1 5 2

样例 2 输出

55

其余样例见下发文件。

数据规模与约定

• 对于 $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}$。