HPPROF - Help Professor

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.


Added by:Savan Popat
Date:2013-09-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2015-09-29 19:00:27 Mayank Garg
only silly mistakes can get u WA here .. :( btw easy one !!
2015-06-27 09:26:53 Ankush
ACODE again. Just deleted a single line from my code
2015-06-20 20:47:41 Rishabh Joshi
one '0' case cost me one WA. Exactly the same as ACODE with only one minor difference.
2015-06-06 18:45:10 :.Mohib.:
Awsm que...!! daiictian... ;)
2015-06-01 07:21:48 Sukeesh
Same as ACODE !!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.