题目描述

Bobo knows that $ \int_{0}^{\infty} \frac{1}{1 + x^2}\ \mathrm{d}x = \frac{\pi}{2}$.

Given n distinct positive integers $a_1, a_2, \dots, a_n$ ​, find the value of $ \frac{1}{\pi} \int_{0}^{\infty} \frac{1}{\prod_{i = 1}^n(a_i^2 + x^2)}\ \mathrm{d}x $.

It can be proved that the value is a rational number $\frac{p}{q}$. Print the result as $(p \cdot q^{-1}) \bmod (10^9+7)$.

输入格式

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n. The second line contains n integers $a_1, a_2, \dots, a_n$​.

• $1 \leq n \leq 10^3$
• $1 \leq a_i \leq 10^9$
• $\{a_1, a_2, \dots, a_n\}$ are distinct.
• The sum of $n^2$ does not exceed $10^7$.

输出格式

For each test case, print an integer which denotes the result.

样例

样例输入

1
1
1
2
2
1 2

样例输出

500000004
250000002
83333334