33662번 - 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

$x_i:=2^{i-1}x \bmod p$, and $b_i:=x_i \bmod 2$.

Rem has been playing for a while, and thinks they have enough information to guess the secret $x$. Given $p$ and the first $\left\lceil\log_2⁡(p)\right\rceil$ "random" bits, return the secret $x$ for Rem.

Input consists of a prime number $p$, ($2≤p<10^9$) and a binary string $b_1b_2\cdots b_{\left\lceil\log_2⁡(p)\right\rceil}$ as described above.

Display the value of $x$ reduced modulo $p$. That is, the value of the secret seed $x$.