Counting Distinct PIN Codes

The BBB (Byteotian Bit Bank) has installed cameras on its cash dispensers. When a client enters his 4-digit PIN while deliberately performing redundant finger movements over the keyboard, the keystrokes become ambiguous. The camera only records the finger movements, not the actual key presses, allowing multiple potential PIN codes to match a single recorded sequence.

For a given recorded sequence (represented as a string of digits), the client may press the key corresponding to each digit any number of times, provided that the total number of pressed keys is exactly 4 and the order of presses follows the sequence order. In other words, if the recorded sequence is denoted by S with elements S[1], S[2], ..., S[m], then the valid PIN codes are those that can be formed by choosing non-negative integers x₁, x₂, ..., x_m such that

[ x_1 + x_2 + \cdots + x_m = 4, ]

and the PIN code is (S[1]) repeated (x_1) times, followed by (S[2]) repeated (x_2) times, and so on. Note that if consecutive characters are identical, they are treated as a single segment because they yield the same digit.

For example, if the recorded sequence is "15", then there are 2 segments: "1" and "5". The number of non-negative integer solutions to \(x_1 + x_2 = 4\) is \(\binom{4+2-1}{4} = \binom{5}{4} = 5\). The possible PIN codes are 1111, 1115, 1155, 1555, and 5555.

inputFormat

A non-empty string of digits representing the sequence of finger movements. For example: 15

outputFormat

An integer representing the number of distinct 4-digit PIN codes that can be formed given the finger movement sequence.

sample

15

5