Link bài gốc:

http://vnoi.info/problems/show/QTDIVSEQ/

Đề bài:

Cho dãy A gồm n số nguyên A1, A2,… , Anvà 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 A1, A2,… , An, 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^9+ 7)

Giới hạn

1 ≤ k ≤ n ≤ 10^6

|Ai| ≤ 10^9 (1 ≤ i ≤ n)

Ví dụ:

Input:

8 3
-2 6 -1 3 -2 4 5 -1

Output:

2

Solution:

Tham khảo tại: http://viahold.com/ROl

Code:

Tham khảo tại: http://viahold.com/S0J