{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe Floppy Cube is essentially a 1 × 3 × 3 Rubik’s Cube. It is made up of 9 identical cubic pieces arranged into a 1 × 3 × 3 cuboid. The puzzle consists of 4 corner pieces, 4 edge pieces and 1 centre piece. Each corner piece has four colours each, each edge piece has three colours each, while the centre piece has two colours (on the opposite faces). The puzzle can be thought of as twisting around its edge pieces. Each twist causes one edge piece to rotate 180 degrees in place, and the two adjacent corner pieces to swap position (while also being rotated). Of course, rotating or flipping the entire Floppy Cube are available moves as well. The purpose of the puzzle is to restore it to the state of having one colour per face.\u003c/p\u003e\n\u003cp\u003eSuppose that we wish to apply new colour stickers to a Floppy Cube in a colouring which is not necessary to be a standard colouring. Specifically, we have n different colours available (with an unlimited supply of stickers of each colour), and we place one sticker on each of the 30 faces in any arrangement that we please. We are not required to use all the colours, and if desired the same colour may appear in more than one face of a single cubic piece.\u003c/p\u003e\n\u003cp\u003eWe say that two such colouring c1 and c2 are essentially distinct if a cube coloured according to c1 cannot be made to match a cube coloured according to c2 by performing mechanically possible Floppy Cube moves. How many essentially distinct colourings are there with n different colours available?\u003c/p\u003e\n\u003ch2 id\u003d\"input\"\u003eInput\u003c/h2\u003e\n\u003cp\u003eThe input has several test cases, and the first line contains an integer T (1 ≤ T ≤ 22222) which is the total number of test cases. For each case, a line contains two integers n and P where 1 ≤ n, P ≤ 111111111.\u003c/p\u003e\n\u003ch2 id\u003d\"output\"\u003eOutput\u003c/h2\u003e\n\u003cp\u003eFor each case, calculate the number of distinct colouring with n different colours available, and output the remainder when it divided by P.\u003c/p\u003e\n"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e3\n1 32145\n2 32145\n3 32145\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n6738\n30690\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}