Problem:

C: カニサル暗号

問題

えびちゃんは、ある非負整数 D を「カニサル暗号」で暗号化して得られた文字列 C を与えられました。この暗号は、非負整数を 10 進法で表したときの各数字をある（元と異なるとは限らない）決められた数字で置き換えるものです。異なる数字が同じ数字に置き換えられたり、同じ数字が出現位置によって異なる数字に書き換えられることはありません。

たとえば、この暗号化方式によって 2646 が 0545 になることはありますが、3456 が 1333 になったり 1333 が 3456 になることはありません。

いま、えびちゃんは D を 10^9+7 で割った余りが M になることを教えてもらいました。このとき、D として考えられるものを一つ出力してください。複数考えられる場合はどれを出力しても構いません。ただし、D の先頭には余分な 0 はついていないものとします。

入力形式

M
C

制約

0\leq M < 10^9+7

1\leq |C| \leq 10^5

出力形式

D として考えられる非負整数を一行に出力してください。存在しない場合は -1 を出力してください。

入力例1

2
1000000007

出力例1

1000000009

今回の暗号化方式は、0 を 0 に、1 を 1 に、9 を 7 に置き換えるものでした。

入力例2

3
1000000007

出力例2

-1

入力例3

1
01

出力例3

-1

D の先頭に余分な 0 がついていることはありません。

入力例4

45
1000000023

出力例4

6000000087

1000000052 や 2000000059 なども条件を満たすので、それを出力してもかまいません。

入力例5

0
940578326285963740

出力例5

123456789864197523



Sample input:
2
1000000007


Sample output:
1000000009

Submission status: Accepted

Solution code:
# 半分全列挙
from itertools import permutations, combinations
M = int(input())
C = list(map(int, input()))
if len(C)==1 and M==0:
    print(0)
    exit()
mod = 10**9 + 7
L = [0] * 10
b = 1
for c in C[::-1]:
    L[c] += b
    b = b * 10 % mod

for t_half1 in combinations(range(10), 5):
    L1, L2 = L[:5], L[5:]
    t_half2 = list(set(range(10)) - set(t_half1))
    if int(C[0]) < 5:
        s1 = {sum(l * n for l, n in zip(L1, t1)) % mod: t1 for t1 in reversed(list(permutations(t_half1))) if t1[int(C[0])] != 0}
    else:
        s1 = {sum(l * n for l, n in zip(L1, t1)) % mod: t1 for t1 in reversed(list(permutations(t_half1)))}
    for t2 in permutations(t_half2):
        s = sum(l * n for l, n in zip(L2, t2))
        if (M-s) % mod in s1:
            t = s1[(M-s) % mod] + t2
            if t[int(C[0])] != 0:
                print("".join(map(lambda x: str(t[x]), C)))
                exit()
print(-1)