#P1940. 2024.8.24-oppo-第3题-数字字符串

2024.8.24-oppo-第3题-数字字符串

题目内容

小塔有一个长度为nn的数字字符串ss，但其中有一些数位被墨水覆盖看不清了。他现在想知道，有多少种可能的数字使得ss是3的倍数（注意：ss不含前导零）。

输入描述

第一行输入一个整数 nn（1≤n≤1051≤n≤10^5）代表数字字符串的长度。

第二行输入一个长度为nn且仅由数字和′?′'?'构成的字符串ss。保证字符串不包含前导零。

输出描述

在一行上输出一个整数，代表满足是33的倍数的数字个数。由于答案可能很大，请将答案对（109+710^9+7）取模后输出

样例1

输入

4
12?4

输出

3

知识点:*****

查看知识点以及同类型题目

Statistics