문제
여러분은 지금 정보올림피아드 대비 모의고사를 보고 있습니다. 문제는 다음과 같습니다.
[1≤a1≤a2≤...≤ak≤n이고, 1≤i≤k-1인 모든 i에 대해 ai+1은 ai의 배수이다.]
n과 k가 주어질 때, 위 조건을 만족하는 수열의 개수를 구하세요. 숫자가 커질 수 있으므로 1,000,000,007(109+7)로 나눈 나머지를 구합시다.
입력
첫 줄에 공백을 사이에 두고 n과 k가 주어집니다.
[제약조건]
서브태스크 1 : 1≤n, k≤8.
서브태스크 2 : 1≤n, k≤400.
서브태스크 3 : 1≤n, k≤2000.
서브태스크 4 : 1≤n≤30,000, 1≤k≤100,000.
서브태스크 5 : 1≤n≤400,000, 1≤k≤400,000.
출력
첫 줄에 수열의 개수를 1 000 000 007(109+7)로 나눈 나머지인 숫자 하나를 출력합니다.
예제 #1
3 2
5
예제 #2
6 4
39
힌트
출처
cki86201
로그인해야 코드를 작성할 수 있어요.