{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eTo prepare for ACM-ICPC 2017 in Saigon, the host univeristy\n – Ho Chi Minh city University of Education (HCMUE) – decided to\n print barcodes on the participants’ t-shirts. The barcode\n requirement needs to be simple to reduce the cost but still\n show some scientific style. HCMUE decided that every barcode\n consists of red bars and blue bars satisfing at least one of\n the following conditions:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe number of blue bars is equal to the number of red\n bars.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThere are no \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e\n consecutive blue bars.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eLet \u003cspan class\u003d\"tex2jax_process\"\u003e$K$\u003c/span\u003e denote the\n number of different ways to create the required barcodes\n containing \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e bars. Given\n two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e is a prime number, your task is to\n help them identify the remainder of \u003cspan class\u003d\"tex2jax_process\"\u003e$K$\u003c/span\u003e divided by \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of several datasets. The first line of\n the input contains the number of datasets, which is a positive\n number and is not greater than \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e. Each dataset is described by one\n line containing two numbers \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq N \\leq 10^6$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \u0026lt;\n M \\leq 10^7$\u003c/span\u003e). \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e\n is a prime number.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eFor each dataset, write in one line the remainder of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$K$\u003c/span\u003e divided by\n \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6\n1 997\n2 997\n3 997\n5 997\n7 997\n9 997\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3\n5\n13\n34\n89\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}