간선 세기

단순 그래프의 각 연결 요소가 사이클을 최대 하나만 가질 때, 그 그래프를 좋은 그래프라고 부른다.

$n$개의 레이블이 붙은 정점을 가진 모든 좋은 그래프에 대해, 사이클에 속하는 간선의 개수를 세려고 한다.

아주 큰 정수 계산을 피하기 위해, 간선 개수의 합을 $p$로 나눈 나머지를 출력한다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫 줄에는 두 정수 $T$와 $p$가 주어진다 ($1 \le T \le 3000$, $1 \le p \le 2^{30}$). $T$는 테스트 케이스의 수이고, $p$는 나눗셈의 나머지를 구할 때 쓰는 수이다. 각 테스트 케이스는 다음과 같다.

첫 줄에 정수 $n$이 하나 주어진다 ($1 \leq n \leq 3000$).

각 테스트 케이스마다 간선 개수의 합을 $p$로 나눈 나머지를 한 줄에 출력한다.

레이블이 붙은 정점 4개를 가진 좋은 그래프 중 사이클이 존재하는 것은 세 가지 종류가 있다.

각 종류의 그래프 수는 $3$, $12$, $4$이다. 따라서 간선 개수의 합은 $3 \times 4 + 12 \times 3 + 4 \times 3 = 60$이다.