[BOJ 13003] 배수열

View as PDF

Submit solution

Points: 3
Time limit: 2.0s
Memory limit: 512M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

민호는 1부터 N까지의 숫자를 사용해 길이 L인 수열을 만들려고 한다. 이럴 경우 경우의 수는 NL이 된다.</p>

하지만 이렇게 수열을 만드는 경우는 너무 재미가 없다고 생각한 민호는 아래 두가지 규칙을 지키면서 두열을 만들려고 한다.

  1. 수열의 수는 비 내림차순이여야 한다. 즉 수열은 뒤로 갈수록 감소하지 않아야 한다.
  2. 수열의 모든 수는 서로 배수 관계여야 한다.

이렇게 만든 수열의 전체 경우의 수를 계산해 출력하자. 단 경우의 수가 많아질 수 있으니 109 + 7으로 나눈 나머지를 출력한다.

입력 형식

첫 번째 줄에 N, L (1 ≤ N, L ≤ 2,000) 이 공백을 구분으로 주어진다.

출력 형식

위에 두가지 조건을 지키면서 수열을 만드는 경우의 수를 109 + 7으로 나눈 나머지를 출력한다.

예제 입력 1

3 2

예제 출력 1

5

예제 입력 2

6 4

예제 출력 2

39

Comments

There are no comments at the moment.