아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

배수열

시간 제한2초메모리 제한512 MB

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

보통10점 중 7점

유형
조합론, 동적 계획법, 수학, 정수론
정답자
아직 제출이 없습니다

문제

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

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

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

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

입력

첫째 줄에 NN과 LL이 공백 하나로 구분되어 주어진다. (1≤N,L≤20001 \le N, L \le 2000)

출력

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

예제5

  1. 예제 1

    입력
    3 2
    
    예상 출력
    5
    
  2. 예제 2

    입력
    6 4
    
    예상 출력
    39
    
  3. 예제 3

    입력
    1 1
    
    예상 출력
    1
    
  4. 예제 4

    입력
    7 1
    
    예상 출력
    7
    
  5. 예제 5

    입력
    10 3
    
    예상 출력
    53