까다로운 수 찾기
시간 제한1초메모리 제한512 MB
A와 K가 주어질 때 인접한 두 자리의 차가 A 이상인 양의 정수 중 K번째 작은 수를 찾아 10^9+7로 나눈 값을 출력한다.
문제
알버트는 학교에서 정수, 숫자, 뺄셈을 배웠다. 그래서 심심할 때마다 혼자 즐길 수 있도록 "까다로운 수"라는 게임을 만들었다.
이 게임을 하려면 먼저 0 이상 9 이하의 숫자 A를 골라야 한다. 그 다음 K번째로 작은 "A-까다로운 수"를 찾아야 하는데, 양의 정수 X가 아래 조건을 만족하면 "A-까다로운 수"라고 한다.
- X가 한 자릿수면 "A-까다로운 수"이다.
- X가 두 자리 이상이면서, X를 구성하는 숫자 중 인접한 숫자의 차이가 A 미만인 경우가 없으면 "A-까다로운 수"이다.
예를 들어 A = 0인 경우 모든 양의 정수는 "A-까다로운 수"이다.
A = 1인 경우, 첫 30개의 "A-까다로운 수"는 다음과 같다.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, ...
A와 K가 주어졌을 때, K번째로 작은 "A-까다로운 수"를 구하는 프로그램을 작성하시오. 답이 매우 클 수 있으므로 10^9+7로 나눈 나머지를 출력한다.
입력
첫째 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 100). 다음 T줄에 걸쳐서 각 줄에 K와 A가 주어진다. 두 정수는 공백으로 구분되어져 있다. (1 ≤ K ≤ 10^18, 0 ≤ A ≤ 9)
출력
각 테스트 케이스마다 K번째로 작은 "A-까다로운 수"를 10^9+7로 나눈 나머지를 한 줄에 하나씩 출력한다.