Bài tập

Ta gọi một dãy số nguyên dương \(b_1, b_2, \dots, b_k\) là dãy chia hết nếu \(b_k \le n\) và mỗi phần tử là ước của phần tử đứng ngay sau nó, tức là \(b_i \mid b_{i+1}\) với mọi \(1 \le i < k\). (Do ước không vượt quá bội nên dãy này cũng thoả \(b_1 \le b_2 \le \dots \le b_k \le n\); các phần tử có thể bằng nhau.)

Cho hai số nguyên \(n\) và \(k\). Hãy đếm số dãy chia hết có độ dài đúng \(k\). Vì kết quả có thể rất lớn, in ra phần dư khi chia cho \(10^9 + 7\).

Input

Một dòng chứa hai số nguyên \(n\) và \(k\).

Output

In ra một số nguyên là số dãy chia hết độ dài \(k\), lấy modulo \(10^9 + 7\).

Constraints

• \(1 \le n, k \le 2000\)

Sample Input

6 3

Sample Output

25

Explanation

Với \(n = 6\), \(k = 3\) có \(25\) dãy thoả mãn, chẳng hạn \((1,1,1)\), \((1,2,6)\), \((2,4,4)\), \((3,3,6)\), \((6,6,6)\), ...

Một mảnh vườn hình chữ nhật có hai kích thước \(a\) và \(b\). Người ta đào một cái ao hình tròn bán kính \(R\) nằm hoàn toàn bên trong mảnh vườn. Phần đất còn lại (không tính ao) dùng để trồng rau. Hãy tính diện tích phần đất trồng rau.

Dùng giá trị chính xác của hằng số \(\pi\).

Input

• Một dòng gồm ba số nguyên dương \(a, b, R\) cách nhau bởi dấu cách.

Output

• In ra diện tích phần đất trồng rau, làm tròn đến đúng \(2\) chữ số sau dấu phẩy thập phân.

Constraints

• \(1 \le a, b, R \le 10^6\)
• \(2R \le \min(a, b)\) (ao nằm trọn trong vườn)

Sample Input 1

10 6 2

Sample Output 1

47.43

Explanation

Diện tích vườn là \(60\), diện tích ao là \(4\pi \approx 12.566\), phần còn lại khoảng \(47.434\) nên làm tròn thành \(47.43\).

Có \(N\) con ốc được đánh số từ \(1\) đến \(N\); giá trị của con ốc thứ \(i\) là \(i\). Trên mỗi con ốc phải đặt một dấu \(+\) hoặc \(-\). Đếm số cách đặt dấu sao cho tổng đại số

bằng đúng số nguyên \(S\) cho trước. Hai cách được coi là khác nhau nếu có ít nhất một con ốc được đặt dấu khác nhau.

Vì kết quả có thể rất lớn, in ra phần dư khi chia cho \(998\,244\,353\).

Input

Một dòng chứa hai số nguyên \(N\) và \(S\).

Output

In ra một số nguyên là số cách, lấy modulo \(998\,244\,353\).

Constraints

• \(1 \le N \le 600\).
• \(|S| \le 10^9\).

Sample Input

4 2

Sample Output

2

Explanation

Hai cách là \(-1+2-3+4 = 2\) và \(+1+2+3-4 = 2\).

Với mỗi số nguyên dương \(x\), gọi \(d(x)\) là số ước dương của \(x\). Một dãy số nguyên dương được gọi là dãy đẹp nếu số ước của các phần tử tăng thực sự theo thứ tự trong dãy, tức là \(d(b_1) < d(b_2) < \ldots < d(b_k)\).

Cho dãy \(a_1, a_2, \ldots, a_n\). Ta được xóa một số phần tử (giữ nguyên thứ tự các phần tử còn lại) để phần còn lại là một dãy đẹp. Hãy tìm độ dài lớn nhất của dãy đẹp có thể thu được (tức là số phần tử ít nhất phải xóa là \(n\) trừ đi giá trị này).

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\).

Output

• In ra một số nguyên: số phần tử lớn nhất của dãy đẹp thu được.

Constraints

• \(1 \le n \le 5 \cdot 10^5\)
• \(1 \le a_i \le 10^9\)
• Subtask 1 (20%): \(n \le 20\), \(a_i \le 10^3\).
• Subtask 2 (40%): \(n \le 10^3\), \(a_i \le 10^6\).
• Subtask 3 (20%): \(n \le 5 \cdot 10^4\), \(a_i \le 10^6\).
• Subtask 4 (20%): không có ràng buộc thêm.

Sample Input 1

6
12 2 9 7 30 4

Sample Output 1

3

Explanation

Số ước của từng phần tử là \(6, 2, 3, 2, 8, 3\). Có thể giữ lại các phần tử \(2, 9, 30\) (số ước \(2 < 3 < 8\)) tạo thành dãy đẹp dài \(3\), và không có dãy đẹp nào dài hơn.