<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>

class Solution {
public:
int n;
int dp[41][(1 << 10) + 9];
map<int, vector<int>> arr;
int mod = 1e9+7;

int solve(int idx, int mask){
	//BaseCase : All people assigned hat
	//ie mask is 1111111111 return 1 
	//ie 1 possible arrangement found
	if(mask == (1 << n) - 1)
		return 1;

	//If exhauset all hats and mask not full
	if (idx == 40)
		return 0;

	if(dp[idx][mask] != -1)
		return dp[idx][mask];

	//option 1 not assign this hat
	int ans = solve(idx + 1, mask);

	//option 2 assighn this hat to any person which has this preffered
	int new_mask;
	for (int i = 0; i<arr[idx].size(); i++){
		int j = arr[idx][i];
	//check if the jth person is wearing a hat 
		if (mask & (1 << j)) continue;
		new_mask = mask;
		//selet this person ie set the jth bit
		new_mask |= (1 << j);
		ans += solve(idx + 1, new_mask);
		ans %= mod;
	}
	return dp[idx][mask] = ans % mod;
}
int numberWays(vector<vector<int>>& hats){
	n = hats.size();
	int idx = 0;
	
	//map each person id with their prefernce vector
	//hati -> p1, p4, p5 etc
	for (auto person : hats){
		for (auto hat : person){
		//ie hat -1 is perffered by person at index 0 (idx)
			arr[hat-1].push_back(idx);
			//keep 0 based index
		}
		idx++;
	}

	memset(dp, -1, sizeof(dp));
	return solve(0,0);
}
};
12200