그래프 변환

그래프의 변환$(f:G \mapsto G')$을 다음과 같이 정의한다. $G$의 간선을 $G'$의 정점으로 보고 $G$의 인접한 간선끼리 $G'$에서 간선으로 연결하여 $G$에서 인접하였음을 나타낸다.

서로 다른 두 간선이 같은 정점을 하나 이상 공유하면 두 간선이 인접한다고 표현한다.

다음은 그래프 변환의 예시 중 하나이다.

그리고 변환한 그래프를 다시 변환하는 것도 가능하다.

$N$-완전 그래프를 $K$번 변환한 그래프의 정점이 몇 개인지 구하시오. $N$-완전 그래프는 정점이 $N$개인 그래프에서 서로 다른 두 정점에 대해 반드시 간선이 존재하는 그래프이다.

첫째 줄에 정수 $N$, $K$가 공백을 사이에 두고 주어진다. $(3 \leq N \leq 100 \\, 000;$ $\\, 0 \leq K \leq 100 \\, 000)$

$K$번 변환한 그래프의 정점의 개수를 $1 \\, 000 \\, 000 \\, 007(= 10^9 + 7)$로 나눈 나머지를 출력한다. 이 수는 소수이다.