AT_kupc2017_c.Best Password

京都大学的一栋建筑物只有知道密码的人才能通过认证并进入。

密码是由小写英文字母组成的字符串，作为建筑物的用户，你已经知道了这个密码。

这个认证系统会对输入的密码计算其哈希值，并通过该哈希值进行比对。

长度为 $N$ 的字符串 $S$ 的哈希值的计算如下：设 $S_i$ 表示第 $i$ 个字符，则有

$A^1 \times C[S_1] + A^2 \times C[S_2] + \cdots + A^N \times C[S_N]$

其中 $A$ 是一个固定整数，满足 $2 \leq A \leq 10$，并且规定 $C[a]=1$，$C[b]=2$，$\cdots$，$C[z]=26$。

你非常忙碌，希望能够用尽可能短的输入完成认证。

请你求出与原密码哈希值相同的最短字符串。如果有多个满足条件的字符串，请输出字典序最大的一个。

输入为一行，格式如下：

$A$ $S$

请输出满足条件的字符串，共一行。

数据范围

• $2 \leq A \leq 10$
  • $A$ 是整数。
• $1 \leq |S| \leq 1000$
  • $S$ 是由小写字母组成的字符串。

样例解释1

原字符串的哈希值为 $2^1 \times 11 + 2^2 \times 21 + 2^3 \times 16 + 2^4 \times 3 = 282$。输出字符串的哈希值同样为 $2^1 \times 25 + 2^2 \times 26 + 2^3 \times 16 = 282$。

样例解释4

哈希值有可能非常大。

由 ChatGPT 5 翻译