### PROBLEM LINKS

### DIFFICULTY

HARD

### EXPLANATION

Inclusion Exclusion can be used to solve the problem. Let F(i,j) denote the number of ways in which atleast a given set of i people who do not purchase anything and

atleast a given set of j items which are not purchased by anyone.

F(i,j) = ncr[(n - i) * (m - j)][r] ;

There are ncr[n]* ways to choose i people from n people, and ncr[m][j] ways to choose j items from m items. Let

G(i,j) = ncr[n]* * ncr[m][j] * F(i,j)

The final answer is given by summing G(i,j) over all (i,j). We add G(i,j) to the answer if (i + j) is even, else we subtract it.