Equal Share

4

1 votes
Problem

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)

Time Limit: 1
Memory Limit: 32
Source Limit:
Explanation

There are two ways to divide into 3 regions at positions: (4, 8) or (4, 9).

Editor Image

?