Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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 **A _{i}** is the

Note: Two sequences will be different if there exists an index where two sequences have two different values at that index.

The first line will contain an integer **n(1 ≤ n ≤ 10 ^{6})**. Next line will contain

The last line will contain two integers **k** and **m (1 ≤ k, m ≤ 10 ^{9}).**

Output the number of unique special sequences Mr Makor can make modulo **(10 ^{9}+7)**.

Input | Output |
---|---|

2 6 4 2 10 | 2 |

93% Solution Ratio

mohanr7073Earliest,

kzvd4729Fastest, 0.7s

EgorKulikovLightest, 55 MB

kzvd4729Shortest, 672B

Login to submit