Mr Makor And His Friends

Mr Makor has a set S of n integers. He calls a sequence of length k special if every element of the sequence is taken from the set S (the sequence can have the same element multiple numbers of times) and the summation of every two consecutive elements is divisible by m. More formally, if A is a sequence of length k and Ai is the ith element of the sequence then sequence A will be special if Ai ϵ S for every 1 ≤ i ≤ k and m | (Ai + Ai+1) (means m divides Ai + Ai+1) for every 1 ≤ i < k. Mr Makor was thinking about giving some sequences to his friends as a gift. So he thought about the number of distinct special sequences he can make. As this number may be quite large, you need to find its remainder modulo (109+7).


This is a companion discussion topic for the original entry at https://toph.co/p/makor