Tổng K tập con

Cho số nguyên dương \(n\). Xét tập \(\Omega_n = \{1, 2, \ldots, n\}\). Một bộ bậc \(k\) là một dãy có thứ tự gồm \(k\) tập con \((X_1, X_2, \ldots, X_k)\), trong đó với mọi \(1 \le i \le k\) thì \(X_i \subseteq \Omega_n\). Các tập con có thể rỗng, có thể trùng nhau, và thứ tự của các tập con trong dãy là quan trọng.

Trọng lượng của một bộ bậc \(k\) được định nghĩa là

Nếu một phần tử xuất hiện trong nhiều tập con khác nhau thì nó được tính nhiều lần.

Bạn cần trả lời \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên \(k\) và \(w\). Hãy đếm số bộ bậc \(k\) có trọng lượng đúng bằng \(w\). Vì đáp án có thể rất lớn nên hãy in kết quả modulo \(10^9 + 7\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(Q\) (\(1 \le n \le 10^9\), \(1 \le Q \le 2 \times 10^5\)).

• Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(k\) và \(w\) (\(1 \le k \le 10\), \(0 \le w \le 10^5\)) --- tương ứng với một truy vấn.

Ràng buộc:

• Subtask 1 (10 điểm): \(n \le 20\), \(Q \le 100\), \(k = 1\), \(w \le 200\).

• Subtask 2 (20 điểm): \(n \le 10^5\), \(k = 1\), \(w \le 10^5\).

• Subtask 3 (25 điểm): \(n \le 10^5\), \(k \le 2\), \(w \le 10^5\).

• Subtask 4 (45 điểm): Không có ràng buộc bổ sung.

Output

Với mỗi truy vấn, in ra một dòng duy nhất là số bộ bậc \(k\) có trọng lượng đúng bằng \(w\), modulo \(10^9 + 7\).

Example

Input:

3 6
1 0
1 3
1 6
2 3
2 6
3 6

Output:

1
2
1
6
10
43

Note

Với \(n = 3\), ta có \(\Omega_3 = \{1, 2, 3\}\).

Với truy vấn \((k, w) = (1, 0)\): chỉ có một tập con duy nhất có trọng lượng \(0\) là tập rỗng, nên đáp án là \(1\).

Với truy vấn \((k, w) = (1, 3)\): có hai tập con của \(\Omega_3\) có trọng lượng \(3\), đó là \(\{3\}\) và \(\{1, 2\}\), nên đáp án là \(2\).

Với truy vấn \((k, w) = (1, 6)\): chỉ có một tập con có trọng lượng \(6\), đó là \(\{1, 2, 3\}\), nên đáp án là \(1\).

Với truy vấn \((k, w) = (3, 6)\): có \(43\) bộ ba tập con \((X_1, X_2, X_3)\) của \(\Omega_3\) (có thể rỗng, có thể trùng nhau) sao cho tổng trọng lượng của ba tập con bằng \(6\).