# Ways to select one or more pairs from two different sets

Given two positive numbers ‘n’ and ‘m’ (n <= m) which represent total number of items of first and second type of sets respectively. Find total number of ways to select at-least one pair by picking one item from first type(I) and another item from second type(II). In any arrangement, an item should not be common between any two pairs.**Note:** Since answer can be large, output it in modulo **1000000007**.

Input: 2 2Output: 6ExplanationLet's denote the items of I type as a, b and II type as c, d i.e, Type I - a, b Type II - c, d Ways to arrange one pair at a time 1. a --- c 2. a --- d 3. b --- c 4. b --- d Ways to arrange two pairs at a time 5. a --- c, b --- d 6. a --- d, b --- cInput: 2 3Output: 12Input: 1 2Output: 2

The approach is simple, we only need the combination of choosing ‘**i**‘ items from ‘**n**‘ type and ‘**i**‘ items from ‘**m**‘ type and multiply them(Rule of product) where ‘**i**‘ varies from **1** to ‘**n**‘. But we can also permute the resultant product in ‘i’ ways therefore we need to multiply with **i!**. After that take the sum(Rule of sum) of all resultant product to get the final answer.

## C++

`// C++ program to find total no. of ways` `// to form a pair in two different set` `#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `// initialize global variable so that` `// it can access by preCalculate() and` `// nCr() function` `int` `* fact, *inverseMod;` `const` `int` `mod = 1e9 + 7;` ` ` `/* Iterative Function to calculate (x^y)%p in O(log y) */` `int` `power(` `int` `x, ` `int` `y, ` `int` `p)` `{` ` ` `int` `res = 1; ` `// Initialize result` ` ` ` ` `x = x % p; ` `// Update x if it is more than or` ` ` `// equal to p` ` ` ` ` `while` `(y) {` ` ` ` ` `// If y is odd, multiply x with result` ` ` `if` `(y & 1)` ` ` `res = (1LL * res * x) % p;` ` ` ` ` `// y must be even now` ` ` `y = y >> 1; ` `// y = y/2` ` ` `x = (1LL * x * x) % p;` ` ` `} ` `// trace(res);` ` ` ` ` `return` `res;` `}` ` ` `// Pre-calculate factorial and` `// Inverse of number` `void` `preCalculate(` `int` `n)` `{` ` ` `fact[0] = inverseMod[0] = 1;` ` ` `for` `(` `int` `i = 1; i <= n; ++i) {` ` ` ` ` `fact[i] = (1LL * fact[i - 1] * i) % mod;` ` ` `inverseMod[i] = power(fact[i], mod - 2, mod);` ` ` `}` `}` ` ` `// utility function to calculate nCr` `int` `nPr(` `int` `a, ` `int` `b)` `{` ` ` `return` `(1LL * fact[a] * inverseMod[a - b]) % mod;` `}` ` ` `int` `countWays(` `int` `n, ` `int` `m)` `{` ` ` `fact = ` `new` `int` `[m + 1];` ` ` `inverseMod = ` `new` `int` `[m + 1];` ` ` ` ` `// Pre-calculate factorial and` ` ` `// inverse of number` ` ` `preCalculate(m);` ` ` ` ` `// Initialize answer` ` ` `int` `ans = 0;` ` ` `for` `(` `int` `i = 1; i <= n; ++i) {` ` ` ` ` `ans += (1LL * ((1LL * nPr(n, i) ` ` ` `* nPr(m, i)) % mod)` ` ` `* inverseMod[i]) % mod;` ` ` `if` `(ans >= mod)` ` ` `ans %= mod;` ` ` `}` ` ` ` ` `return` `ans;` `}` ` ` `// Driver program` `int` `main()` `{` ` ` `int` `n = 2, m = 2;` ` ` ` ` `cout << countWays(n, m);` ` ` ` ` `return` `0;` `}` |

## Java

`// Java program to find total` `// no. of ways to form a pair` `// in two different set` ` ` `public` `class` `Test` `{` ` ` `static` `long` `[] fact;` ` ` `static` `long` `[] inverseMod;` ` ` `static` `int` `mod=` `1000000007` `;` ` ` ` ` `/* Iterative Function to calculate ` ` ` `(x^y)%p in O(log y) */` ` ` ` ` `static` `long` `power(` `long` `x, ` `int` `y, ` `int` `p)` ` ` `{` ` ` `// Initialize result` ` ` `long` `res = ` `1` `; ` ` ` ` ` `// Update x if it is more than or` ` ` `// equal to p` ` ` `x = x % p; ` ` ` ` ` `while` `(y!=` `0` `)` ` ` `{` ` ` ` ` `// If y is odd, multiply ` ` ` `// x with result` ` ` `if` `((y & ` `1` `)!=` `0` `)` ` ` `res = (` `1` `* res * x) % p;` ` ` `}` ` ` `// y must be even now` ` ` `y = y >> ` `1` `; ` ` ` ` ` `x = (` `1` `* x * x) % p;` ` ` `} ` ` ` ` ` ` ` `return` `res;` ` ` `}` ` ` ` ` `// Pre-calculate factorial and` ` ` `// Inverse of number` ` ` `public` `static` `void` `preCalculate(` `int` `n)` ` ` `{` ` ` `//int fact[]=new long[n];` ` ` `// int inverseMod[]=new long[n];` ` ` `fact[` `0` `] = ` `1` `;` ` ` `inverseMod[` `0` `] = ` `1` `;` ` ` ` ` `for` `(` `int` `i = ` `1` `; i <= n; i++) ` ` ` `{` ` ` ` ` `fact[i] = (` `1` `* fact[i - ` `1` `] * i)` ` ` `% mod;` ` ` ` ` `inverseMod[i] = power(fact[i], ` ` ` `mod - ` `2` `, mod);` ` ` ` ` `}` ` ` `}` ` ` ` ` `// utility function to calculate nCr` ` ` `public` `static` `long` `nPr(` `int` `a, ` `int` `b)` ` ` `{` ` ` ` ` `return` `(` `1` `* fact[a] * inverseMod[a - b])` ` ` `% (` `long` `)mod;` ` ` `}` ` ` ` ` `public` `static` `int` `countWays(` `int` `n, ` `int` `m)` ` ` `{` ` ` ` ` `fact = ` `new` `long` `[m + ` `1` `];` ` ` `inverseMod = ` `new` `long` `[m + ` `1` `];` ` ` ` ` `// Pre-calculate factorial and` ` ` `// inverse of number` ` ` `preCalculate(m);` ` ` ` ` `// Initialize answer` ` ` `long` `ans = ` `0` `;` ` ` ` ` `for` `(` `int` `i = ` `1` `; i <= n; i++) {` ` ` ` ` `ans = ans+(` `1` `* ((` `1` `* nPr(n, i)* ` ` ` `nPr(m, i)) % mod)*` ` ` `(inverseMod[i])) % mod;` ` ` ` ` `if` `(ans >= mod)` ` ` `ans %= mod;` ` ` `}` ` ` ` ` `return` `(` `int` `)ans;` ` ` `} ` ` ` ` ` `/* Driver program */` ` ` `public` `static` `void` `main(String[] args) ` ` ` `{` ` ` `int` `n = ` `2` `, m = ` `2` `;` ` ` ` ` `System.out.println(countWays(n, m));` ` ` `}` `}` ` ` `// This code is contributed by Gitanjali` |

**Output:**

6

**Time complexity: **O(m*log(mod))**Auxiliary space: **O(m)

This article is contributed by Shubham Bansal. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.