Ta quy ước một dãy con không giảm của dãy \(B_1\), \(B_2\),..., \(B_m\) là một bộ chỉ số \((j_1,j_2,...,j_k)\) sao cho \(1\leq j_1<j_2<...<j_k\leq m\) và \(B_{j_1}\leq B_{j_2}\leq ... \leq B_{j_k}\).

Bạn hãy viết chương trình đọc vào mảng \(A\) gồm \(N\) số nguyên thuộc đoạn \([1, K]\) và \(Q\) truy vấn. Truy vấn thứ \(i\) cho biết hai chỉ số \(l_i\), \(r_i\) \((1\leq l_i\leq r_i\leq N)\) và bạn phải xác định số lượng dãy con không giảm của đoạn con \(A[l_i...r_i]\) (tính cả dãy con rỗng). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(10^9+7\).

Input

Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(1\leq N\leq 5\cdot 10^4\), \(1\leq K\leq 20\)).

Dòng tiếp theo chứa \(N\) số nguyên \(A_1\), \(A_2\),..., \(A_N\) \((1\leq A_i\leq K)\).

Dòng tiếp theo chứa số nguyên \(Q\) \((1\leq Q\leq 2\cdot 10^5)\).

Dòng thứ \(i\) trong \(Q\) dòng tiếp chứa hai số nguyên dương \(l_i\) và \(r_i\).

Output

In ra \(Q\) dòng, mỗi dòng chứa một số nguyên là câu trả lời cho câu hỏi tương ứng.

Ví dụ

Sample input

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

Sample output

3
4
20

Giải thích

Với truy vấn đầu tiên, ba dãy con không giảm tìm được là \(()\), \((2)\), và \((3)\). \((2,3)\) không phải là một dãy con không giảm vì \(A_2>A_3\).

Với truy vấn thứ nhì, bốn dãy con không giảm tìm được là \(()\), \((4)\), \((5)\), và \((4,5)\).