A한수
시간 제한2초메모리 제한128 MB
각 자리 숫자가 비내림차순이며 연속한 등차수열 그룹으로 나눌 때 필요한 최소 그룹 수가 정확히 A인 N자리 수의 개수를 1,000,000,007로 나눈 나머지로 구합니다.
문제
어떤 수 X의 자리수를 A개의 비어 있지 않은 연속된 그룹으로 나눌 수 있고, 각 그룹 안의 자리수가 등차수열을 이룰 때 X를 A한수라고 한다.
양의 정수 X가 A한수이지만 (A-1)한수는 아니며, X의 자리수가 왼쪽에서 오른쪽으로 비내림차순이면 X를 진짜 A한수라고 한다.
N과 A가 주어진다. N자리 수이며 첫 자리수가 0이 아닌 진짜 A한수의 개수를 구하시오.
입력
첫째 줄에 자연수 N과 A가 주어진다. 두 수는 모두 1,000 이하이다.
출력
첫째 줄에 N자리 진짜 A한수의 개수를 1,000,000,007로 나눈 나머지를 출력한다.