统计打字方案数

题目描述

Alice 使用手机九宫格键盘给 Bob 发微信消息。九宫格数字到字母的映射关系如下：

• 2 → "abc"
• 3 → "def"
• 4 → "ghi"
• 5 → "jkl"
• 6 → "mno"
• 7 → "pqrs"
• 8 → "tuv"
• 9 → "wxyz"

为了输入一个字母，Alice 需要按下对应数字键若干次，次数等于该字母在该键位上的位置（从 1 开始）。例如：

• 按 '2' 一次得到 'a'，两次得到 'b'，三次得到 'c'
• 按 '7' 四次得到 's'

注意：数字 '0' 和 '1' 不对应任何字母，因此不会出现在输入中。

由于传输错误，Bob 没有收到原始文字，而是收到了 Alice 按下的按键序列字符串。例如，若 Alice 发送 "bob"，Bob 会收到 "2266622"。

现在给你 Bob 收到的按键字符串 pressedKeys，请你计算 Alice 可能发出的不同文字信息的总数。

由于答案可能非常大，请将结果对 $10^9 + 7$ 取模后返回。

输入格式

一行，一个字符串 pressedKeys，仅包含字符 '2' 到 '9'。

输出格式

一个整数，表示可能的文字信息种数对 $10^9 + 7$ 取模后的结果。

示例

示例 1

输入：

22233

输出：

8

解释：
Alice 可能发出的文字信息包括：
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae", "ce"。
共 8 种。

示例 2

输入：

222222222222222222222222222222222222

输出：

82876089

解释：
总共有 2082876103 种可能信息，取模 $10^9 + 7$ 后为 82876089。

数据范围

• $1 \leq \text{pressedKeys.length} \leq 10^5$
• pressedKeys 中只包含字符 '2' 到 '9'