cho.sh

Good Sets

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

Medium6Bit manipulationCombinatoricsDynamic programmingNo attempts yetTime limit2sMemory limit512 MB

Problem

Let SS be the set of the integers from 1 to NN.

Write a program that counts how many subsets of SS 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 NN. (1≤N≤1091 \le N \le 10^9)

Output

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