Mike has an array A of N integers. beauty of segment (sub array) A[l,r] is defined as XOR of all elements in the segment A[l,r]. but mike likes only those segments which has length at least x and at most y.
Now mike is curious to know, what is the total beauty of all the segments which he likes. but he needs your help to do so.
Input:
first line will contains three integers N, x and y. Next line will contain array A of N integers.
Output:
output single integer which is answer to the problem. Since the answer can be large output it modulo 10^9 + 7, that is, you need to output the remainder of division of the actual answer by 10^9 + 7.
limits:
1 <= N <= 1000000
1 <= x <= y <= N
0 <= A[i] <= 1000000000
Setter : Mohib Manva
following are the segments of given array:
1) { 1 } has beauty = 1.
2) { 1, 2 } has beauty = 1 ^ 2 = 3.
3) { 1, 2, 3} Mike dislikes this sub array because it has length 3, which is greater than y.
4) { 2 } has beauty = 2.
5) { 2, 3 } has beauty = 2 ^ 3 = 1.
6) { 3 } has beauty = 3.
so, total beauty = 1 + 3 + 2 + 1 + 3 = 10
