(combi.*)

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) = \left\{ \begin{aligned} 0\ \ \ ,\ \ & nếu\ i < j \\ \binom{i}{j},\ \ & nếu\ i \geq j \end{aligned} \right.\ \]

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},\ldots,\ 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 \leq b_{1} < b_{2} < \ \ldots\ < b_{r} \leq n.\)

• \(u \leq a_{b_{1}}\ \&\ a_{b_{2}}\ \&\ldots\&\ a_{b_{r}} \leq 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},\ldots,\ 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 \leq u_{i} \leq 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 \leq k \leq r\).

  • \(1 \leq b_{1} < b_{2} < \ \ldots\ < b_{k} \leq n.\)

  • \(u_{i} \leq a_{b_{1}}\ \&\ a_{b_{2}}\ \&\ldots\&\ a_{b_{k}} \leq 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 \leq u_{i} \leq 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 \leq k \leq r\).

  • \(1 \leq b_{1} < b_{2} < \ \ldots\ < b_{k} \leq n.\)

  • \(u_{i} \leq a_{b_{1}}\ |\ a_{b_{2}}\ |\ldots|\ a_{b_{k}} \leq 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 đó.

Dữ liệu vào: 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 \leq l \leq r \leq n)\).

• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_{1},\ a_{2},\ldots,\ 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.

Kết quả: 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\).

Ví dụ:

Input	Output	Giải thích
4 2 1 2 2 3 5 6 1 1 2 2 0 4	5 3	- 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)

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài thoả mãn điều kiện: \(n,q \leq {2.10}^{2};\) \(l = 1,\ r = n;\) \(a_{i} < 2^{8}\) với \(1 \leq i \leq n\); \(v_{i} < 2^{8}\) với \(1 \leq i \leq q\).

• 30% số test khác ứng với 30% số điểm của bài thoả mãn điều kiện: \(n \leq 10^{6},q \leq {3.10}^{5};\ l = 1,\ r = n;\) \(a_{i} < 2^{19}\) với \(1 \leq i \leq n\); \(v_{i} < 2^{19}\) với \(1 \leq i \leq q\).

• 50% số test còn lại ứng với 50% số điểm của bài thoả mãn điều kiện: \(n \leq 10^{6},q \leq {3.10}^{5};\ a_{i} < 2^{19}\) với \(1 \leq i \leq n\); \(v_{i} < 2^{19}\) với \(1 \leq i \leq q\).