You are given a string made only of digits. You must insert exactly three dots into it, splitting it (without reordering or removing any digit) into four non-empty consecutive parts, in order. Each of the four parts must be a valid IPv4 octet: it must represent an integer between 0 and 255 inclusive, and it must not contain a leading zero unless the part is exactly the single character 0.
Count the number of distinct ways to place the three dots so that all four resulting parts are valid octets.
Input format
Line 1: a string s of digit characters 0-9.
Output format
A single integer: the number of valid ways to split s into four valid octets.
Constraints
- 4 ≤ length of s ≤ 12
- s contains only digit characters.