#include <bits/stdc++.h>

#define input "colorare3.in"
#define output "colorare3.out"
#define MOD 1000000007
#define NMAX 100005

using namespace std;
typedef long long ll;

ifstream in(input);
ofstream out(output);

vector < int > muchii[NMAX];
queue < int > coada;

ll K;
bool uz[NMAX];
int N;

void Solve()
{
    ll R = 1;
    coada.push(1);
    uz[1] = 1;
    while(!coada.empty())
    {
        int nod = coada.front(); coada.pop();
        ll T = 0;
        for(unsigned i = 0; i < muchii[nod].size(); i++)
        {
            int new_nod = muchii[nod][i];
            if(!uz[new_nod])
            {
                T++; uz[new_nod] = 1; coada.push(new_nod);
            }
        }
        //out << "Suntem in nodul " << nod << " si avem " << T << "\n";
        ll P = 1;
        if(nod == 1)
        {
            for(ll i = K - T + 1; i <= K; i++)
                P = (P * i) % MOD;
        }
        else
        {
            for(ll i = K - T; i < K; i++)
                P = (P * i) % MOD;
        }
        R = (R * P) % MOD;
    }
    if(R < 0) R += MOD;
    out << R << "\n";
}

int main()
{
    Read_Data();
    Solve();
    return 0;
}