Migrated from Lutece 3225 数学专题签到处

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定常数 $N$，共 $Q$ 次询问。

每次给定 $x$，求

答案对 $10^9+7$ 取模。

Input

第一行，两个正整数 $N$ 和 $Q$。

接下来 $n$ 行，每行一个正整数 $x$。

Output

共 $Q$ 行，每行一个整数，表示答案。

Samples

5 3
10
14
5

3069
15
3927

Constraints

$1\leq N\leq 10^6$，$1\leq Q \leq 10^5$，$1\leq x\leq 3N$

Resources

2024 UESTC ICPC Training for Math