배수열

1부터 N까지의 값으로 길이 L의 비감소 수열을 만들되, 임의의 두 항 중 하나가 다른 하나의 배수인 수열의 개수를 10^9+7로 나눈 나머지로 구한다.

보통7조합론동적 계획법수학정수론아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

민호는 1 이상 NN 이하의 정수를 사용해 길이 LL인 수열을 만들려고 한다. 아무 제한이 없다면 경우의 수는 NLN^L이다.

민호는 그런 수열이 재미없다고 생각해서, 다음 두 규칙을 지키는 수열만 만들기로 했다.

  1. 수열은 비내림차순이다. 즉 앞에 오는 수가 뒤에 오는 수보다 클 수 없다.
  2. 수열에서 두 자리를 어떻게 골라도, 한쪽 수가 다른 쪽 수의 배수다.

두 규칙을 모두 지키는 수열이 몇 개인지 세어 보자. 개수가 매우 커질 수 있으므로 109+710^9 + 7로 나눈 나머지를 구한다.

입력

첫째 줄에 NNLL이 공백 하나로 구분되어 주어진다. (1N,L20001 \le N, L \le 2000)

출력

두 규칙을 지키는 수열의 개수를 109+710^9 + 7로 나눈 나머지를 한 줄에 출력한다.