Sereja and Salesman

Sereja has an undirected graph on N vertices. There are edges between all but M pairs of vertices. A permutation p on the vertices of the graph is represented as p[1], p[2], … , p[N] such that for all i, p[i] is a vertex of the graph. A permutation is called connected if there is an edge between vertices p[i] and p[i+1] for all natural numbers i less than N. Sereja wants to know the number of con