C ++ implementation of the above approach .
#include <bits/stdc++.h> NEW_LINE #define mp  make_pair NEW_LINE #define ll  long long NEW_LINE using namespace std ; const int mod = 1000000007 ; const int MAX = 100005 ;