Gần đây Bessie tham gia một kỳ thi USACO và gặp bài toán sau. Tất nhiên, Bessie biết cách giải nó. Còn bạn thì sao?

Xét một dãy \(A_1,A_2,\ldots,A_N\) có độ dài \(N\) (\(1\le N\le 5\cdot 10^4\)), chỉ gồm các số nguyên trong khoảng \(1\ldots K\) (\(1\le K\le 20\)). Bạn được cho \(Q\) truy vấn (\(1\le Q\le 2\cdot 10^5\)) có dạng \([L_i,R_i]\) (\(1\le L_i\le R_i\le N\)). Với mỗi truy vấn, hãy tính số dãy con không giảm của \(A_{L_i},A_{L_i+1},\ldots,A_{R_i}\) theo modulo \(10^9+7\).

Một dãy con không giảm của \(A_L,\ldots,A_R\) là một tập hợp chỉ số \((j_1,j_2,\ldots,j_x)\) sao cho \(L\le j_1<j_2<\cdots<j_x\le R\) và \(A_{j_1}\le A_{j_2}\le\cdots\le A_{j_x}\). Hãy nhớ tính cả dãy con rỗng!

Phân nhóm

• Các test từ \(2\) đến \(3\) thỏa mãn \(N\le 1000\).
• Các test từ \(4\) đến \(6\) thỏa mãn \(K\le 5\).
• Các test từ \(7\) đến \(9\) thỏa mãn \(Q\le 10^5\).
• Các test từ \(10\) đến \(12\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp nondec.in.

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.

Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\), cách nhau bởi dấu cách.

Dòng thứ ba chứa một số nguyên \(Q\).

Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(L_i\) và \(R_i\), cách nhau bởi dấu cách.

Dữ liệu ra

Với mỗi truy vấn \([L_i,R_i]\), ghi ra tệp nondec.out trên một dòng mới số dãy con không giảm của \(A_{L_i},A_{L_i+1},\ldots,A_{R_i}\) theo modulo \(10^9+7\).

Ví dụ

5 2
1 2 1 1 2
3
2 3
4 5
1 5

3
4
20

Nguồn

• Kỳ thi: USACO 2020 January Contest, Platinum
• Tên bài: Non-Decreasing Subsequences
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=997
• Tác giả đề: Benjamin Qi