D-Disgusting Relationship_2020牛客暑期多校训练营（第八场）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

There are n people falling in love. Everybody has a unique people he/she loves, and somebody love themselves. But they have a secret agreement: no two people love the same one. To satisfy such a relationship between n people, we call it a $\textbf{love relationship}$ , denoted by $\mathcal{R}$ . Obviously, there are n! different $\textbf{love relationships}$ for n people. And a $\textbf{love relationship}$ can be presented as a permutation. For example, if n = 3, $\mathcal{R} = [3,1,2]$ means the first people loves the third people, the second people loves the first people, the third people loves the second people.
if A loves B, and B loves C, and C loves A, then we call the relationship between these 3 people $\textbf{3-love polygon}$ . and so on, we can easily define $\textbf{k-love polygon}$ for each integer k. Extraordinary, if A loves B and B loves A, we call them $\textbf{2-love polygon}$ . If A loves himself, we call it $\textbf{1-love polygon}$ .

Apollo said proudly to Avery: If I konw "how many $\textbf{k-love polygon}$ are there in this relationship" for each k, Then I can easily tell you how many relationship combinations might be legal for these n people.
But Avery said: No, It's not enough. Let's use $f(a_1, a_2, a_3, ..., a_n)$ to denote the number of $\textbf{love relationships}$ of n people, which can form $a_1$ $\textbf{1-love polygon}$ , $a_2$ $\textbf{2-love polygon}$ , ...,and $a_n$ $\textbf{n-love polygon}$ . If one relationship $\mathcal{R}$ of n people can form $a_1$ $\textbf{1-love polygon}$ , $a_2$ $\textbf{2-love polygon}$ , ..., $a_n$ $\textbf{n-love polygon}$ , and $f(a_1, a_2, a_3, ..., a_n)$ is divisible by my favourite number P, then I will feel the relationship $\mathcal{R}$ is disgusting. I will tell you my favourite number P, and could you calculate how many relationships are $\textbf{not}$ disgusting between these n people? I know this might be too difficult to you, so you can just tell me how many $\textbf{different types}$ of $\textbf{love relationships}$ are $\textbf{not}$ disgusting.

$\textbf{Different type}$ : for relationships $\mathcal{R}_a$ and $\mathcal{R}_b$ , if $\mathcal{R}_a$ will let there be $a_k$ k-love polygons for each $k \in \mathbb{N}_+$ , $\mathcal{R}_b$ will let there be $b_k$ k-love polygons for each $k \in \mathbb{N}_+$ , and there exist at least one i, such that $a_i \neq b_i$ , then we call love relationships $\mathcal{R}_a$ and $\mathcal{R}_b$ are $\textbf{different types}$ .

Apollo could not handle this task very well. Could you help him?

输入描述:

The first line is an integer  (), which is the number of test cases.

Each test case consists of one line with two integers n () and P (, P is a prime).

输出描述:

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is answer. Answer may be very large, so just output the answer mod 1,000,000,007.

示例1

输入

复制

输出

复制

Case #1: 2
Case #2: 2
Case #3: 5
Case #4: 2

说明

For n = 4, there are 5 different types of love relationships:
f(4, 0, 0, 0) = 1: 
f(2, 1, 0, 0) = 6: , , , , , 
f(1, 0, 1, 0) = 8: , , , , , , , 
f(0, 2, 0, 0) = 3: , , 
f(0, 0, 0, 1) = 6: , , , , , 

If P = 2, the first and the fourth type can meet the requirements.
If P = 3, the first and the third type can meet the requirements.
If P = 5, all types can meet the requirements.