문제

다다스는 프로그래밍 대회 국가대표를 선발하는 국대섬에 초청받았다. 그 이유는, 다다스가 아주 이상한 숫자를 빠르게 세는 능력이 있기 때문이다.

다다스가 좋아하는 숫자는 아래 조건을 만족해야 한다:

• 이상 이하의 정수 중에서, 자릿수에 사용된 숫자들의 총합이 정확히 가 되어야한다.
• 숫자 안에 연속으로 번 이상 같은 숫자가 나오는 구간이 존재하지 않아야한다.
  • 예시로 1123은 1이 연속으로 2번만 나오니, 일 경우에 허용된다.
  • 하지만 1113은 1이 연속으로 3번만 나오니, 일 경우에 불허용된다.

하지만 다다스는 국대가 되기전 학교 내신을 끝내야해서, 다다스를 대신해 이성원이 국대섬에 초청받았다. 하지만 이성원에게 숫자를 빠르게 세는 방법을 모른다. 이성원을 도와 이상 이하의 정수 중, 위 조건을 만족하는 수의 개수를 구해보자!

입력

첫 번째 줄에 정수 , , , 가 주어진다.

출력

조건을 만족하는 수의 개수를 출력한다.