Với ~p = p_1, p_2, . . . , p_n~ là một hoán vị của ~n~ số nguyên dương từ ~1~ đến ~n~, gọi ~\beta(p)~ là số vị trí ~i~ có ~p_i < i~.

Cho ~n~ và ~k~, hãy đếm số hoán vị ~p~ của ~n~ số từ ~1~ đến ~n~ có ~\beta(p) = k~.

Input

• Dòng đầu ghi số nguyên dương ~n,k~.

Constraints

• ~1 \le n \le 1000, 0 \le k \le n~

Subtask

• ~30\%~ số test: ~n \le 10~
• ~30\%~ số test: ~n \le 20~
• ~40\%~ số test: không ràng buộc gì thêm.

Output

• Ghi một số nguyên duy nhất là số bộ đẳng cấu thứ tự với ~p~ sau khi chia lấy dư cho ~10^9 + 7~.

Sample Input 1

4 1 

Sample Output 1

11

Cho số nguyên dương ~n~.

Đếm số dãy nguyên dương tăng chặt có tổng bằng ~n~. Nói cách khác, hãy đếm số dãy ~a_1, a_2, \dots, a_k~ (~k \geq 1~) gồm các số nguyên dương thỏa mãn ~a_i < a_{i+1}~ với mọi ~1 \leq i < k~ và ~\sum_{i=1}^k a_i = n~.

Vì kết quả có thể rất lớn, hãy in ra kết quả sau khi modulo ~10^9~.

Input

• Gồm một dòng duy nhất chứa số nguyên ~n~ (~1 \leq n \leq 2 \times 10^5~).

Output

• In ra một số nguyên là số dãy nguyên dương tăng chặt có tổng bằng ~n~, modulo ~10^9~.

Subtask

• ~20\%~ số test: ~n \leq 20~.

• ~30\%~ số test khác : ~n \leq 10^3~.

• ~20\%~ số test khác : ~n \leq 10^4~

• ~30\%~ số test còn lại : Không có ràng buộc gì thêm

Example

Input 1

4

Output 1

2

Tương truyền, Ngưu Lang và Chức Nữ yêu nhau thắm thiết đến độ có thể thần giao cách cảm. Để kiểm chứng điều này, Ngọc Hoàng đã đưa cho họ một số nguyên dương ~n~. Hàng năm vào ngày rằm tháng bảy, Ngọc Hoàng sẽ đưa cho họ thêm một số nguyên dương k, sau đó bảo hai người họ mỗi người chọn một tập con của ~{1, 2, . . . , n}~.

Nếu tổng các số Ngưu Lang chọn cộng với tổng các số Chức Nữ chọn bằng đúng ~k~ thì họ sẽ được gặp nhau.

Yêu cầu: Hãy giúp cặp đôi này tính toán số cách chọn khác nhau cho từng năm để họ được gặp nhau. Hai cách chọn được cho là khác nhau nếu tập mà Ngưu Lang chọn là khác nhau trong hai cách đó hoặc tập mà Chức Nữ chọn là khác nhau trong hai cách đó

Input

• Dòng đầu chứa hai số nguyên dương ~n~ ~Q~ với ~Q~ là số năm
• Mỗi dòng trong ~Q~ dòng tiếp theo ghi một số nguyên dương ~k~

Constraints

• ~n,k,Q \le 10^5~

Subtask

• Subtask ~1~ ~(25\%)~: ~k \le 500~
• Subtask ~2~ ~(25\%)~: ~n \le 500~
• Subtask ~3~ ~(25\%)~: ~Q \le 500~
• Subtask ~4~ ~(25\%)~: Không có ràng buộc gì thêm.

Output

• Ghi ~Q~ dòng là số cách chọn tương ứng cho ~Q~ năm, sau khi chia lấy dư cho ~10^9 + 7~

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

2
3
6
9
14

Cho dãy ~a_1, a_2, \dots, a_n~ gồm các số nguyên dương.

Một hoán vị ~p_1, p_2, \dots, p_n~ của các số ~1, 2, \dots, n~ được coi là đẹp nếu không tồn tại vị trí ~i~ nào thỏa mãn ~1 \leq i < n~ và ~a_{p_i} \times a_{p_{i+1}}~ là số chính phương.

Hãy đếm số hoán vị đẹp như vậy, modulo ~998244353~.

Input

• Dòng đầu chứa số nguyên ~n~ (~1 \leq n \leq 300~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 10^9~).

Output

• In ra một số nguyên là số hoán vị đẹp, modulo ~998244353~.

Example

Input 1

4
1 2 3 4

Output 1

12

Xét đoạn mã sau:

int bubbleSort(int arr[], int n) {
  int cnt = 0;
  for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
              std::swap(arr[j], arr[j + 1]);
              cnt++;
          }
      }
  }
  return cnt;
}

Cho hai số nguyên dương ~n~ và ~k~, hãy đếm số bộ hoán vị độ dài ~n~ sao cho số phép thực hiện hàm swap trong code Bubble Sort trên đúng bằng ~k~.

Nói cách khác, gọi ~p(n)~ là hoán vị độ dài ~n~, hãy đếm các ~p(n)~ sao cho bubbleSort(p(n),n) = k.

Input

• Gồm một dòng chứa hai số nguyên ~n~ và ~k~. ~(n \le 10^5, k \le min(10^5, \frac{n\times (n-1)}{2})~

Output

• In ra một số nguyên là số hoán vị thỏa mãn, modulo ~10^9+7~.

Subtask

• ~30\%~ số test: ~n,k \leq 400~.

• ~30\%~ số test khác : ~n,k \le 4000~

• ~40\%~ số test còn lại : Không có ràng buộc gì thêm.

Example

Input 1

4 3

Output 1

6