An old scroll encodes a message as a string of digits 0-9. The cipher maps a group of ONE digit, from 1 to 9, to a single letter (the digit 0 may never stand alone). It also maps a group of TWO consecutive digits whose numeric value is between 10 and 26 inclusive to a single letter. Reading left to right, the scroll is split into such groups with no gaps or overlaps. Count the number of distinct ways to split the entire digit string into valid groups. Since this count can be large, print it modulo 1000000007. (If no valid split exists, print 0.)
Input format
Line 1: a non-empty string of digits s.
Output format
A single integer: the number of valid ways to decode s, modulo 1000000007.
Constraints
- 1 ≤ length of s ≤ 60
- every character of
sis a digit0-9