Mảng con đặc biệt

Trong một buổi giao lưu truyền thống, FullHouse Dev được thử thách với một bài toán thú vị về mảng. Bài toán này không chỉ kiểm tra kỹ năng lập trình của họ mà còn đòi hỏi sự hiểu biết sâu sắc về số học. Với tinh thần ham học hỏi, FullHouse Dev đã bắt tay vào giải quyết bài toán này.

Bài toán

Cho một mảng \(A\) gồm \(N\) số nguyên và một số nguyên \(K\). Nhiệm vụ của FullHouse Dev là tìm số lượng mảng con có số lượng số nguyên tố nhỏ hơn hoặc bằng \(K\).

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).
• Dòng thứ hai chứa \(N\) số nguyên - các phần tử của mảng \(A\).

OUTPUT FORMAT:

• In ra số lượng mảng con thỏa mãn điều kiện.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq K \leq N\)
• \(1 \leq A[i] \leq 10^9\)

Ví dụ

INPUT

5 1
2 3 4 5 9

OUTPUT

9

Giải thích

Các mảng con có số lượng số nguyên tố nhỏ hơn hoặc bằng 1 là:

• [4], [9], [4, 5], [4, 9], [5, 9], [4, 5, 9]
• [2], [3], [2, 3]

Tổng cộng có 9 mảng con thỏa mãn điều kiện.

Giới hạn thời gian: 2 giây

Giới hạn bộ nhớ: 256 MB