Assessment#427
Vasyl loves programming and is also fond of science fiction. Once, during vacation, after reading books with his friend Petro, Vasyl decided to devise a formula to show the growth of the population on Mars. According to Vasyl's calculations, after years, the population of Martians should be s_n. The value s_n is determined by the formula:
After hearing Vasyl's theory, Petro had doubts and decided to calculate this number on his computer to verify it. Furthermore, Petro recently read a book about programming and thinks it will not take much time.
You are invited to perform the same calculation, but without reading a smart book. Note that, for convenience, output s_n modulo .
The first line contains the number of tests . Each of the following lines contains two integers: — the age of Mars, and — the modulo (0 < n \leq 10^9, 0 < m \leq 10^9).
For each test, output the expected number of Martians after years modulo .
Example 1