Heavenly Dragon Flash

Time limit2sMemory limit128 MB

Summary

Count sequences of nondecreasing cut heights where each cut divides the object's height, modulo 1000000007.

Level: Medium7 of 10
Topics: Dynamic programming, Number theory
Solved: No attempts yet

Problem

Seunggyun, a swordsman who outlives his era, trained a new technique called the Heavenly Dragon Flash to sharpen his school, the Alps Sword Style.

The Heavenly Dragon Flash cuts the $N$ objects in front of him one at a time, in the order they stand. The cutting height never drops from one cut to the next. It either stays the same or goes higher.

The remarkable part of the technique is that the height of an object divided by the height of the cut always comes out as a whole natural number. Seunggyun can also cut an object at exactly its own height. Height 0 cannot be cut.

Say three objects of heights 2, 4 and 6 stand in front of him. He can cut them at heights 1, 2 and 3, because 2 is divisible by 1, 4 by 2, 6 by 3, and the cutting height never drops. For the same reason 1, 1, 1 works, and so does 2, 4, 6, which he uses to show off his precision.

To see how much the Heavenly Dragon Flash is capable of, Seunggyun wants the number of ways to cut all $N$ objects. The example above has 12 ways.

He never learned numbers, so he cannot count them himself. Count the ways for him.

Input

The input holds several test cases.

The first line contains the number of test cases $T$ . $(1 \le T \le 30)$

The first line of each test case contains the number of objects $N$ . $(1 \le N \le 300)$

The second line contains the $N$ object heights $H_1, H_2, \dots, H_N$ , separated by spaces. $(1 \le H_i \le 1000000)$

Output

For each test case, print on its own line the number of ways Seunggyun can cut the objects, modulo $1000000007$ .

Examples7

Example 1
Input
```
2
3
2 4 6
2
2 3
```
Expected output
```
12
3
```
Example 2
Input
```
1
1
1
```
Expected output
```
1
```
Example 3
Input
```
1
1
1000000
```
Expected output
```
49
```
Example 4
Input
```
1
3
6 4 2
```
Expected output
```
4
```
Example 5
Input
```
1
5
2 2 2 2 2
```
Expected output
```
6
```
Example 6
Input
```
1
4
999983 999979 999961 999959
```
Expected output
```
2
```

Example 7

Input

3
2
1 1000000
4
12 12 12 12
6
1000000 500000 250000 100 10 1

Expected output

49
126
1