Bài tập

Cho một xâu \(S\) độ dài \(N\) chỉ gồm hai loại ký tự A và B. Hãy đếm số đoạn con liên tiếp của \(S\) (tính theo vị trí bắt đầu và kết thúc, hai đoạn ở vị trí khác nhau được tính là khác nhau) thỏa mãn đồng thời:

• Độ dài \(L\) của đoạn thỏa \(1 \le L \le M\);
• Trong đoạn có đúng \(K\) ký tự A.

Input

• Dòng 1: ba số nguyên \(N\), \(M\), \(K\).
• Dòng 2: xâu \(S\) gồm \(N\) ký tự.

Output

• In ra một số nguyên là số đoạn con thỏa mãn.

Constraints

• \(1 \le N < 255\)
• \(1 \le K \le M \le 14\)

Sample Input

10 4 2
BAABABAAAB

Sample Output

12

Chủ trại có \(N\) con trâu, con thứ \(i\) cày được đúng \(a_i\) đơn vị diện tích. Hãy đếm số cách chọn một tập con các con trâu có tổng diện tích cày được đúng bằng \(S\). Hai tập được xem là khác nhau nếu có một con trâu thuộc tập này mà không thuộc tập kia (các con trâu được phân biệt theo chỉ số, kể cả khi \(a_i\) bằng nhau). Đồng thời hãy cho biết số con trâu ít nhất trong một tập như vậy.

Input

• Dòng 1: hai số nguyên \(N\) và \(S\).
• Dòng 2: \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• Nếu không có cách chọn nào, in KHONG CHON DUOC.
• Ngược lại in hai số cách nhau một dấu cách: số cách chọn và số con trâu ít nhất của một cách chọn.

Constraints

• \(1 \le N \le 32\)
• \(1 \le S \le 3.2 \times 10^{10}\)
• \(1 \le a_i \le 10^9\)

Sample Input 1

6 7
1 2 3 4 5 6

Sample Output 1

4 2

Sample Input 2

5 100
3 8 20 5 9

Sample Output 2

KHONG CHON DUOC

Explanation

Ở ví dụ 1 có 4 tập: \(\{1,6\}\), \(\{2,5\}\), \(\{3,4\}\), \(\{1,2,4\}\); tập nhỏ nhất có 2 con.

Cho số nguyên dương \(K\) và \(m\) số nguyên dương \(a_1, a_2, \dots, a_m\). Đếm xem trong các số \(1, 2, \dots, K\) có bao nhiêu số chia hết cho ít nhất một trong các số \(a_i\).

Input

• Dòng đầu chứa hai số nguyên \(K\) và \(m\).
• Dòng thứ hai chứa \(m\) số nguyên \(a_1, \dots, a_m\).

Output

In ra một số nguyên là đáp số.

Constraints

• \(1 \le K \le 10^9\), \(1 \le m \le 15\).
• \(1 \le a_i \le 10^9\).

Sample Input

30 3
4 6 10

Sample Output

11

Explanation

Có \(7\) bội của \(4\), \(5\) bội của \(6\), \(3\) bội của \(10\); trừ đi các số bị đếm hai lần (\(12\) và \(24\); \(20\); \(30\)) ta được \(7+5+3-2-1-1 = 11\).

Ba số nguyên dương \((A, B, C)\) được gọi là một bộ ba đẹp của \(N\) nếu \(A \times B + C = N\). Hai bộ khác nhau về thứ tự các thành phần được tính là khác nhau. Ví dụ với \(N = 4\) có \(5\) bộ ba đẹp: \((1,1,3)\), \((1,2,2)\), \((1,3,1)\), \((2,1,2)\), \((3,1,1)\).

Cho \(N\), hãy đếm số bộ ba đẹp.

Input

• Một số nguyên dương \(N\).

Output

• In ra số lượng bộ ba đẹp.

Constraints

• \(1 \le N \le 10^6\)

Sample Input

6

Sample Output

10

Explanation

Với \(C = 1\): \(A \times B = 5\) có 2 cách. \(C = 2\): tích bằng 4 có 3 cách. \(C = 3\): tích bằng 3 có 2 cách. \(C = 4\): tích bằng 2 có 2 cách. \(C = 5\): tích bằng 1 có 1 cách. Tổng cộng \(2+3+2+2+1 = 10\).