시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 512 MB 17 13 4 80.000%

문제

알버트는 학교에서 정수, 숫자, 뺄셈을 배웠다. 그래서 심심할 때마다 혼자 즐길 수 있도록 "까다로운 수"라는 게임을 만들었다.

이 게임을 하려면 먼저, 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-까다로운 수"를 구하는 프로그램을 작성하시오. 단, 답이 매우 큰 수가 될 수 있기 때문에, 109+7로 나눈 나머지를 출력한다.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 100). 다음 T줄에 걸쳐서 각 줄에 K와 A가 주어진다. 두 정수는 공백으로 구분되어져 있다. (1 ≤ K ≤ 1018, 0 ≤ A ≤ 9)

출력

각 테스트 케이스마다 K번째 작은 "A-까다로운 수"를 109+7로 나눈 나머지를 한 줄에 하나씩 출력한다.

예제 입력 1

8
5 0
5 1
30 1
12 2
20 5
21 5
30 8
1000 8

예제 출력 1

5
5
32
15
50
60
9190
80902435
  • 네 번째 테스트 케이스: A = 2 일 때 10, 11, 12 는 "2-까다로운 수"가 아니다. 
  • 마지막 테스트 케이스: 1000번째 "8-까다로운 수"는 808080908091이고, 이 값을 109+7로 나눈 나머지는 80902435 이다.
