5611. T4 序列（sequence）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 小 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$。 ## 输出格式 输出只有一行，包含一个整数。 ## 输入 ```in1 4 1 3 2 ``` ## 输出 ```out1 4 ``` 样例 1 解释 所有可能的序列 $A$ 如下： $[2,0,0,0]$，$[0,2,0,0]$，$[0,0,2,0]$，$[0,0,0,2]$。 ```in2 5 1 5 2 ``` ```out2 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}$。