배수열
시간 제한2초메모리 제한512 MB
1부터 N까지의 값으로 길이 L의 비감소 수열을 만들되, 임의의 두 항 중 하나가 다른 하나의 배수인 수열의 개수를 10^9+7로 나눈 나머지로 구한다.
문제
민호는 1 이상 이하의 정수를 사용해 길이 인 수열을 만들려고 한다. 아무 제한이 없다면 경우의 수는 이다.
민호는 그런 수열이 재미없다고 생각해서, 다음 두 규칙을 지키는 수열만 만들기로 했다.
- 수열은 비내림차순이다. 즉 앞에 오는 수가 뒤에 오는 수보다 클 수 없다.
- 수열에서 두 자리를 어떻게 골라도, 한쪽 수가 다른 쪽 수의 배수다.
두 규칙을 모두 지키는 수열이 몇 개인지 세어 보자. 개수가 매우 커질 수 있으므로 로 나눈 나머지를 구한다.
입력
첫째 줄에 과 이 공백 하나로 구분되어 주어진다. ()
출력
두 규칙을 지키는 수열의 개수를 로 나눈 나머지를 한 줄에 출력한다.