Problem Statement

A message containing letters from A-Z is being encoded to numbers using the following mapping:

 'A' -> 1
 'B' -> 2
 ...
 'Z' -> 26

Given an encoded message A containing digits, determine the total number of ways to decode it modulo 109 + 7.

Problem Constraints

1 <= |A| <= 105

Input Format

The first and the only argument is a string A.

Output Format

Return a single integer denoting the total number of ways to decode it modulo 109 + 7.

Example Input

Input 1:

 A = "8"

Input 2:

 A = "12"

Example Output

Output 1:

 1

Output 2:

 2