#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cstdint>
#ifdef _MSC_VER
#include <intrin.h>
#pragma intrinsic(__popcnt, _BitScanForward)
#endif
#include <omp.h>

constexpr int MAXN = 12;
int n;

inline int popcount32(unsigned x)
{
#ifdef _MSC_VER
    return (int)__popcnt(x);
#else
    return __builtin_popcount(x);
#endif
}
inline int ctz32(unsigned x)
{
#ifdef _MSC_VER
    unsigned long idx;
    _BitScanForward(&idx, x);
    return (int)idx;
#else
    return __builtin_ctz(x);
#endif
}

static std::vector<uint32_t> combos;
static std::vector<std::vector<std::vector<uint32_t>>> transitions;
thread_local std::vector<uint64_t> dpLocal;

inline uint64_t countMatchings(const int rowChoice[])
{
    const int full = 1 << n;
    dpLocal[0] = 1;
    for (int m = 1; m < full; ++m) dpLocal[m] = 0;

    for (int mask = 0; mask < full - 1; ++mask)
    {
        uint64_t ways = dpLocal[mask];
        if (!ways) continue;

        int r = popcount32((unsigned)mask);
        const auto& nexts = transitions[rowChoice[r]][mask];
        for (uint32_t nm : nexts) dpLocal[nm] += ways;
    }
    return dpLocal[full - 1];
}

void backtrack_row(
    int r,
    int min_ci,
    int rowChoice[],
    std::unordered_map<uint64_t, uint64_t>& hist,
    const std::vector<uint64_t>& fact)
{
    if (r == n)
    {
        uint64_t denom = 1;
        int run = 1;
        for (int i = 1; i < n; ++i)
        {
            if (rowChoice[i] == rowChoice[i - 1]) ++run;
            else { denom *= fact[run]; run = 1; }
        }
        denom *= fact[run];
        uint64_t weight = fact[n] / denom;

        uint64_t cnt = countMatchings(rowChoice);
        hist[cnt] += weight;
        return;
    }

    for (int ci = min_ci; ci < (int)combos.size(); ++ci)
    {
        rowChoice[r] = ci;
        backtrack_row(r + 1, ci, rowChoice, hist, fact);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    n = 9;

    combos.reserve(n * (n - 1) * (n - 2) / 6);
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            for (int k = j + 1; k < n; ++k)
                combos.push_back((1u << i) | (1u << j) | (1u << k));

    const int full = 1 << n;

    transitions.assign(combos.size(), std::vector<std::vector<uint32_t>>(full));
    for (size_t ci = 0; ci < combos.size(); ++ci)
    {
        uint32_t rmask = combos[ci];
        for (int mask = 0; mask < full; ++mask)
        {
            uint32_t avail = rmask & ~uint32_t(mask);
            while (avail)
            {
                uint32_t bit = avail & ~(avail - 1);
                avail ^= bit;
                transitions[ci][mask].push_back(mask | bit);
            }
        }
    }

    std::vector<uint64_t> fact(n + 1, 1);
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;

    omp_set_dynamic(0);
    omp_set_num_threads(omp_get_num_procs());

    std::unordered_map<uint64_t, uint64_t> globalHist;
    globalHist.reserve(1024);

#pragma omp parallel
    {
        dpLocal.resize(full);

        std::unordered_map<uint64_t, uint64_t> localHist;
        localHist.reserve(1024);
        int rowChoice[MAXN];

#pragma omp for schedule(dynamic,1)
        for (int ci0 = 0; ci0 < (int)combos.size(); ++ci0)
        {
            rowChoice[0] = ci0;
            backtrack_row(1, ci0, rowChoice, localHist, fact);
        }

#pragma omp critical
        for (auto& p : localHist) globalHist[p.first] += p.second;
    }

    std::vector<std::pair<uint64_t, uint64_t>> out(globalHist.begin(), globalHist.end());
    std::sort(out.begin(), out.end(), [](auto& a, auto& b) { return a.first < b.first; });

    std::cout << "Perfect-matchings\tFrequency\n";
    std::cout << "a(" << n << ")\n";
    for (auto& pr : out) std::cout << pr.first << '\t' << pr.second << '\n';

    return 0;
}