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:
Input format:
Output format:
Consist of only one line; the number of ways to divide into K regions modulo 1,000,007.
(Problem credit: Fatih Gelgi)
There are two ways to divide into 3 regions at positions: (4, 8) or (4, 9).