# Little Elephant and T-Shirts | CodeChef Solution

Hello coders, today we are going to solve Little Elephant and T-Shirts CodeChef Solution whose Problem Code is TSHIRTS.

Little Elephant and his friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts of the same ID.

They want to know how many arrangements are there in which no two persons wear same T-Shirt. One arrangement is considered different from another arrangement if there is at least one person wearing a different kind of T-Shirt in another arrangement.

## Input Format

First line of the input contains a single integer denoting number of test cases. Then T test cases follow.

For each test case, first line contains an integerÂ N, denoting the total number of persons. Each of the nextÂ NÂ lines contains at leastÂ 1Â and at mostÂ 100Â space separated distinct integers, denoting the ID’s of the T-ShirtsÂ ithÂ person has.

## Output Format

For each test case, print in single line the required number of ways moduloÂ 1000000007 = 109+7.

## Constraints

• 1 â‰¤ T â‰¤ 10
• 1 â‰¤ N â‰¤ 10

Example

Sample Input

``````2
2
3 5
8 100
3
5 100 1
2
5 100``````

Sample Output

``````4
4``````

Explanation

For the first case,Â 4Â possible ways areÂ (3,8),Â (3,100),Â (5,8)Â andÂ (5,100).
For the second case,Â 4Â possible ways areÂ (5,2,100),Â (100,2,5),Â (1,2,100), andÂ (1,2,5).

## Solution – Little Elephant and T-Shirts

### C++

```#include <bits/stdc++.h>
#define GREEN "\033[32m"
#define MAGENTA "\033[35m"
#define RESET "\033[0m"
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
#ifdef BCDBG
#define tcT template<typename T
tcT,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p) {return os<<"("<<p.first<<", "<<p.second<<")";}
tcT,typename U=typename enable_if<!is_same<T,string>::value,typename T::value_type>::type> ostream& operator<<(ostream &os,const T &v)
{os<<"\n{";string sep;for(const U &x:v)os<<sep<<x,sep=", ";return os<<'}';}
void debug_help() {cout<<RESET<<endl;}
tcT,typename... U> void debug_help(T t,U... u) {cout<<t;if(sizeof...(u))cout<<", ";debug_help(u...);}
int debug_dms[10],debug_md;
void debug_fill() {}
tcT,typename... U> void debug_fill(T t,U... u) {debug_dms[debug_md++]=t;debug_fill(u...);}
tcT> void debug_arr(T x,int d) {cout<<x;}
tcT> void debug_arr(T* arr,int d)
{cout<<"\n{";string sep;for(int i=0;i<debug_dms[d];i++)cout<<sep,sep=", ",debug_arr(arr[i],d+1);cout<<'}';if(d==0)cout<<RESET<<endl;}
#define dbg(...) cout<<MAGENTA<<__LINE__<<" ["<<#__VA_ARGS__<<"]: "<<GREEN,debug_help(__VA_ARGS__)
#define dba(arr,...) cout<<MAGENTA<<__LINE__<<" ["<<#arr<<"]: "<<GREEN,debug_md=0,debug_fill(__VA_ARGS__),debug_arr(arr,0)
#else
#define dbg(...)
#define dba(arr,...)
#endif
typedef long long ll;
typedef unsigned long long ull;
const char df = '\n';

vector<string> split(const string& s) {
int a = 0, b = 0, n = s.size();
vector<string> r;
while (b < n) {
while (b < n && !isspace(s[b])) b++;
r.push_back(s.substr(a, b - a));
while (b < n && isspace(s[b])) b++;
a = b;
}
return r;
}

const int mod = 1e9+7;

int add(int a, int b) {
int c = (a + b) % mod;
if (c < 0) c += mod;
return c;
}

int n;
string line;
int has[10][101];
int dp[101][1 << 10];

void solve() {
memset(has, 0, sizeof(has));
getline(cin, line);
n = stoi(line);
for (int i = 0; i < n; i++) {
getline(cin, line);
auto r = split(line);
for (auto& x:r) {
has[i][stoi(x)] = 1;
}
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i < 101; i++) {
for (int mk = 0; mk < (1 << n); mk++) {
dp[i][mk] = add(dp[i - 1][mk], dp[i][mk]);
for (int j = 0; j < n; j++) {
if ((mk >> j & 1) == 0 && has[j][i]) {
dp[i][mk | 1 << j] = add(dp[i][mk | 1 << j], dp[i - 1][mk]);
}
}
}
}
int total = 0;
for (int mk = 0; mk < (1 << n); mk++) {
if (__builtin_popcount(mk) == n) {
}
}
cout << total << df;
}

signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
getline(cin, line);
int tt = stoi(line);
for (int i = 1; i <= tt; i++) {
solve();
}
return 0;
}```

### Python

