Count Subsequences

Given an array arr, count the subsequences whose MEX lies in the closed interval [l,r]. A subsequence is formed by choosing some positions of the original array, and the empty subsequence also counts; different choices of positions are counted separately even if their value sequences are identical. Output the answer modulo 1,000,000,007.

输入格式

The first line contains n, l, r, and the second line contains n integers arr[i]. Original ranges: 1≤n≤3×10⁵, 0≤arr[i]≤10⁹, 0≤l≤r≤10⁹.

输出格式

Output the number of position subsequences whose MEX lies in [l,r], modulo 1,000,000,007.

样例 1

输入：

3 1 2
0 1 2

输出：

3

样例 2

输入：

2 1 1
0 0

输出：

3

样例 3

输入：

2 0 0
0 0

输出：

1

样例说明

The original problem defines a subsequence as deleting elements at any positions while keeping the order, and explicitly states that the empty subsequence has MEX=0; the source solution's formula (2^c−1) also confirms that equal values at different positions are counted separately.