Problem J
Generator Dream
Rem is playing a game that relies on random bits and is starting to get annoyed by all the random chance. Rem wants to win, not to gamble! So, Rem wants your help in avoiding the randomness as much as possible.
The game generates randomness by starting with a secret seed $x$ and a known prime $p$. Then the game generates a sequence of "random" numbers $x_1, x_2, \dots , x_i, \dots $ and "random" bits $b_1, b_2, \dots , b_i, \dots $ by defining
\begin{equation*} x_i := 2^{i-1} x \mod p, \quad \textrm{and} \quad b_i := x_i \mod 2 \, . \end{equation*}Rem has been playing for a while, and thinks they have enough information to guess the secret $x$. Given $p$ and the first $\lceil \log _2(p) \rceil $ "random" bits, return the secret $x$ for Rem.
Input
Input consists of a prime number $p$, ($2 \leq p < 10^9$) and a binary string $b_1b_2 \cdots b_{\lceil \log _2(p)\rceil }$ as described above.
Output
Display the value of $x$ reduced modulo $p$. That is, the value of the secret seed $x$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 110 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 110 |
5 |
| Sample Input 4 | Sample Output 4 |
|---|---|
257 100000010 |
3 |
| Sample Input 5 | Sample Output 5 |
|---|---|
257 110101100 |
173 |
