CSL的密码

发布时间: 2018年6月14日 17:53   最后更新: 2018年6月15日 12:49   时间限制: 1000ms   内存限制: 256M

众所周知,CSL最喜欢的密码是******。

为了改变这一点,他随机生成了一个数字串,并打算去掉一些数字作为他的新密码。

他的密码需要满足以下条件:

  • 密码必须是$3$的倍数,且不能为$0$。
  • 密码中不能含有前导零。

由于他生成的字符串太长了,他希望你帮他数一下他有多少种不同的选择。

两种方案不同当且仅当去掉的数字的位置不同。

第一行有一个整数$T$,表示测试数据的组数。
对于每组测试数据,有一个数字$n$。
$T \leq 1000$
$1 \le n \le 10 ^{5000}$

对于每组测试数据,在一行内输出答案,由于这个数可能很大,请将其对$10^9 + 7$取模。CSl

复制
6
100000
111000
100011
100023
123456
123456789012345678901234567890
0
8
8
17
23
357566622

dp

ACM集训队暑期集训热身赛