그래프 변환

그래프의 변환 $(f:G \mapsto 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)$로 나눈 나머지를 출력한다. 이 수는 소수이다.