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