2023, the Year of the Black Rabbit

Interview

Time limit2sMemory limit512 MB

Summary

Count how many serial numbers from 1 to N have 2023 as a subsequence of their digits.

Level: Easy3 of 10
Topics: String, Greedy
Solved: No attempts yet

Problem

2023 is known as the year of the black rabbit. Star wants to make a black cat lottery to celebrate the year of the black rabbit.

A black cat lottery has $N$ tickets in total. Each ticket has a serial number that is an integer from $1$ to $N$ , and no two tickets share the same serial number.

A ticket wins if its serial number has at least four digits and you can pick four digits at different positions, erase all the other digits, and get 2023. For example, 2023 wins, 1280423 wins, and 2200233 wins, while 3480, 572, and 2032 lose.

Input

The number of tickets $N$ in the black cat lottery is given. ( $1 \leq N \leq 10\,000\,000$ )

Output

Print the number of winning tickets.

Examples3

Example 1
Input
```
2023
```
Expected output
```
1
```
Example 2
Input
```
1237987
```
Expected output
```
1994
```
Example 3
Input
```
35
```
Expected output
```
0
```