小AA的数列
题号:NC14414
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

小AA找到了一个数列,她想要知道这个数列中所有长度为偶数的区间异或和之和 。
后来她发现这个问题太简单了,于是她加了一个限制,要求区间长度在[L,R]之间,
然后她就不会了。。。
请你告诉她问题的答案。

输入描述:

第一行三个数 n, L, R(n<=105,1<=L<=R<=n)
第二行n个数表示这个数列。(ai<=109)

输出描述:

输出一行表示答案,由于答案可能很大,请输出答案模109+7的值。
示例1

输入

复制
5 1 5
1 2 3 4 5

输出

复制
16
示例2

输入

复制
4 1 4
4 4 4 4

输出

复制
0