AT_kupc2017_c Best Password

[problemUrl]: https://atcoder.jp/contests/kupc2017/tasks/kupc2017_c 京都大学のある建物にはパスワードを知っている者だけが認証を通り、入ることができます。 パスワードは英小文字からなる文字列であり、建物の利用者であるあなたにはこのパスワードが知らされています。 この認証システムは入力されたパスワードのハッシュ値を求め、そのハッシュ値を使って照合されるというシステムです。 長さ $ N $ の文字列 $ S $ のハッシュ値は、$ i $ 文字目を $ S_i $ として、以下の式で求められます。 $ A^1\ \times\ C[S_1]\ +\ A^2\ \times\ C[S_2]\ +\ ...\ +\ A^N\ \times\ C[S_N] $ ただし $ A $ は $ 2 $ 以上 $ 10 $ 以下の整数の定数であり、$ C[a]=1 $, $ C[b]=2 $, $ ... $, $ C[z]=26 $ です。 あなたはとても忙しく、出来る限り短い入力で認証を済ませたいと考えています。 本来のパスワードと同じハッシュ値を持つような最短の文字列を求めてください。 条件を満たす最短の文字列が複数ある場合は、辞書順最大のものを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ A $ $ S $

求める文字列を $ 1 $ 行に出力せよ。

### 制約 - $ 2\ \leq\ A\ \leq\ 10 $ - $ A $ は整数である。 - $ 1\ \leq\ |S|\ \leq\ 1,000 $ - $ S $ は英小文字からなる文字列である。 ### Sample Explanation 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 $ です。 ### Sample Explanation 4 ハッシュ値は非常に大きくなることがあります。