시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB75234925647.059%

문제

성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다.

  • 배열의 길이는 N이다.
  • 배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다.
  • 배열에서 연속한 수가 A와 B일 때, A <= B 또는 A % B != 0 을 만족해야 한다.

예를 들어, N = 4, K = 7인 경우에 [1, 7, 7, 2]는 성관이가 좋아하는 배열이다. 모든 연속한 수가 1 <= 7, 7 <= 7, 7 % 2 != 0 조건을 만족하기 때문이다.

N과 K가 주어졌을 때, 성관이가 좋아하는 배열의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000)

출력

첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

2 2

예제 출력 1

3

예제 입력 2

9 1

예제 출력 2

1

예제 입력 3

3 3

예제 출력 3

15

예제 입력 4

1 107

예제 출력 4

107

예제 입력 5

2 10

예제 출력 5

83

출처