Company: Goldman sachs_4nov
Difficulty: medium
Alphanumeric Combinations John is teaching his son Rob the English alphabet and counting. He treats a as the 1st letter, b as the 2nd, and so on up to z as the 26th. John says that kite can be written as 119205 , because k is the 11th letter, i the 9th, t the 20th and e the 5th. Rob, being quicker than his father, points out that 119205 could also mean aaite from (1)(1)(9)(20)(5), or aste from (1)(19)(20)(5), and several others. John now wants to know, for a given string of digits, how many words it can stand for. Task Given a string S of digits, count the ways to split it into consecutive blocks so that every block is the position of a letter. A block of one digit must be between 1 and 9 . A block of two digits must be between 10 and 26 , which means a two-digit block can never start with 0 . Every digit of S must belong to exactly one block. Input Format A single line containing the string S . Output Format Print a single integer, the number of words S can stand for. Print 0 when the