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

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

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

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

입력 형식

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

출력 형식

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

예제 입력 1

3

예제 출력 1

7

예제 입력 2

10

예제 출력 2

767