An old phone keypad maps digits to letters as follows: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz.
You are given a string of digits, each between 2 and 9. For each position you choose one letter from that digit's set, producing a letter string of the same length as the digit string. Count how many distinct resulting letter strings have no two ADJACENT positions holding the same letter (that is, result[i] != result[i+1] for every valid i).
Input format
Line 1: a string of digits, each character in 2-9.
Output format
A single integer: the number of valid letter strings with no two adjacent equal letters.
Constraints
- 1 ≤ length of the digit string ≤ 8