생성 트리 세기

최근 Alex는 무방향 연결 그래프의 생성 트리 개수를 세는 기법에서 놀라운 진전을 이루었다. 그는 다음 사실을 알아냈다.

• n개의 정점으로 이루어진 사이클에는 서로 다른 생성 트리가 n개 있다.
• n개의 정점으로 이루어진 완전 그래프에는 서로 다른 생성 트리가 n``n−2개 있다.

이 두 발견으로 Alex는 매우 기뻐졌고, 생성 트리 세기 모험을 계속하려 한다. 즉, 그는 여러 가지 그래프에서 생성 트리의 개수를 셀 수 있기를 바란다.

어느 날 Alex는 친구들과 만난다. 모두 큰 원탁 둘레에 둥글게 앉았다. 그 모습을 본 Alex는 곧바로 생성 트리 문제를 떠올린다. 친구 각각을 정점으로 보고 이웃한 친구(거리가 1인 정점)끼리 간선으로 이어져 있다고 하면 이는 사이클이 된다. 그러나 Alex는 사이클에서의 계산을 이미 완전히 익혀 더는 흥미가 없다. 그래서 그래프를 조금 바꾸었다. 이웃한 친구끼리만 간선을 추가하는 것이 아니라, 한 자리를 사이에 두고 떨어진 친구(거리가 2인 정점)끼리도 간선을 추가한다. 이제 간선 하나로 이어진 친구끼리는 인접하다고 본다. 이는 다음 그림과 같다.

Alex는 이런 종류의 그래프에서 생성 트리의 개수를 세어 본 적이 없지만, 어떤 그래프에서든 생성 트리의 개수를 세는 일반적인 방법이 있다고 선생님이 설명해 주셨던 것을 기억한다. 먼저 n×n 행렬 A = { ai j }를 다음과 같이 만든다.

여기서 di는 정점 i의 차수이다.

위 그림과 같은 원탁 그래프에 대응하는 행렬 A를 만들어 보자. 생성 트리의 개수를 세려면 A의 마지막 행과 마지막 열을 제거하여 얻은 (n−1)×(n−1) 행렬 B를 구하기만 하면 된다. 행렬 B의 행렬식을 계산하면 위 그래프의 생성 트리 개수가 나온다.

따라서 이 그래프의 생성 트리 개수는 |B| = 3528이다. Alex는 일반적인 방법을 쓰면 계산이 매우 복잡하고 번거롭다는 것을 알아차렸다. 그렇지만 이보다 더 간단한 다른 공식을 찾지 못했다. 그래서 그래프를 단순화했다. 어느 지점에서 원탁 둘레를 끊어 버린 것이다. 그러면 친구들은 정점의 사슬을 이루게 되고, 거리가 1이거나 거리가 2인 모든 정점 쌍 사이에 간선이 존재한다. 정점이 8개인 경우는 다음 그림과 같다.

이렇게 하면 생성 트리의 총 개수가 크게 줄어든다. Alex는 모임이 끝날 때까지 계속 생각한다. 마침내 그는 이 그래프의 생성 트리 개수를 세는 효율적인 방법을 떠올린다. 그러나 거리가 3인 정점끼리도 이어 붙이기로 하면, 그는 다시 답을 효율적으로 구하는 방법을 알지 못한다. 이런 종류의 그래프에서 생성 트리의 개수를 세도록 Alex를 도와주자!

입력은 공백으로 구분된 두 정수 k와 n을 포함한다. k는 그래프에서 거리가 k 이하인 모든 정점 쌍을 간선으로 연결한다는 뜻이다. n은 전체 정점의 개수가 n개임을 나타낸다.

그래프의 생성 트리 개수를 정수 하나로 출력한다. 답이 매우 클 수 있으므로 답을 65521로 나눈 나머지를 출력해야 한다.

• k ≤ 5
• n ≤ 1015