```mod = 1e9+7
import numpy as np

t = int(input())
for _ in range(t):
n = int(input())
ingr = [0]*101
for i in range(n):
for shirt in map(int, input().split(' ')):
ingr[shirt] |= (1<<i)

dp = [[0 for _ in range((1<<n) + 1)] for _ in range(101)]

dp[0][0] = 1
for i in range(1, 101):
if (bit & ingr[i]):

print(int(dp[100][(1<<n)-1]))
```

### Java

```import java.util.*;
import java.io.*;
import java.math.*;

public class Main

{
static long dp[][];
static int mod=1000000007;
static int max;
public static void main(String[] args)
{
PrintWriter out=new PrintWriter(System.out);
//StringBuffer sb=new StringBuffer("");
int ttt=1;
ttt =i();

outer :while (ttt-- > 0)
{
int n=i();
ArrayList<Integer> AA[]=new ArrayList[101];
for(int i=0;i<101;i++)
AA[i]=new ArrayList<Integer>();
for(int i=0;i<n;i++) {
String s=sc.nextLine().trim();
String B[]=s.split(" ");
for(String ss : B) {
int y=Integer.parseInt(ss);
}
}
int A[][]=new int[101][];
for(int i=1;i<101;i++) {
A[i]=new int[AA[i].size()];
for(int j=0;j<AA[i].size();j++) {
A[i][j]=AA[i].get(j);
//System.out.println(A[i][j]+" "+i+" "+j);
}
}
dp=new long[101][1<<n];
for(int i=0;i<101;i++) {
Arrays.fill(dp[i],-1);
}
System.out.println(go(A, 1, (1<<n)-1, n));

}

//System.out.println(sb.toString());
out.close();

//CHECK FOR N=1                    //CHECK FOR M=0
//CHECK FOR N=1                    //CHECK FOR M=0
//CHECK FOR N=1
//CHECK FOR N=1
//CHECK FOR N=1

}
static long go(int A[][],int i,int mask,int n) {
return 1;
if(i==A.length)
return 0;
ans%=mod;
for(int j : A[i]) {
ans%=mod;
}
}

}

static class Pair implements Comparable<Pair>
{
long x;
long y;
Pair(long x,long y){
this.x=x;
this.y=y;

}
@Override
public int compareTo(Pair o) {
if(this.x>o.x)
return 1;
else if(this.x<o.x)
return -1;
else {
if(this.y>o.y)
return 1;
else if(this.y<o.y)
return -1;
else
return 0;
}
}

/* FOR TREE MAP PAIR USE */

//		public int compareTo(Pair o) {
// 			if (x > o.x) {
// 				return 1;
// 			}
// 			if (x < o.x) {
// 				return -1;
// 			}
// 			if (y > o.y) {
// 				return 1;
// 			}
// 			if (y < o.y) {
// 				return -1;
// 			}
// 			return 0;
// 		}

}

static int[] input(int n) {
int A[]=new int[n];
for(int i=0;i<n;i++) {
A[i]=sc.nextInt();
}
return A;
}
static long[] inputL(int n) {
long A[]=new long[n];
for(int i=0;i<n;i++) {
A[i]=sc.nextLong();
}
return A;
}
static String[] inputS(int n) {
String A[]=new String[n];
for(int i=0;i<n;i++) {
A[i]=sc.next();
}
return A;
}
static long sum(int A[]) {
long sum=0;
for(int i : A) {
sum+=i;
}
return sum;
}
static long sum(long A[]) {
long sum=0;
for(long i : A) {
sum+=i;
}
return sum;
}
static void reverse(long A[]) {
int n=A.length;
long B[]=new long[n];
for(int i=0;i<n;i++) {
B[i]=A[n-i-1];
}
for(int i=0;i<n;i++)
A[i]=B[i];

}
static void reverse(int A[]) {
int n=A.length;
int B[]=new int[n];
for(int i=0;i<n;i++) {
B[i]=A[n-i-1];
}
for(int i=0;i<n;i++)
A[i]=B[i];

}
static void input(int A[],int B[]) {
for(int i=0;i<A.length;i++) {
A[i]=sc.nextInt();
B[i]=sc.nextInt();
}
}
static int[][] input(int n,int m){
int A[][]=new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
A[i][j]=i();
}
}
return A;
}
static char[][] charinput(int n,int m){
char A[][]=new char[n][m];
for(int i=0;i<n;i++) {
String s=s();
for(int j=0;j<m;j++) {
A[i][j]=s.charAt(j);
}
}
return A;
}
static int find(int A[],int a) {
if(A[a]==a)
return a;
return A[a]=find(A, A[a]);
}
static int max(int A[]) {
int max=Integer.MIN_VALUE;
for(int i=0;i<A.length;i++) {
max=Math.max(max, A[i]);
}
return max;
}
static int min(int A[]) {
int min=Integer.MAX_VALUE;
for(int i=0;i<A.length;i++) {
min=Math.min(min, A[i]);
}
return min;
}
static long max(long A[]) {
long max=Long.MIN_VALUE;
for(int i=0;i<A.length;i++) {
max=Math.max(max, A[i]);
}
return max;
}
static long min(long A[]) {
long min=Long.MAX_VALUE;
for(int i=0;i<A.length;i++) {
min=Math.min(min, A[i]);
}
return min;
}
static long [] prefix(long A[]) {
long p[]=new long[A.length];
p[0]=A[0];
for(int i=1;i<A.length;i++)
p[i]=p[i-1]+A[i];
return p;
}
static long [] prefix(int A[]) {
long p[]=new long[A.length];
p[0]=A[0];
for(int i=1;i<A.length;i++)
p[i]=p[i-1]+A[i];
return p;
}
static long [] suffix(long A[]) {
long p[]=new long[A.length];
p[A.length-1]=A[A.length-1];
for(int i=A.length-2;i>=0;i--)
p[i]=p[i+1]+A[i];
return p;
}
static long [] suffix(int A[]) {
long p[]=new long[A.length];
p[A.length-1]=A[A.length-1];
for(int i=A.length-2;i>=0;i--)
p[i]=p[i+1]+A[i];
return p;
}
static int min(int a,int b) {
return Math.min(a, b);
}
static int min(int a,int b,int c) {
return Math.min(a, Math.min(b, c));
}
static int min(int a,int b,int c,int d) {
return Math.min(a, Math.min(b, Math.min(c, d)));
}
static int max(int a,int b) {
return Math.max(a, b);
}
static int max(int a,int b,int c) {
return Math.max(a, Math.max(b, c));
}
static int max(int a,int b,int c,int d) {
return Math.max(a, Math.max(b, Math.max(c, d)));
}
static long min(long a,long b) {
return Math.min(a, b);
}
static long min(long a,long b,long c) {
return Math.min(a, Math.min(b, c));
}
static long min(long a,long b,long c,long d) {
return Math.min(a, Math.min(b, Math.min(c, d)));
}
static long max(long a,long b) {
return Math.max(a, b);
}
static long max(long a,long b,long c) {
return Math.max(a, Math.max(b, c));
}
static long max(long a,long b,long c,long d) {
return Math.max(a, Math.max(b, Math.max(c, d)));
}

static long power(long x, long y, long p)
{

if(y==0)
return 1;
if(x==0)
return 0;
long res = 1;
x = x % p;

while (y > 0) {

if (y % 2 == 1)
res = (res * x) % p;

y = y >> 1;
x = (x * x) % p;
}

return res;
}
static void print(int A[]) {
for(int i : A) {
System.out.print(i+" ");
}
System.out.println();
}
static void print(long A[]) {
for(long i : A) {
System.out.print(i+" ");
}
System.out.println();
}
static long mod(long x) {
return ((x%mod + mod)%mod);
}
static String reverse(String s) {
StringBuffer p=new StringBuffer(s);
p.reverse();
return p.toString();
}

static int i() {
return sc.nextInt();
}
static String s() {
return sc.next();
}
static long l() {
return sc.nextLong();
}
static void sort(int[] A){
int n = A.length;
Random rnd = new Random();
for(int i=0; i<n; ++i){
int tmp = A[i];
int randomPos = i + rnd.nextInt(n-i);
A[i] = A[randomPos];
A[randomPos] = tmp;
}
Arrays.sort(A);
}
static void sort(long[] A){
int n = A.length;
Random rnd = new Random();
for(int i=0; i<n; ++i){
long tmp = A[i];
int randomPos = i + rnd.nextInt(n-i);
A[i] = A[randomPos];
A[randomPos] = tmp;
}
Arrays.sort(A);
}
static String sort(String s) {
Character ch[]=new Character[s.length()];
for(int i=0;i<s.length();i++) {
ch[i]=s.charAt(i);
}
Arrays.sort(ch);
StringBuffer st=new StringBuffer("");
for(int i=0;i<s.length();i++) {
st.append(ch[i]);
}
return st.toString();
}
static HashMap<Integer,Integer> hash(int A[]){
HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
for(int i : A) {
if(map.containsKey(i)) {
map.put(i, map.get(i)+1);
}
else {
map.put(i, 1);
}
}
return map;
}
static TreeMap<Integer,Integer> tree(int A[]){
TreeMap<Integer,Integer> map=new TreeMap<Integer, Integer>();
for(int i : A) {
if(map.containsKey(i)) {
map.put(i, map.get(i)+1);
}
else {
map.put(i, 1);
}
}
return map;
}
static boolean prime(int n)
{
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
double sq=Math.sqrt(n);

for (int i = 5; i <= sq; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
static boolean prime(long n)
{
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
double sq=Math.sqrt(n);

for (int i = 5; i <= sq; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
static long gcd(long a, long b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}

{
StringTokenizer st;

{
}

String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
}
catch (IOException  e)
{
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt()
{
return Integer.parseInt(next());
}

long nextLong()
{
return Long.parseLong(next());
}

double nextDouble()
{
return Double.parseDouble(next());
}

String nextLine()
{
String str = "";
try
{