Problem Description
Coco the Monkey has contracted a strange disease called 'lemon disease' and is going bananas over lemons. He is going to organize a lemon party for all his monkey friends to get them to be addicted to lemons too! There are K monkeys invited to the party (including Coco) and each monkey is to get an equal (non-negative) number of lemons. Coco is going to harvest lemons for his lemon party from the lemon trees. There are N trees in a row and all of them contain lemons, where the ith tree contains Li lemons. Coco is a lazy monkey, so he wants to pick lemons from a contiguous segment of trees, and will pick all the lemons from every tree he visits. He is also a perfectionist, so he wants the total number of lemons he picks to be able to divide among the monkeys such that there are no lemons left after the division. Guess what, he is also a picky monkey! He wants you to determines the number of distinct ways he can pick lemons from the lemon trees that satisfy his requirements.
Wanna go to Coco's lemon party? Then help him find the answer!
Input
The first line of input contains two space separated integers, N and K.
The second line of input contains N integers, which represent the number of lemons on each tree.
Output
Output one integer, the number of ways.
Limits
1 ≤ N ≤ 5000000. 1 ≤ K ≤ 15. 0 ≤ Li ≤ 1000.
Subtask 1 (15%): 1 ≤ N ≤ 500.
Subtask 2 (21%): 1 ≤ N ≤ 5000.
Subtask 3 (8%): 1 ≤ N ≤ 5000000. K = 1.
Subtask 4 (56%): No other constraints apply.
Subtask 5 (0%): Sample testcases.
Sample Input 1
5 3
2 6 8 5 3
Sample Output 1
4
Explanation for Sample 1
(6), (3), (2, 6, 8, 5), (2, 6, 8, 5, 3).
Credits
HCI Mock NOI 2015 backup problem.