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

91% Solution Ratio

mepromeeEarliest, 1w ago

neo11235Fastest, 0.0s

sakib_muhitLightest, 131 kB

cgspyn_868Shortest, 607B

Submit

Login to submit