시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

정수 1부터 N까지로 이루어진 집합 S가 있다.

이때, 집합 S의 부분 집합 중에서 좋은 집합의 개수를 구하는 프로그램을 작성하시오.

좋은 집합이란 집합에 포함되어 있는 모든 수에, 0부터 9까지 각 숫자가 최대 한 번씩 등장하는 집합을 말한다.

예를 들어, {12, 345, 67890}과 {47, 109}는 좋은 집합이고, {147, 342}는 4가 두 번 나오기 때문에, 좋은 집합이 아니다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 109)

출력

집합 S의 부분 집합 중에서 좋은 집합의 개수 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3

예제 출력 1

7

예제 입력 2

10

예제 출력 2

767