Hamiltonian Flight

#include <bits/stdc++.h>

using namespace std;

int dp[1 << 21][21];
bool visited[1 << 21][21];
vector<int> adj[21];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; // 1 - n
        adj[a - 1].push_back(b - 1); // 0 - n-1
    }

    queue<pair<int, int>> q;

    dp[1][0] = 1;
    q.push({1, 0});
    visited[1][0] = true;

    while (!q.empty()) {
        int mask = q.front().first, u = q.front().second;
        q.pop();

        for (int v: adj[u]) {
            if (!(mask & (1 << v))) {
                dp[mask ^ (1 << v)][v] += dp[mask][u];
                dp[mask ^ (1 << v)][v] %= int(1e9) + 7;
                if (!visited[mask ^ (1 << v)][v]) {
                    visited[mask ^ (1 << v)][v] = true;
                    q.push({mask ^ (1 << v), v});
                }
            }
        }
    }

    cout << dp[(1 << n) - 1][n - 1] << '\n';

    return 0;
}