QTDIVSEQ - Chia đoạn

Giới hạn

• Thời gian: 1.0s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

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

---

• Người up: kata69
• Nguồn bài: Thi HSG tỉnh Bình Phước 2014 - 2015