Dãy Con Không Giảm

Cho một dãy gồm $N$ số nguyên, mỗi số trong khoảng $[1,K]$. Có $Q$ truy vấn: với mỗi truy vấn $(L,R)$, đếm số dãy con không giảm (kể cả dãy rỗng) trong đoạn vị trí $L$ đến $R$, modulo ${10}^9+7$.

Dãy con là một tập con các phần tử lấy theo thứ tự ban đầu (không nhất thiết liên tiếp). Dãy con không giảm là dãy con mà mỗi phần tử $\le$ phần tử tiếp theo.

Dữ liệu vào

• Dòng 1: $N$ và $K$ ($1\le N\le 5\times {10}^4$, $1\le K\le 20$).
• Dòng 2: $N$ số nguyên $a_1,a_2,\dots ,a_N$ ($1\le a_i\le K$).
• Dòng 3: $Q$ ($1\le Q\le 2\times {10}^5$).
• $Q$ dòng tiếp theo: mỗi dòng gồm $L_i$ và $R_i$ ($1\le L_i\le R_i\le N$).

Dữ liệu ra

Với mỗi truy vấn, in kết quả trên một dòng.

Ví dụ