Little White recently likes playing Tower Defence. She wants to make a map. The map is an undirected graph which has n vertices(graph may not connect).The length of each edge is 1.The shortest distance of vertice 1 to any other vertices is not equal to k.She wants to know how many graphs which satisfy all these conditions.If two vertices is disconnected, the distance between them is infinite.