<p>There are <code>n</code> people and <code>40</code> types of hats labeled from <code>1</code> to <code>40</code>.</p>

<p>Given a 2D integer array <code>hats</code>, where <code>hats[i]</code> is a list of all hats preferred by the <code>i<sup>th</sup></code> person.</p>

<p>Return <em>the number of ways that the <code>n</code> people wear different hats to each other</em>.</p>

<p>Since the answer may be too large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> hats = [[3,4],[4,5],[5]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> hats = [[3,5,1],[3,5]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 ways to choose hats:
(3,5), (5,3), (1,3) and (1,5)
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
<strong>Output:</strong> 24
<strong>Explanation:</strong> Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == hats.length</code></li>
	<li><code>1 &lt;= n &lt;= 10</code></li>
	<li><code>1 &lt;= hats[i].length &lt;= 40</code></li>
	<li><code>1 &lt;= hats[i][j] &lt;= 40</code></li>
	<li><code>hats[i]</code> contains a list of <strong>unique</strong> integers.</li>
</ul>

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long int
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vt vector<ll>v;
#define cYes cout<<"YES"<<'\n';
#define cNo cout<<"NO"<<'\n';
#define INPUT int t;cin>>t;while(t--)
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define F first
#define S second
#define forx3(x, start, stop, step) for (long long x = start; x < (long long)(stop); x += step)
#define forx(x, start, stop) forx3(x, start, stop, 1) 
#define forx2(x, stop) forx(x, 0, stop)
#define forr(x,start,stop)  for (long long x = start; x >= (long long)(stop); x -= 1)
#define all(a) a.begin(), a.end()
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {
    cout << '\n';
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << ' ';
    err(++it, args...);
}
static constexpr ll MOD = 1e9+7;

ll modPow(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        exp >>= 1;
        base = (base * base) % mod;
    }
    return res;
}

class Solution {
public:
    int numberWays(vector<vector<int>>& hats) {
        int sz = hats.size();
        int mx = 0;
        
        forx(i, 0, sz) {
            for(auto i: hats[i]) {
                mx = max(mx, i);
            }
        }
        vector<unordered_set<int>> v(mx + 2);
        forx(i, 0, sz) {
            for(auto j: hats[i]) {
                v[j].insert(i);
            }
        }

        int dp[mx + 1][1 << 11];
        memset(dp, -1, sizeof(dp));
        function<int(int,int)> dfs = [&](int hat, int mask) {
            if (mask == (1 << sz) - 1) return 1; // All people are assigned hats
            if (hat > mx) return 0; // No more hats available to try
            if (dp[hat][mask] != -1) return dp[hat][mask];
            
            int res = dfs(hat + 1, mask); // Skip the current hat
            for (int ppl : v[hat]) {
                //error(ppl);
                if (((1 << ppl) & mask) == 0) {
                    res = (res + dfs(hat + 1, mask | (1 << ppl))) % MOD;
                }
            }
            return dp[hat][mask] = res;
        };

        return dfs(1, 0);
    }
};
11800