영과 이

flickr.com에서 가져온 이미지

Arnar와 Arnar는 함께 수를 살펴보고 있다. Arnar는 숫자 $0$만 좋아하는 반면, Arnar는 숫자 $2$만 좋아한다. Arnar와 Arnar는 친구이므로, 둘 다 자신의 가장 좋아하는 숫자뿐만 아니라 서로가 가장 좋아하는 숫자가 들어 있는 수도 마음에 들어 한다. 하지만 수에는 다른 숫자가 절대로 포함되어서는 안 된다.

따라서 수 $20$, $2\,002$, $0$, $2$은 허용되지만, $54$, $173$, $120\,120$은 허용되지 않는다.

이제 Arnar와 Arnar는 $0$부터 자신들이 아는 가장 큰 수인 $n$까지의 모든 수를 모았다. 그들은 모은 수 중 마음에 드는 수가 몇 개인지 알고 싶지만, 수를 셀 줄 모른다. 그들이 수를 세도록 도와줄 수 있는가?

점수

그룹 | 점수 | 제한

1 | 10 | $n \leq 10^{3}$

2 | 15 | $n \leq 10^{6}$

3 | 20 | $n \leq 10^{18}$

4 | 25 | $n = 10^{k}$, 여기서 $0 \leq k \leq 50$이다. ($n$은 $100\dots$ 형태이다.)

5 | 30 | 추가 제한 없음

입력의 첫째 줄에는 Arnar와 Arnar가 아는 가장 큰 수인 하나의 정수 $n$ ($1 \leq n \leq 10^{50}$)이 주어진다.

Arnar와 Arnar가 모은 수 중 마음에 드는 수의 개수를 출력한다.