Ông Sắc là một doanh nhân đại tài, ông đã xây dựng nên sự nghiệp của ông từ con số 1. Trong một khóa dạy kinh doanh, ông đã đưa ra bài toán cho những học trò của mình dựa trên trải nghiệm của mình:

Dãy \(a\) ban đầu chỉ có duy nhất phần tử \(1\). Chọn dãy con từ dãy \(a\) và chèn vào dãy \(a\) tổng của các phần tử trong dãy con ấy. Nói cách khác chọn \(k\) chỉ số khác nhau \(i_1, i_2, ..., i_k\) và chèn vào dãy a một giá trị \(a_{i_1} + a_{i_2} + ... + a_{i_k}\).

Cho trước một dãy \(b\). Hỏi từ dãy \(a\) có tạo được nên dãy \(b\) không?

Input

• Dòng đầu tiên chứa \(t\) là số lượng bộ dữ liệu khác nhau \((1 \le t \le 20)\).
• \(t\) nhóm sau, mỗi số gồm \(2\) dòng:
  • Dòng đầu chứa số nguyên dương \(n\) (\(n \le 10^5\));
  • Dòng tiếp theo chứa \(n\) số \(b_1, b_2, ..., b_n\) (\(b_i \le 2 * 10^5\)).

Output

• In ra \(\text{YES}\) nếu đúng yêu cầu đề bài, ngược lại in ra \(\text{NO}\).

Scoring

• Subtask 1: \(50\%\) số test tương ứng với \(50\%\) số điểm có \(n \le 10^3\), \(b_i \le 10^3\).
• Subtask 2: \(50\%\) số test tương ứng với \(50\%\) số điểm không có ràng buộc gì thêm.

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

YES
YES
NO
NO
YES

Ông Liêm là 1 kẻ trộm bò lừng lẫy, khét tiếng lúc bấy giờ khiến các chủ trang trại nghe tên là hoảng sợ. Ông Hai là 1 chủ trang trại bò lớn tại làng Hòn. Bỗng một ngày nghe tin ông Liêm đã tới làng của mình, ông Hai bèn nghĩ ra cách để đối phó với tên trộm đặc biệt này. Các chuồng bò của ông Hai được đánh số từ \(1\) đến \(n\), có \(m\) công tắc nối giữa \(2\) chuồng. Ban đầu các chuồng bò đều đóng cửa. Nếu ai tác động vào công tắc của một chuồng bất kì thì tất cả các chuồng nối với nó đều thay đổi trạng thái cánh cửa (đóng thành mở, mở thành đóng). Ông Liêm là 1 kẻ trộm tham lam, ông muốn một khi đã trộm thì phải trộm cho hết, do đó ông Liêm nhờ bạn tìm số công tắc tối thiểu cần tác động để mở được tất cả các chuồng bò của ông Hai.
Yêu cầu: Hãy tìm số tác động ít nhất để các cách cửa chuồng bò đều mở? Giả thiết là luôn có phương án để mở tất cả các chuồng bò.

Input

• Dòng 1 chứa 2 số nguyên dương \(n\) và \(m\) (\(1 \le n \le 40\), \(1 \le m \le \frac{n(n-1)}{2}\));
• \(m\) dòng sau, mỗi dòng ghi 1 cặp số \(a\) và \(b\) tương ứng có một công tắc nối giữa hai chuồng \(a\) và \(b\). Các dây điện nối với công tắc là dây điện hai chiều. Dữ liệu đầu vào được đảm bảo rằng mỗi cặp chuồng \((a, b)\) có duy nhất một công tắc nối giữa chúng.

Output

• Một số duy nhất là số lần tác động ít nhất.

Scoring

• Subtask 1: \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \le 22\);
• Subtask 2: \(70\%\) số test tương ứng với \(70\%\) số điểm không có ràng buộc gì thêm

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

3

Cho hai số nguyên dương \(n, k\). Hãy tính giá trị của biểu thức:

\(S = \lceil \frac{n}{1} \rceil + \lceil \frac{n}{2} \rceil + \lceil \frac{n}{3} \rceil + \cdots + \lceil \frac{n}{k-1} \rceil + \lceil \frac{n}{k} \rceil\)

Ở đây, \(\lceil x \rceil\) là số nguyên nhỏ nhất không nhỏ hơn \(x\).

Input

• Một dòng chứa \(2\) số nguyên dương \(n, k\) \((1 \le k \le n \le 10^{12})\)

Output

• Giá trị của biểu thức \(S\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^6\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 10^{12}\).

Example

2 2

3

5 3

10

Cho bàn cờ vua \(n \times m\) ô. Đếm số cách đặt các quân mã (số lượng tùy ý) lên bàn cờ sao cho chúng đôi một không ăn nhau. Hai cách được coi là khác nhau nếu tồn tại một ô được đặt trong cách này không được đặt trong cách kia.

Input

• Chỉ một dòng duy nhất chứa số tự nhiên \(n\), \(m\) (\(n \times m \le 10000\)).

Output

• Gồm một số nguyên duy nhất là số cách đặt chia lấy dư cho $ 1000000007 $.

Constraints

• Subtask 1 ($ 30\% $ test): \(n \times m \le 4\)
• Subtask 2 ($ 70\% $ test): Không có ràng buộc thêm

Example

2 3

36