Alphanumeric Combinations

A digit string can be split, in order, into integers 1..26, which map to a..z. Each valid split corresponds to one word; a leading zero cannot be decoded on its own or as part of 01..09.

输入格式

A single line containing a digit string S. This site adds 1≤|S|≤1000 with characters only 0..9, so that the output fits within this problem's judging output limit.

输出格式

Output the number of valid decodings as a decimal integer; output 0 if there is no valid decoding.

样例 1

输入：

2112

输出：

5

样例 2

输入：

2101

输出：

1

样例 3

输入：

100

输出：

0