← 返回 google 的题目列表Count Good Numbers
类型：online_judge
Given a positive integer m, count how many good numbers lie in the inclusive range [1, m].
A positive integer is a good number if and only if all of the following conditions hold:
Its decimal representation does not contain digit 0.
Every digit appears at most once.
No digit is strictly smaller than both of its adjacent digits. In other words, for every 1 ≤ i < len(s)-1, the following must not hold:
s[i] < s[i-1] and s[i] < s[i+1].
Here, s is the decimal representation of the number. Numbers with one or two digits automatically satisfy condition 3.
Input
One line containing a positive integer m.
Output
Print one integer: the number of good numbers in [1, m].
Constraints
1 ≤ m ≤ 10^18
Examples
Example 1
Input:
20
Output:
17
Example 2
Input:
132
Output:
88
Example 3
Input:
999
Output:
417
Example
Input
9
Output
9