Distinct Subsequences in Repeated Colored Wool Sequence

WAPER is playing a game with colored wools. In the i-th round of the game, a parameter (m_i) is chosen and exactly (n) wools are placed sequentially. The color of the wool at position (j) (for (1 \le j \le n)) is defined by [ S_j = ((j-1) \bmod m_i) + 1, \quad 1 \le j \le n. ] For example, when (n=7) and (m_i=3), the sequence is [ 1,; 2,; 3,; 1,; 2,; 3,; 1. ]

WAPER then may choose to break (i.e. remove) some of the blocks (possibly none or all), thereby obtaining a subsequence (the order is preserved). Two subsequences are considered different if they are of different lengths or differ in the color at some corresponding position. Note that the empty subsequence is also counted.

Your task is to compute the number of distinct subsequences that can be formed from the sequence, and output the result modulo (10^9+7).

inputFormat

The first line contains two integers (n) and (q), where (n) is the number of wool blocks and (q) is the number of rounds. Each of the following (q) lines contains one integer (m_i) representing the parameter for that round.

outputFormat

For each round, output a single integer -- the number of distinct subsequences modulo (10^9+7). Print each answer on a new line.

sample

7 1
3

96