Good Sets

Time limit2sMemory limit512 MB

Summary

Count nonempty subsets of {1,...,N} whose decimal digits, pooled together, use each digit 0-9 at most once.

Level: Medium6 of 10
Topics: Bit manipulation, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

Let $S$ be the set of the integers from 1 to $N$ .

Write a program that counts how many subsets of $S$ are good sets.

A subset is a good set when you write every number it contains in decimal, collect all of those digits together, and each of the digits 0 to 9 appears at most once. The empty set is not counted.

For example, {12, 345, 67890} and {47, 109} are good sets, while {147, 342} is not a good set because the digit 4 appears twice.

Input

The first line contains $N$ . ( $1 \le N \le 10^9$ )

Output

Print the number of good sets among the subsets of $S$ , modulo 1,000,000,007.

Examples2

Example 1
Input
```
3
```
Expected output
```
7
```
Example 2
Input
```
10
```
Expected output
```
767
```