29773번 - 2023년은 검은 토끼의 해 (Hard)

문제

2023년은 검은 토끼의 해로 불린다. 스타는 검은 토끼의 해를 기념해서 흑묘 복권을 만들려고 한다.

흑묘 복권은 총 $N$개의 티켓으로 구성된다. 각 티켓에는 1ドル$ 이상 $N$ 이하의 정수인 시리얼 번호가 적혀 있으며 서로 다른 티켓에는 서로 다른 시리얼 번호가 적혀있다.

티켓 중에서 시리얼 번호가 네 자릿수 이상이고 서로 다른 자리에서 네 개의 자릿수를 골라 고른 자릿수를 제외한 나머지 자릿수를 지울 때 2023을 만들 수 있으면 해당 티켓은 당첨 티켓이다. 예를 들어 시리얼 번호가 2023, 1280423, 2200233이면 당첨이고 3480, 572, 2032이면 꽝이다.

$N$이 주어졌을 때, 흑묘 복권의 당첨 티켓 수를 구하여라.

입력

흑묘 복권의 티켓 수 $N$이 주어진다. $(1 \leq N \leq 10^{18})$

출력

당첨 티켓 수를 출력한다.

제한

힌트