Giải bài trực tuyến

Cho dãy A gồm n số nguyên A₁, A₂,… , A_n và số nguyên dương k. Hỏi có bao nhiêu cách chia dãy A thành k đoạn liên tiếp có tổng bằng nhau (mỗi đoạn có ít nhất 1 phần tử) ?

Input

-          Dòng đầu : hai số nguyên dương n và k, cách nhau một khoảng trắng

-          Dòng hai : n số nguyên A₁, A₂,… , A_n, mỗi số cách nhau một khoảng trắng

Output

-          Số nguyên S là số cách chia thỏa yêu cầu đề bài. Do kết quả có thể rất lớn, bạn chỉ cần in ra S mod 1000000007 (10⁹ + 7)

Giới hạn :

-          1 ≤ k ≤ n ≤ 10⁶

-          |A_i| ≤ 10⁹ (1 ≤ i ≤ n)

Ví dụ :

Input:
8 3
-2 6 -1 3 -2 4 5 -1
Output:
2