Problem B

To prepare for ACM-ICPC 2017 in Saigon, the host univeristy – Ho Chi Minh city University of Education (HCMUE) – decided to print barcodes on the participants’ t-shirts. The barcode requirement needs to be simple to reduce the cost but still show some scientific style. HCMUE decided that every barcode consists of red bars and blue bars satisfing at least one of the following conditions:

  • The number of blue bars is equal to the number of red bars.

  • There are no $2$ consecutive blue bars.

Let $K$ denote the number of different ways to create the required barcodes containing $N$ bars. Given two integers $N$ and $M$, where $M$ is a prime number, your task is to help them identify the remainder of $K$ divided by $M$.


The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than $20$. Each dataset is described by one line containing two numbers $N$ and $M$ ($1 \leq N \leq 10^6$, $1 < M \leq 10^7$). $M$ is a prime number.


For each dataset, write in one line the remainder of $K$ divided by $M$.

Sample Input 1 Sample Output 1
1 997
2 997
3 997
5 997
7 997
9 997
CPU Time limit 1 second
Memory limit 512 MB
Source The 2017 ACM - ICPC Asia Ho Chi Minh City Regional Contest
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in