Maximum Edge Count in Graphs Without Simple Paths of Length 3

You are given a large prime number \(P\) and \(q\) queries. In each query, a positive integer \(n\) is provided. You need to count the number of labeled undirected graphs satisfying the following conditions, and output the answer modulo \(P\):

1. The graph has \(n\) vertices and contains neither multiple edges nor self-loops.
2. The graph does not contain any simple path of 3 edges. Formally, a path passing through vertices \(u_1, u_2, \dots, u_k\) is called a simple path if all \(u_i\) are distinct. In particular, there must not exist four pairwise distinct vertices \(u_1, u_2, u_3, u_4\) with edges \((u_1,u_2)\), \((u_2,u_3)\), and \((u_3,u_4)\) all present in the graph.
3. Among all graphs that satisfy conditions 1 and 2, the graph has the maximum possible number of edges.

It can be shown that the answer depends on \(n\) as follows:

• If \(n = 1\), the only graph has 0 edges.
• If \(n = 2\), the maximum is 1 edge.
• If \(n = 3\), a triangle (complete graph on three vertices) is possible with 3 edges.
• If \(n \ge 4\), the graph achieving the maximum number of edges is a star graph, which has \(n-1\) edges.

Your task is to compute the answer \(A(n)\) modulo \(P\) for each query, where:

[ A(n) = \begin{cases} 0, & \text{if } n = 1,\ 1, & \text{if } n = 2,\ 3, & \text{if } n = 3,\ n - 1, & \text{if } n \ge 4. \end{cases} ]

</p>

Note: The graph is labeled, which means vertices are distinguishable. The input contains the prime \(P\) (used as the modulus) and \(q\) queries.

inputFormat

The first line contains two positive integers: a large prime \(P\) and the number of queries \(q\) (1 ≤ q). Each of the following \(q\) lines contains one positive integer \(n\) (\(1 \le n\)).

For example:

1000000007 3
1
2
3

outputFormat

For each query, output a single integer denoting \(A(n) \bmod P\) on a separate line.

For the sample input above, the output should be:

0
1
3

sample

1000000007 3
1
2
3

0
1
3

</p>