4353: T4 序列（sequence）
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
## T4 序列（sequence）
### 题目描述
小 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$。
输出
### 输出格式
输出只有一行，包含一个整数。
样例输入 复制
4 1 3 2样例输出 复制
4提示
### 样例 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}$。