At the heart of the Mathematical Mirage Casino, Parsa finds himself at the Color Roulette table—a game known to bankrupt geniuses and thrill mathematicians.

Laid out before him is an infinite roulette strip, each integer position on the ~x~-axis representing a pocket to be painted. The dealer deals Parsa ~n~ enchanted chips, each representing a unique magical color with a mystical constraint.

Each chip ~i~ has a locking interval ~l_i~. When Parsa drops chip ~i~ on pocket ~x~, he's bound by roulette law to to color every multiple of ~l_i~ away from ~x~ with the same chip—pockets at ~x \pm l_i~, ~x \pm 2l_i~ and so on, forever.

The house rule is firm: every pocket must receive exactly one color, and the periodicity of each chip must be strictly respected. Parsa can smell the jackpot… but first, he must count.

In how many distinct ways can he paint the entire roulette line under these constraints?

The pit boss assures him the answer is finite, but Parsa must compute it modulo ~10^9 + 7~ to make it out with his winnings.

Will he walk away a legend?

Input

The first line of input contains ~n~ ~(1 \le n \le 10^6)~, the number of distinct chip colors.

The second line contains ~n~ integers, where the ~i~th number represents ~l_i~ ~(1 \le l_i \le 10^6)~, the periodicity of each chip color ~i~.

Output

Print how many distinct valid ways there are to assign colors to all the pockets on the ~x~-axis, using the given chips and obeying their periodic constraints.

Clarifications

• You can imagine we have infinitely many chips of each color available.
• You can use a color any number of times (including zero).

Examples

Input 1

3
1 1 1

Output 1

3

Explanation

Since all of our ~3~ colors have a periodicity of ~1~, we can only use one of them to color the whole thing. So since we have ~3~ colors to do so, there are ~3~ different valid ways.

Input 2

2
2 4

Output 2

4

Explanation

Let's say the colour with ~l_i = 2~ is blue, and the other one is red. There are four possible ways to colour the entire roulette strip:

1. Colour every point blue.
2. Colour every point red.
3. Colour the even-numbered points blue and the odd-numbered ones red.
4. Colour the odd-numbered points blue and the even-numbered ones red.

Input 3

4
1 2 4 4

Output 3

26