민호는 1 이상 N 이하의 정수를 사용해 길이 L인 수열을 만들려고 한다. 아무 제한이 없다면 경우의 수는 NL이다.
민호는 그런 수열이 재미없다고 생각해서, 다음 두 규칙을 지키는 수열만 만들기로 했다.
- 수열은 비내림차순이다. 즉 앞에 오는 수가 뒤에 오는 수보다 클 수 없다.
- 수열에서 두 자리를 어떻게 골라도, 한쪽 수가 다른 쪽 수의 배수다.
두 규칙을 모두 지키는 수열이 몇 개인지 세어 보자. 개수가 매우 커질 수 있으므로 109+7로 나눈 나머지를 구한다.