One day, TA of one of the course at DA-IICT was checking First In-sem exam papers. The exam was of 20 marks. After checking some of the papers, he decided to give marks of those students to his professor but he messed up here. He forgot to put spaces between the marks. So professor got confused.

Since you are his favourite student, help him determine the number of ways in which this marks can be separated (by spaces) so that they are valid marks.

Marks are valid if they are between 0 to 20 and have no leading zeros. For example, 0, 1, 2, 3 ... 20 are valid but 01, 003, 21, 25 are not valid.

Input

Input contains only one line, a string of length less than 20 .

Output

Output the number of ways in which you can put spaces and interpret them as a valid marks of students.

Example

Input 1:
12

Output 1:
2

Input 2:
111

Output 2:
3

Input 3:
101

Output 3:
2

Explanation:

In the first case, 12 can be interpreted in two ways,

1. 1, 2
2. 12

In the second case, 111 can be interpreted as following ways.

1. 1, 1, 1
2. 11, 1
3. 1, 11

In the third case,

1. 1, 0, 1
2. 10, 1

Note that 1, 01 can not be valid because 01 has leading zeros.