Counting Hamiltonian Cycles in a k-Nearest Graph with Deleted Vertices

Given a simple undirected graph ( G=(V,E) ) with ( |V|=n ). A subset ( S\subset V ) is given, and the vertices in ( S ) are considered deleted. For a given positive integer ( k ), an edge ( (u,v) ) exists in ( E ) if and only if ( u,v\in V\setminus S ) and ( 0<|u-v|\le k ).

A cycle in ( G ) is defined as a sequence ( a_0,a_1,\ldots,a_{m-1} ) (with ( m=|V\setminus S| )) such that for every ( 0\le i<m ) we have ( (a_i,a_{(i+1)\bmod m})\in E ) and the sequence contains every vertex in ( V\setminus S ) exactly once.

Two cycles ( a ) and ( a' ) are considered essentially identical if there exists a nonnegative integer ( k ) such that ( a_i = a'_{(i+k)\bmod m} ) for all ( 0\le i<m ); in other words, they are cyclic shifts of each other.

Compute the number of essentially different cycles in ( G ) modulo ( 10^9+7 ).

inputFormat

The first line contains three integers ( n ), ( k ), and ( d ) (where ( d=|S| )). If ( d>0 ), the second line contains ( d ) distinct integers representing the elements of ( S ).

outputFormat

Output a single integer representing the number of essentially different Hamiltonian cycles modulo ( 10^9+7 ).

sample

3 2 1
2

1