Jack is planning something and needs your help. Jack needs your help to finish his math homework because he slept through class and has no idea what he is doing. He is given an array which satisfies for all . A new array is generated which satisfies for all . For each , all integers in the range have an equal chance of being chosen.

Jack wants to know the probability that the array is beautiful.

Array is beautiful if there exists an integer such that for each . This probability can be represented as where and are relatively prime.

Since and might be really large, Jack would like to receive the answer as , modulo .

#### Constraints

##### Subtask 1 [15%]

is prime.

##### Subtask 2 [15%]

##### Subtask 3 [70%]

No additional constraints.

#### Input Specification

The first line contains .

The next line contains integers, the th of which is .

#### Output Specification

Output , modulo .

#### Sample Input 1

```
3
1 2 4
```

#### Sample Output 1

`3`

#### Explanation

There are total possible arrays for . Only of those arrays are beautiful. They are , , and .

The probability can be expressed as which simplifies to .

so the answer is .

#### Sample Input 2

```
4
83 838 8383 83838
```

#### Sample Output 2

`167`

## Comments