Problem Description

Before leaving this world, Mayuri wants to find her Lucky Number.

Mayuri will provide a number \( a \) and a 01 string \( S \) of length \( b \).

Simply put, her Lucky Number is a positive integer \( n \) that satisfies the following conditions:

• \( n \) has \( b \) digits and does not have leading zeros.
• If the \( i \)-th digit of \( S \) is 1, then the number formed by the first \( i \) digits of \( n \) is a multiple of \( a \); otherwise, it is not a multiple of \( a \).

The number formed by the first \( i \) digits of a number refers to the number formed by concatenating the first \( i \) digits sequentially. For example, the first 3 digits of 312311 form the number 312, and the first 5 digits form the number 31231.

Now, please help Mayuri calculate her Lucky Number. Since there may be multiple numbers that satisfy the conditions, you need to output the smallest one. If no such number exists, output -1.

Input Format

The input data consists of two lines.

The first line contains two integers \( a \) and \( b \), as described in the problem.

The second line contains a string \( S \) of length \( b \).

Output Format

One line, the smallest number \( n \) that satisfies the conditions. If no such number exists, output -1.

Sample Input and Output

Sample Input #1

2 2
01

Sample Output #1

10

Sample Input #2

10 1
1

Sample Output #2

-1

Sample Input #3

6 6
110100

Sample Output #3

601210

Notes/Hints

For convenience, an additional test case is provided for contestants to test their code.

Sample Input Sample Output

Sample Explanation

For the first sample, 10 is a 2-digit number, and the number formed by its first 1 digit, 1, is not a multiple of 2, while the number formed by its first 2 digits, 10, is a multiple of 2. Since 10 is the smallest 2-digit number, there is no smaller number that satisfies the conditions.

For the second sample, we need to construct a 1-digit number that is divisible by 10. Obviously, no such number exists.

Data Range

This problem uses subtask scoring

For all data, it is guaranteed that \( 2 \leq a \leq 10 \), \( 1 \leq b \leq 10^5 \), and \( S \) contains only 0 and 1.

见题面 Input 部分

见题面 Output 部分