W3sicHJvYmxlbV9pZCI6IjE2MjAzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZTRjXHViMmU0XHViODVjXHVjNmI0IFx1YzIxOCBcdWNjM2VcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU0Y1x1YmM4NFx1ZDJiOFx1YjI5NCBcdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWMgXHVjODE1XHVjMjE4LCBcdWMyMmJcdWM3OTAsIFx1YmU4NFx1YzE0OFx1Yzc0NCBcdWJjMzBcdWM2ZTBcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWMyZWNcdWMyZWNcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0IFx1ZDYzY1x1Yzc5MCBcdWM5OTBcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCAmcXVvdDtcdWFlNGNcdWIyZTRcdWI4NWNcdWM2YjQgXHVjMjE4JnF1b3Q7XHViNzdjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViODI0XHViYTc0IFx1YmEzY1x1YzgwMCwgMCBcdWM3NzRcdWMwYzEgOSBcdWM3NzRcdWQ1NTggXHVjMjJiXHVjNzkwIEFcdWI5N2MgXHVhY2U4XHViNzdjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1ZDZjNCBLXHViYzg4XHVjOWY4IFx1Yzc5MVx1Yzc0MCAmcXVvdDtBLVx1YWU0Y1x1YjJlNFx1Yjg1Y1x1YzZiNCBcdWMyMTgmcXVvdDtcdWI5N2MgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBYXHVhYzAwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3NCAmcXVvdDtBLVx1YWU0Y1x1YjJlNFx1Yjg1Y1x1YzZiNCBcdWMyMTgmcXVvdDtcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlhcdWFjMDAgXHVkNTVjIFx1Yzc5MFx1YjliZlx1YzIxOFx1YmE3NCAmcXVvdDtBLVx1YWU0Y1x1YjJlNFx1Yjg1Y1x1YzZiNCBcdWMyMTgmcXVvdDtcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlhcdWFjMDAgXHViNDUwIFx1Yzc5MFx1YjlhYyBcdWM3NzRcdWMwYzFcdWM3NzRcdWJhNzRcdWMxMWMsIFhcdWI5N2MgXHVhZDZjXHVjMTMxXHVkNTU4XHViMjk0IFx1YzIyYlx1Yzc5MCBcdWM5MTEgXHVjNzc4XHVjODExXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgQSBcdWJiZjhcdWI5Y2NcdWM3NzggXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVjNlx1YzczY1x1YmE3NCAmcXVvdDtBLVx1YWU0Y1x1YjJlNFx1Yjg1Y1x1YzZiNCBcdWMyMTgmcXVvdDtcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgQSA9IDBcdWM3NzggXHVhY2JkXHVjNmIwIFx1YmFhOFx1YjRlMCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViMjk0ICZxdW90O0EtXHVhZTRjXHViMmU0XHViODVjXHVjNmI0IFx1YzIxOCZxdW90O1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+QSA9IDFcdWM3NzggXHVhY2JkXHVjNmIwLCBcdWNjYWIgMzBcdWFjMWNcdWM3NTggJnF1b3Q7QS1cdWFlNGNcdWIyZTRcdWI4NWNcdWM2YjQgXHVjMjE4JnF1b3Q7XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjEsIDIsIDMsIDQsIDUsIDYsIDcsIDgsIDksIDEwLCAxMiwgMTMsIDE0LCAxNSwgMTYsIDE3LCAxOCwgMTksIDIwLCAyMSwgMjMsIDI0LCAyNSwgMjYsIDI3LCAyOCwgMjksIDMwLCAzMSwgMzIsIC4uLjxcL3A+XHJcblxyXG48cD5BXHVjNjQwIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgS1x1YmM4OFx1YzlmOFx1Yjg1YyBcdWM3OTFcdWM3NDAgJnF1b3Q7QS1cdWFlNGNcdWIyZTRcdWI4NWNcdWM2YjQgXHVjMjE4JnF1b3Q7XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWIyZTgsIFx1YjJmNVx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVkMDcwIFx1YzIxOFx1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIDEwPHN1cD45PFwvc3VwPis3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoMSAmbGU7IFQgJmxlOyAxMDApLiBcdWIyZTRcdWM3NGMgVFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHVhYzAxIFx1YzkwNFx1YzVkMCBLXHVjNjQwIEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVjODE1XHVjMjE4XHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IEsgJmxlOyAxMDxzdXA+MTg8XC9zdXA+LCAwICZsZTsgQSAmbGU7IDkpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgS1x1YmM4OFx1YzlmOCBcdWM3OTFcdWM3NDAgJnF1b3Q7QS1cdWFlNGNcdWIyZTRcdWI4NWNcdWM2YjQgXHVjMjE4JnF1b3Q7XHViOTdjIDEwPHN1cD45PFwvc3VwPis3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsInNhbXBsZV9leHBsYWluXzEiOiI8dWw+XHJcblx0PGxpPlx1YjEyNCBcdWJjODhcdWM5ZjggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNDogQSA9IDIgXHVjNzdjIFx1YjU0YyAxMCwgMTEsIDEyIFx1YjI5NCAmcXVvdDsyLVx1YWU0Y1x1YjJlNFx1Yjg1Y1x1YzZiNCBcdWMyMTgmcXVvdDtcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5cdWI5YzhcdWM5YzBcdWI5YzkgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNDogMTAwMFx1YmM4OFx1YzlmOCAmcXVvdDs4LVx1YWU0Y1x1YjJlNFx1Yjg1Y1x1YzZiNCBcdWMyMTgmcXVvdDtcdWIyOTQgODA4MDgwOTA4MDkxXHVjNzc0XHVhY2UwLCBcdWM3NzQgXHVhYzEyXHVjNzQ0IDEwPHN1cD45PFwvc3VwPis3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWIyOTQmbmJzcDs4MDkwMjQzNSBcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNjIwMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpbmRpbmcgVHJpY2t5IE51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkFsYmVydCByZWNlbnRseSBsZWFybmVkIGFib3V0IGludGVnZXJzLCBkaWdpdHMsIGFuZCBzdWJ0cmFjdGlvbi4gSGUmIzM5O3Mgc28gZmFzY2luYXRlZCBieSB0aGVzZSBuZXcgbWF0aGVtYXRpY2FsIGNvbmNlcHRzLCBhbmQgaGUgaW52ZW50ZWQgYSBnYW1lIGNhbGxlZCB0aGUgJnF1b3Q7VHJpY2t5IE51bWJlcnMmcXVvdDsuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgZ2FtZSwgaGUgZmlyc3QgcGlja3MgYW4gaW50ZWdlciBkaWdpdCBBIChBIGlzIGJldHdlZW4gMCBhbmQgOSwgaW5jbHVzaXZlKS4gSGUgdGhlbiBkZWZpbmVzICYjMzk7QS10cmlja3kgbnVtYmVycyYjMzk7IGFzIGZvbGxvd3MuIEEgcG9zaXRpdmUgaW50ZWdlciB4IGlzIGFuICZxdW90O0EtdHJpY2t5IG51bWJlciZxdW90OyBpZiB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnMgYXJlIG1ldDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JZiB4IG9ubHkgaGFzIG9uZSBkaWdpdCAoaS5lLiwgeCBpcyBiZXR3ZWVuIDEgYW5kIDksIGluY2x1c2l2ZSksIHRoZW4gaXQgaXMgYW4gQS10cmlja3kgbnVtYmVyLjxcL2xpPlxyXG5cdDxsaT5JZiB4IGNvbnRhaW5zIHR3byBvciBtb3JlIGRpZ2l0cywgYW5kIHRoZSAoYWJzb2x1dGUpIGRpZmZlcmVuY2UgYmV0d2VlbiBldmVyeSBwYWlyIG9mIGNvbnNlY3V0aXZlIGRpZ2l0cyBvZiB4IGlzIGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byBBLCB0aGVuIHggaXMgYW4gQS10cmlja3kgbnVtYmVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBpbnN0YW5jZSwgc3VwcG9zZSBBbGJlcnQgcGlja3MgQSA9IDAuIFRoZW4gZXZlcnkgcG9zaXRpdmUgaW50ZWdlciBpcyBhIDAtdHJpY2t5IG51bWJlci48XC9wPlxyXG5cclxuPHA+V2hlbiBBID0gMSwgdGhlIGZvbGxvd2luZyBsaXN0IHNob3dzIHRoZSBmaXJzdCB0aGlydHkgMS10cmlja3kgbnVtYmVyczo8XC9wPlxyXG5cclxuPHA+MSwgJm5ic3A7MiwgJm5ic3A7MywgJm5ic3A7NCwgJm5ic3A7NSwgJm5ic3A7NiwgJm5ic3A7NywgJm5ic3A7OCwgJm5ic3A7OSwgMTAsJm5ic3A7MTIsIDEzLCAxNCwgMTUsIDE2LCAxNywgMTgsIDE5LCAyMCwgMjEsJm5ic3A7MjMsIDI0LCAyNSwgMjYsIDI3LCAyOCwgMjksIDMwLCAzMSwgMzIsIC4uLjxcL3A+XHJcblxyXG48cD5BbGJlcnQgd2FudHMgdG8gZmluZCB0aGUgSy10aCBzbWFsbGVzdCBBLXRyaWNreSBudW1iZXIgKGdpdmVuIEEgYW5kIEspLCBhbmQgdG8gdmVyaWZ5IHdoZXRoZXIgaGlzIGZpbmRpbmdzIGFyZSBjb3JyZWN0IC0tIGhlIG5lZWRzIHlvdXIgaGVscCEgTm90ZSB0aGF0IHRoZSBudW1iZXIgY2FuIGJlIHZlcnkgbGFyZ2UgZm9yIGNlcnRhaW4gdmFsdWVzIG9mIEsgYW5kIEEuIFRoZXJlZm9yZSwgQWxiZXJ0IHNheXMgeW91IGNhbiBzaW1wbHkgZ2l2ZSBoaW0gdGhlIEstdGggc21hbGxlc3QgQS10cmlja3kgbnVtYmVyIG1vZHVsbyAoMTA8c3VwPjk8XC9zdXA+KzcpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIGEgcG9zaXRpdmUgaW50ZWdlciwgVCAoMSAmbGU7Jm5ic3A7VCAmbGU7IDEwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIFQgbGluZXMgd2lsbCBjb250YWluIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyAoSyBhbmQgQSksIHNlcGFyYXRlZCBieSBhIHdoaXRlc3BhY2UuIEsgaXMgYmV0d2VlbiAxIGFuZCAxMDxzdXA+MTg8XC9zdXA+IChpbmNsdXNpdmUpIGFuZCBBIGlzIGJldHdlZW4gMCBhbmQgOSAoaW5jbHVzaXZlKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHlvdSBzaG91bGQgb3V0cHV0IHRoZSBLLXRoIHNtYWxsZXN0IEEtdHJpY2t5IG51bWJlciAobW9kdWxvICgxMDxzdXA+OTxcL3N1cD4rNykpLiBFYWNoIHRlc3QgY2FzZSYjMzk7cyBvdXRwdXQgc2hvdWxkIGJlIGNvbnRhaW5lZCBpbiBhIHNpbmdsZSBsaW5lIChzZWUgdGhlIHNhbXBsZSBvdXRwdXQgYmVsb3cpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCIsInNhbXBsZV9leHBsYWluXzEiOiI8dWw+XHJcblx0PGxpPkZvciB0aGUgZm91cnRoIHRlc3QgY2FzZSAoSyA9IDEyIGFuZCBBID0gMiksIG5vdGUgdGhhdCAxMCwgMTEsIGFuZCAxMiBhcmUgbm90IDItdHJpY2t5IG51bWJlcnMuPFwvbGk+XHJcblx0PGxpPkZvciB0aGUgbGFzdCBjYXNlLCB0aGUgYWN0dWFsIGFuc3dlciBpcyA4MDgwODA5MDgwOTEgKGJlZm9yZSBhcHBseWluZyB0aGUgbW9kdWxvIG9wZXJhdGlvbikuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처

  • 문제를 만든 사람: haden