#18 「 共同喜好 」

统计

R君有一个长度为n的序列S。

R君十分喜欢AND位运算,同时有一个品味的区间$[a,b]$,如果S序列的一个子区间满足$a \le (S_L\ and\ S_{L+1}\ and\ \ldots\ and\ S_R) \le b$,那么这个区间就被R君喜欢。

Z君十分喜欢OR位运算,同时有一个品味的区间$[c,d]$,如果S序列的一个子区间满足$c \le (S_L\ or\ S_{L+1}\ or\ \ldots\ or\ S_R) \le d$ ,那么这个区间就被R君喜欢。

and、or为位运算的与和或。

求S有多少个R君和Z君共同喜好的区间。

为了避免64位整数输出,请将答案对$10^9 + 7$取模。

输入格式

输入一共两行。

第一行五个数字n,a,b,c,d。

第二行n个数字,表示S序列。

输出格式

输出一行一个整数,表示答案。

样例数据

input

3 2 2 3 3
2 3 3

output

2

样例解释

AND[1..1] = 2, OR[1..1] = 2

AND[1..2] = 2, OR[1..2] = 3

AND[1..3] = 2, OR[1..3] = 3

AND[2..2] = 3, OR[2..2] = 3

AND[2..3] = 3, OR[2..3] = 3

AND[3..3] = 3, OR[3..3] = 3

只有[1..2]与[1..3]合法,答案为2。

数据规模与约定

$1 \le n \le 10^5, 1 \le a \le b \le 10^6, 1 \le c \le d \le 10^6, 0 \le S_i \le 10^6$。

时间限制:1s

空间限制:512MB

Author: zrt