Bobo 在 ICPCCamp 中发现了一个奇怪的素数 $P = 10^{10} + 19$，他决定写下 $n$ 个整数 $x_1, x_2, \dots, x_n$，使得它们的和是 $P$ 的倍数，同时对于给定的 $a_1, a_2, \dots, a_n$，满足 $0 \leq x_i < P - a_i$。

Bobo 想知道写下 $x_1, x_2, \dots, x_n$ 的不同方案数，结果对 $(10^9+7)$ 取模。

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

• $1 \leq n \leq 10^5$
• $0 \leq a_i \leq 10^5$
• 所有测试用例的 $n$ 之和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示不同方案的数量。

样例

输入格式 1

2
0 0

输出格式 1

999999956

输入格式 2

3
0 1 2

输出格式 2

2756