Our superhero, Alpha Maria has N gems fixed on a line on the ground. She has K sisters and she would like to split the line into K regions using dividers such that all regions have the same amount of gems. In how many ways can she put the dividers?

For instance, she has 6 gems at positions 2, 3, 5, 7, 10, 15 and she has 3 sisters. Then she can put the dividers in two different ways: at positions (4, 8) or (4, 9).

Gems and dividers can only be at integer positions and they cannot be at the same position. It is guaranteed that N is divisible by K.

Constraints:

• 3 < N <= 100,000
• 1< K < N
• N mod K = 0

Input format:

• First line is composed of two integers: N and K
• Second line is composed of N space separated integers; the coordinates of the points. Each integer will be in the interval (-1,000,000 ; 1,000,000)

Output format:

• Consist of only one line; the number of ways to divide into K regions modulo 1,000,007.

(Problem credit: Fatih Gelgi)