Hash Collision

Tommy’s encryption system uses the following string hash algorithm:

int Hash(string s, int base, int mod) {
  int result = 0;
  for (int i = 0; i < s.length(); i++)
    result = (1LL * result * base + s[i]) % mod;
  return result;
}

Here \(\texttt{base}\) and \(\texttt{mod}\) are given parameters satisfying \(257 \le \texttt{base} \le \texttt{mod} \le 10^9+9\), and \(\texttt{mod}\) is a prime number.

Dream now wants to break Tommy’s cipher. As a first step, he needs to find a valid hash collision. Given \(\texttt{base}\), \(\texttt{mod}\), and a string \(S\), please find another string \(T\) with the same length as \(S\) such that:

• \(|S| = |T|\),
• \(\texttt{Hash}(S)=\texttt{Hash}(T)\) (where the hash is computed as above; note that the computation is done in integer arithmetic modulo \(mod\)),
• but \(S\) and \(T\) differ in at least one position.

If there are multiple valid answers, you may output any one.

Note: You may assume the input string \(S\) has length at least 2.

inputFormat

The input consists of a single line containing two integers \(\texttt{base}\) and \(\texttt{mod}\) followed by the string \(S\), separated by spaces.

For example:

257 1000000007 ab

outputFormat

Output a string \(T\) satisfying the requirements. If there is no solution (for instance when \(|S| < 2\)), you may output -1.

sample

257 1000000007 ab

`ţ