Happy Sub-Sequence

Recently Alex has participated in a programming contest.

He became 1st runner up. He couldn't solve one problem. He is so upset.
Now Alex comes to you and gives you the problem.

Alex gives you an integer array arr1, arr2, arr3, ...., arrn.

An array p is called to be a sub-sequence of arr if it is possible to remove some elements from an array arr to get p.

Array p1, p2, p3, ... , pm is called to be "Happy" if it is not empty and for every i(1 <= i <= m), pi is divisible by i.

The array a has exactly 2n−1 different sub-sequences (excluding an empty sub-sequence).

Find the number of "Happy" sub-sequences.

Input

The first line contains an integer n (1 <= n <= 100000) — the length of the array arr.

The next line contains integers arr1, arr2, arr3,..., arrn (1 <= arri <= 106).

Output

Print exactly one intger - the number of "Happy" subsequences taken modulo 109 + 7.

Samples

Input	Output
5 2 2 1 22 14	13

Input	Output
1 5	1