bp

def count_num(s):
    a = [[0, 0, 0] for _ in range(len(s))]
    a[0][int(s[0])%3] = 1
    for i in range(1,len(s)):
        n = int(s[i])
        if n%3 == 0:
            a[i][0] = a[i - 1][0] * 2 + 1
            a[i][1] = a[i - 1][1] * 2
            a[i][2] = a[i - 1][2] * 2
        elif n%3 == 1:
            a[i][0] = a[i - 1][2] + a[i - 1][0]
            a[i][1] = a[i - 1][0] + a[i - 1][1] + 1
            a[i][2] = a[i - 1][1] + a[i - 1][2]
        elif n%3 == 2:
            a[i][0] = a[i - 1][1] + a[i - 1][0]
            a[i][1] = a[i - 1][2] + a[i - 1][1]
            a[i][2] = a[i - 1][0] + a[i - 1][2] + 1

    print(a[-1][0]%1e9+7)

a[i][n] 表示i个数余数为n的子序列个数

a[i]%3 == 0 时,a[i-1][0]每一个子序列加上a[i]都成为一个新的余数为0的子序列
选择a[i]， a[i][0] = a[i-1][0] + 1 (加上只选a[i]自己的一个子序列)
a[i][1] = a[i-1][1] 每个子序列都加上了a[i]
a[i][2] = a[i-1][2]
不选择a[i], a[i][0] = a[i-1][0]
a[i][1] = a[i-1][1]
a[i][2] = a[i-1][2]
选择a[i]不影响其他余数 故a[i][0] = a[i-1][0]2+1 ,a[i][1] = a[i-1][1]2, a[i][2] = a[i-1][2]*2

a[i]%3 == 1 时，a[i-1][2]每一个子序列加上a[i]都成为一个新的余数为0的子序列,a[i-1][1]每一个子序列加上a[i]都成为一个新的余数为2的子序列，
a[i-1][0]每一个子序列加上a[i]都称为一个新的余数为1的子序列
选择a[i], a[i][0] = a[i-1][2]
a[i][1] = a[i-1][0] + 1 (加上只选a[i]自己的一个子序列)
a[i][2] = a[i-1][1]
不选择a[i], a[i][0] = a[i-1][0]
a[i][1] = a[i-1][1]
a[i][2] = a[i-1][2] + 1 (加上只选a[i]自己的一个子序列)
故a[i][0] = a[i-1][2]+a[i-1][0], a[i][1] = a[i-1][0]+a[i-1][1] ,a[i][2] = a[i-1][1]+a[i-1][2]

a[i]%3 == 2 时，a[i-1][2]每一个子序列加上a[i]都成为一个新的余数为1的子序列,a[i-1][1]每一个子序列加上a[i]都成为一个新的余数为0的子序列，
a[i-1][0]每一个子序列加上a[i]都称为一个新的余数为2的子序列
选择a[i], a[i][0] = a[i-1][1]
a[i][1] = a[i-1][2]
a[i][2] = a[i-1][0]
不选择a[i], a[i][0] = a[i-1][0]
a[i][1] = a[i-1][1]
a[i][2] = a[i-1][2]

故a[i][0] = a[i-1][1]+a[i-1][0], a[i][1] = a[i-1][2]+a[i-1][1] ,a[i][2] = a[i-1][0]+a[i-1][2]