A message containing letters from A-Z can be encoded into numbers using 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26". Given a string s containing only digits, return the number of ways to decode it.

Example 1:

Input:  12
Output: 2

("AB" or "L")

Example 2:

Input:  226
Output: 3

("BZ", "VF", "BBF")

Example 3:

Input:  06
Output: 0

Constraints:

• 1 ≤ s.length ≤ 100
• s contains only digits and may contain leading zeros

Input format: A single string of digits.

Output format: Number of decode ways.