Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Happy Sub-Sequence

By dhruba_1603088 · Limits 2s, 512 MB

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

InputOutput
5
2 2 1 22 14
13
InputOutput
1
5
1

Discussion

Statistics


92% Solution Ratio

mepromeeEarliest, Nov '19

neo11235Fastest, 0.0s

sakib_muhitLightest, 131 kB

cgspyn_868Shortest, 607B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.