题目描述

小C喜欢数字609,给出一个数$n$，求$1$到$n$中，有多少个数至少包含数字 6 、 0 、 9一次且不包含其他数字，请注意数字中不能有前导零，即069不能算是一个合法的数字。

输入格式

一个整数 $n$。

输出格式

输出满足条件的数字个数。

样例

1000

4

提示

样例1解释

满足条件的数有 609,690,906,960。

数据范围

前 $30\%$ 的数据，$1 \le n \le 10^6$。

前 100% 的数据, $1 \le n \le 10^9$。