Graph Transformation

The transformation $(f:G \mapsto G')$ of a graph is defined as follows. Treat each edge of $G$ as a vertex of $G'$. Connect two vertices of $G'$ with an edge when the corresponding edges are adjacent in $G$. Two distinct edges are adjacent if they share at least one common vertex.

The transformed graph can be transformed again.

Find the number of vertices of the graph obtained by transforming an $N$-complete graph $K$ times. An $N$-complete graph is a graph with $N$ vertices in which every pair of distinct vertices is joined by an edge.

The first line contains integers $N$ and $K$, separated by a space. ($3 \leq N \leq 100\,000$, $0 \leq K \leq 100\,000$)

Print the remainder when the number of vertices of the graph after $K$ transformations is divided by $1\,000\,000\,007 (=10^9 + 7)$. This number is prime.