그래프 세기

먼저 무방향 연결 레이블 그래프를 정의하자. 이는 각 노드에 고유한 레이블이 붙은 N개의 노드와 여러 간선으로 이루어진 그래프로, 각 간선에는 특정한 방향이 없고, 중복 간선과 한 노드에서 자기 자신으로 가는 간선은 허용되지 않으며, 임의의 노드에서 다른 임의의 노드로 도달할 수 있다.

이런 그래프에서 단절선이란, 그 간선을 제거하면 그래프가 분리되는(서로 도달할 수 없는 노드가 존재하게 되는) 간선을 말한다.

이 문제에서는 N과 K가 주어지며, 정확히 N개의 노드와 K개의 단절선을 가진 서로 다른 무방향 연결 레이블 그래프의 개수를 세는 것이 과제이다. 그 수가 매우 클 수 있으므로 M으로 나눈 나머지를 출력한다.

간선은 그것이 연결하는 노드의 레이블로 정의한다. 예를 들어 (X, Y)는 X와 Y 사이의 간선이라고 할 수 있고, (Y, X)는 같은 간선으로 본다(무방향이기 때문이다). 두 그래프는 한쪽에만 존재하는 간선이 있으면 서로 다른 것으로 본다.

프로그램은 하나 이상의 테스트 케이스에 대해 검사를 받는다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T (1 ≤ T ≤ 100)가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 공백으로 구분된 3개의 정수 N (1 ≤ N ≤ 50), K (0 ≤ K < N), M (1 ≤ M ≤ 109)을 포함하는 한 줄이다. 이들은 문제에서 설명한 수들이다.

전체 테스트 케이스의 95%에서 N은 25를 넘지 않는다.

각 테스트 케이스마다 위에서 설명한 그래프의 개수를 M으로 나눈 나머지를 한 줄에 출력한다.

다음은 첫 번째 테스트 케이스에 대한 3개의 그래프이다.

다음은 두 번째 테스트 케이스에 대한 유일한 그래프이다.