public class InducedSubgraphs{

    long    MOD = 1000000009l;
    int     INF = (1<<29);
    int     V;       //number of vertices
    long    C[][];   // C[n][k] = Binomial
    long    fact[];  // fact[n] = n! (factorial)

    boolean adj[][];  //adjacency matrix


    int     cnt[][];    //cnt[p][x] total size of the subgraph with x as root
                        // and p is the parent of node x.
    long    perm[][];   //perm[p][x] is the number of ways to assign labels
                        //to the children of x when p is its parent.


    long    dp[][][][]; //dp[p][x][s][t]:
                        // The number of ways to assign s small labels
                        // and t big labels to the subtree rooted at x, when
                        // p is the parent of x.


    // The number of ways to assign labels to the subgraph that has x as root
    // (when p is the parent).
    //
    public void dfs_easy(int p, int x){
        int i;

        if (cnt[p][x] != 0) {
            return;
        }

        perm[p][x] = 1;

        int sum = 0; //number of children in the subtree
        for(i=0; i<V; i++) if(adj[x][i] && p != i) {
            dfs_easy(x, i);
            long s = C[ sum + cnt[x][i] ][sum];
            long t = perm[x][i];
            perm[p][x] = perm[p][x] * s % MOD * t % MOD;
            sum += cnt[x][i];
        }
        cnt[p][x] = sum + 1;
    }

    public int solve_easy(int K) {
        // For 2K <= V:
        int i,j,k;
        int dist[][] = new int[V][V];
        // Floyd-Warshall algorithm to quickly find the distances between
        // each pair of nodes.
        for(i=0; i<V; i++) for(j=0; j<V; j++) {
            if (i!=j) {
                dist[i][j] = (adj[i][j] ? 1 : INF);
            }
        }
        for(k=0; k<V; k++) {
            for(i=0; i<V; i++) for(j=0; j<V; j++) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }

        int d = V - 2*K + 1;
        // In this case, there has to be a chain of nodes of size d+1 in the middle section
        // each end of this end is connected with the small and big sections.
        int u, v, u2, v2;
        long ans = 0;

        for(u=0;u<V;u++) for(v=0;v<V;v++) if (u!=v) {
            if(dist[u][v] == d) {
                u2 = v2 = 0;
                // Seek u2 and v2, the appropriate parents for the
                // subtrees at u and v, respectively
                while ( ! adj[u][u2] || dist[u2][v] >= dist[u][v] ) {
                    u2++;
                }
                while ( ! adj[v][v2] || dist[u][v2] >= dist[u][v] ) {
                    v2++;
                }
                // Do the subtrees at u and v have the exact required sizes?
                if (cnt[u2][u] == K && cnt[v2][v] == K) {
                    ans = (ans + perm[u2][u] * perm[v2][v]) % MOD;
                }
            }
        }

        return (int)ans;
    }

    public long[][] merge( long[][] a, long[][] b ){
        int i,j,k,l;
        int A = a.length - 1, B = b.length - 1;

        // a[x][y] : The current number of ways to have
        //           x "small" children and y "big" children in total.
        // b[x][y] : The number of ways to have
        //           x "small" children and y "big" children in total.
        //           in the node that we need to combine with the result in a[][]

        // c[x][y] : The result after combining.
        long c[][] = new long[A+B+1][A+B+1];

        for(i=0;i<=A;i++) for(j=0;j<=A;j++) for(k=0;k<=B;k++) for(l=0;l<=B;l++) {
            long p = a[i][j] * b[k][l];
            long q = C[i+k][k];
            long r = C[j+l][l];
            long tmp = p % MOD * q % MOD * r % MOD;
            c[i+k][j+l] = (c[i+k][j+l] + tmp) % MOD;
        }

        return c;
    }

    public void dfs(int p, int x){
        int i;

        if (dp[p][x].length == 0) {

            long a[][] = new long[2][2];
            a[0][0] = 1;

            for(i=0;i<V;i++) if(adj[x][i] && p != i) {
                dfs(x, i);
                a = merge(a, dp[x][i]);
            }

            // If we decide the current node to be small, the whole
            // subtree must be small:
            a[cnt[p][x]][0] = perm[p][x]; //There are perm[p][x] ways to label
            // If we decide the current node to be big, the whole
            // subtree must be big:
            a[0][cnt[p][x]] = perm[p][x];

            dp[p][x] = a;
        }
    }

    public int solve(int K){
        int i,j;

        dp = new long[V+1][V+1][0][0];
        for(i=0;i<V;i++) dfs(V, i);

        long ans = 0;
        int center = 2*K - V;
        for (i=0; i<V; i++) {
            // number of ways in which node i is a center node:
            ans = (ans + dp[V][i][V-K][V-K]) % MOD;
        }
        // - Each result is repeated {center} times.
        // - we also need to choose labels for the center nodes.
        // -> Multiply by center! / center = (center-1)!

        ans = ans * fact[center - 1] % MOD;
        return (int)ans;
    }

    public int getCount(int[] edge1, int[] edge2, int K){
        int i,j;

        V = edge1.length + 1;

        // Calculate the factorial
        fact = new long[V + 1];
        fact[0] = 1;
        for( i=1; i<=V; i++) {
            fact[i] = i * fact[i-1] % MOD;
        }
        if (K == 1) { // a simple corner case, any permutation of labels will work
            return (int)fact[V];
        }
        adj = new boolean[V][V];
        for (i=0; i<V-1; i++) {
            adj[edge1[i]][edge2[i]] = adj[edge2[i]][edge1[i]] = true;
        }

        // Pascal's triangle
        C = new long[V+1][V+1];
        for(i=0;i<=V;i++) {
            C[i][0] = 1;
            for(j=1; j<=i; j++) {
                C[i][j] = ( C[i-1][j] + C[i-1][j-1] ) % MOD;
            }
        }
        // In both cases, we need to calculate the cnt[][] and perm[][] tables:
        cnt = new int[V+1][V+1];
        perm = new long[V+1][V+1];
        for(i=0;i<V;i++) {
            dfs_easy(V, i);
        }
        if (V >= 2*K) {
            return solve_easy(K);
        } else {
            return solve(K);
        }
    }

}