Contar Transformaciones (Editorial)

Solución

Por el principio básico de conteo, para un conjunto de elementos que tienen elecciones de c_1,c_2,...,c_n, y las elecciones de cada elemento son independientes, entonces el número total de elecciones es \displaystyle \prod_{i=1}^n c_i = c_1 \cdot c_2 \cdot c_3 ... \cdot c_n, lo mismo se puede aplicar aquí.

Para cada dígito, sea $f(d)$ el número de elecciones posibles, calcula esto para cada 0 \le d \le 9 y luego la respuesta será:

def solve():
    n=int(input())
    x=input()
    choice=[1,4,4,2,4,1,2,1,4,1]
    ans=1
    for i in x:
        ans*=choice[int(i)]
        ans%=(999983)
    print(ans%(999983))
    
for _ in range(int(input())):
    solve()