题目内容

现有一个长度为 $n$ 的数字模式串 $s$，其中某些字符因污损而无法辨认，用 '?' 表示。你需要将每个 '?' 替换为一个十进制数字（0-9），使得最终得到的整数没有前导零（即最高位不能是 0），并且该整数能被 3 整除。请你计算所有满足条件的替换方案总数，并对 $10^9+7$ 取模输出。

数据范围：

• 字符串长度 $n$ 满足 $1 \le n \le 10^5$。
• $s$ 仅由数字和 '?' 组成，且第一个字符不会是 '0'。若第一个字符为 '?'，则替换时只能选择 1 到 9 中的数字；其余位置的 '?' 可以替换为 0 到 9 中的任意数字。
• 答案需要对 $10^9+7$ 取模。

输入描述

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示字符串的长度。