좋아하는 숫자

샘이 물었다. "마이스터 에이몬, 가장 좋아하는 숫자가 무엇인가요?"

"당연히 2068965517241379310344827586이지."

"왜요?"

"이 수는 6으로 끝나는 가장 작은 수다. 마지막 자리 6을 맨 앞으로 옮기면 수가 정확히 3배가 된다! 이런 수를 모두 찾는 것이 내 입학시험 문제였지. 아카데미에 들어가고 싶다면 충분히 준비되어 있어야 한다. 이 성질을 가진 수 중 k번째 수를 찾아낼 수 있겠느냐? 수고를 덜어 주마. 그 수를 $10^9+7$로 나눈 나머지만 구하면 된다."

입력 파일의 첫 번째이자 유일한 줄에 정수 $k$ ($1 \le k \le 10^9$)가 주어진다. 이는 찾아야 할 수의 순서 번호다.

출력 파일의 한 줄에 찾는 수를 $10^9+7$로 나눈 나머지를 출력한다.