Minh và Quang cùng làm một bài toán khá hay được Nam đố liên quan đến tổ hợp. Bài toán ban đầu như sau:

Hàm ~S(i, j)~ được định nghĩa như sau: ~S(i, j) = \begin{cases} 0 & \text{nếu } i < j \\ \binom{i}{j} & \text{nếu } i \ge j \end{cases}~ với ~\binom{n}{r}~ là tổ hợp chập ~r~ của ~n~.

Cho ba số nguyên dương ~r, u, v~. Hàm ~A(r, u, v)~ được định nghĩa như sau: ~A(r, u, v) = \sum_{i=u}^{v} S(i, r)~

Vì Quang thấy bài này khá dễ, nên đã đề nghị Minh nâng độ khó của bài lên như sau: Cho mảng ~A~ gồm ~n~ phần tử ~a_1, a_2, a_3, ..., a_n~ và cho ba số nguyên dương ~r, u, v~. Hãy đếm số dãy ~b~ gồm ~r~ phần tử sao cho thoả mãn các điều kiện sau:

• ~1 \le b_1 < b_2 < ... < b_r \le n~.

• ~u \le a_{b_1} \& a_{b_2} \& ... \& a_{b_r} \le v~ với ~\&~ là ký hiệu của phép AND trong xử lý bit.

Minh sau một phút suy nghĩ vẫn cảm thấy không khó, nên đã đề nghị Quang nâng tầm thêm bài khó hơn nữa như sau: Cho mảng ~A~ gồm ~n~ phần tử ~a_1, a_2, a_3, ..., a_n~, và cho hai số nguyên dương ~l, r~. Minh đề nghị cho thêm ~q~ truy vấn, truy vấn thứ ~i~ thuộc một trong hai loại như sau:

• ~1 \ u_i \ v_i \ (0 \le u_i \le v_i)~: Hãy đếm số dãy ~b~ gồm ~k~ phần tử sao cho thoả mãn các điều kiện sau:

  • ~l \le k \le r~.

  • ~1 \le b_1 < b_2 < ... < b_k \le n~.

  • ~u_i \le a_{b_1} \& a_{b_2} \& ... \& a_{b_k} \le v_i~ với ~\&~ là ký hiệu của phép toán AND trong xử lý bit.

• ~2 \ u_i \ v_i \ (0 \le u_i \le v_i)~: Hãy đếm số dãy ~b~ gồm ~k~ phần tử sao cho thoả mãn các điều kiện sau:

  • ~l \le k \le r~.

  • ~1 \le b_1 < b_2 < ... < b_k \le n~.

  • ~u_i \le a_{b_1} | a_{b_2} | ... | a_{b_k} \le v_i~ với ~|~ là ký hiệu của phép toán OR trong xử lý bit.

Sau vài phút suy nghĩ thì Quang đồng ý cùng Minh làm bài này. Nhưng có một trở ngại là Minh và Quang chưa có nhiều kinh nghiệm về các bài toán xử lí bit phức tạp, nên khá bối rối. Minh và Quang đều đi hỏi Nam, và Nam cũng khá bối rối với bài toán này.

Yêu cầu: Hãy giúp Minh, Quang và Nam thoát khỏi sự bối rối bằng cách giải quyết bài toán đó.

Input

Gồm ~q+2~ dòng:

• Dòng đầu tiên chứa bốn số nguyên dương ~n, q, l, r~ (~1 \le l \le r \le n~).

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa truy vấn thuộc một trong hai loại trên.

Output

Gồm ~q~ dòng, dòng thứ ~i~ ghi ra một số nguyên không âm duy nhất là phần dư của kết quả của truy vấn thứ ~i~ khi chia cho số ~10^9 + 7~.

Scoring

Sample Input 1

4 2 1 2
2 3 5 6
1 1 2
2 0 4

Sample Output 1

5
3

Notes

• Với truy vấn thứ 1: Có 5 dãy thoả mãn là (theo vị trí): ~(1), (1, 2), (1, 4), (2, 3), (2, 4)~

• Với truy vấn thứ 2: Có 3 dãy thoả mãn là (theo vị trí): ~(1), (2), (1, 2)~