Favorite Array

Interview

Time limit2sMemory limit512 MB

Summary

Count length-N arrays with entries from 1 to K where no earlier element is a larger multiple of the next.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Seonggwan likes an array that satisfies all of the following.

The array has length $N$ .
Every element of the array is an integer between $1$ and $K$ , inclusive.
For any two neighboring elements, with $A$ first and $B$ second, either $A \le B$ or $A \bmod B \ne 0$ holds.

In other words, the only forbidden pair is one where the earlier element is larger than the later element and is divisible by it.

For $N = 4$ and $K = 7$ , the array $[1, 7, 7, 2]$ is one Seonggwan likes. Its three neighboring pairs satisfy $1 \le 7$ , $7 \le 7$ , and $7 \bmod 2 \ne 0$ .

Given $N$ and $K$ , write a program that counts the arrays Seonggwan likes.

Input

The first line contains $N$ and $K$ , separated by a space. ( $1 \le N \le 10$ , $1 \le K \le 100000$ )

Output

Print on the first line the number of arrays Seonggwan likes, modulo 1,000,000,007.

Examples5

Example 1
Input
```
2 2
```
Expected output
```
3
```
Example 2
Input
```
9 1
```
Expected output
```
1
```
Example 3
Input
```
3 3
```
Expected output
```
15
```
Example 4
Input
```
1 107
```
Expected output
```
107
```
Example 5
Input
```
2 10
```
Expected output
```
83
```