IP-주소

IPv4-주소는 마침표로 구분된, 각각 선행 영이 없어야 하는 $0$에서 $255$ 사이의 정수 네 개로 이루어진다. 예를 들어 1.0.3.255은 유효한 주소이지만, 1.0.03.255, 1.0.3.256, 1.0.3은 유효한 주소가 아니다. 숫자들의 수열이 주어질 때, 수열에 마침표 세 개를 삽입하여 만들 수 있는 모든 유효한 IPv4-주소를 찾아라.

첫째 줄에 최소 $4$개, 최대 $12$개의 숫자로 이루어진 문자열이 주어진다.

3개의 마침표를 삽입하여 만들 수 있는 유효한 IP-주소의 개수를 정수 하나로 출력한다.

그룹 | 점수 | 제한

$1$ |$30$| 입력에 영이 포함되지 않는다.

$2$ |$70$| 추가 제한이 없다.

예제 1의 설명: 만들 수 있는 유효한 ip-주소는 255.255.255.255 하나뿐이다. 마침표를 다르게 배치하면 모두 3보다 긴 수가 생긴다.

예제 2의 설명: 숫자가 4개이므로 마침표를 유효하게 배치하는 방법은 하나뿐이다. 숫자 영이 허용되므로 답은 0.0.0.0이 된다.

예제 3의 설명: 마침표를 어떻게 배치하더라도 숫자 영이 아니면서 선행 영이 있는 수가 항상 생긴다. 따라서 답은 0이 된다.

예제 4의 설명: 7개의 문자열을 만들 수 있다$\colon$

• 2.9.18.41

• 2.9.184.1

• 2.91.8.41

• 2.91.84.1

• 29.1.8.41

• 29.1.84.1

• 29.18.4.1