In this **HackerEarth Manhattan distance problem solution,** Ben had two numbers M and N. He factorized both the numbers, that is, expressed M and N as a product of prime numbers.

M = (P1A1)*(P2A2 )*(P3A3)*… *(PNAN)

N = (Q1B1)*(Q2B2 )*(Q3B3)*… *(QNBN)

Here, * represents multiplication.

P1, P2 ...PN are distinct prime numbers.

Q1, Q2 ...QN are distinct prime numbers.

Unfortunately, Ben has lost both the numbers M and N but still he has arrays A and B. He wants to reterive the numbers M and N but he will not be able to. Your task is to determine the minimum and the maximum number of factors their product (that is, M * N) could have. Your task is to tell Ben the minimum and the maximum number of factors that the product of M and N could have.

Since the answer can be large, print modulo 1000000007.

## HackerEarth Factors problem solution.

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define m 1000000007
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
int main() {
FIO;
test
{
ll n,i,ans1=1,ans2=1;
cin>>n;
ll a[n],b[n];
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<n;i++){
cin>>b[i];
}
sort(a,a+n);
sort(b,b+n,greater<ll>());
for(i=0;i<n;i++){
ans1*=(a[i]+b[i]+1);
ans1%=m;
ans2*=(a[i]+1);
ans2%=m;
ans2*=(b[i]+1);
ans2%=m;
}
cout<<ans1<<" "<<ans2<<endl;
}
return 0;
}

### Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 14, M = 1e9 + 7;
int n;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
cin >> n;
int a[n], b[n];
int mx = 1;
for (int i = 0; i < n; ++i) {
cin >> a[i];
mx = (ll) mx * (a[i] + 1) % M;
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
mx = (ll) mx * (b[i] + 1) % M;
}
sort(a, a + n);
sort(b, b + n, greater<int>());
int mn = 1;
for (int i = 0; i < n; ++i)
mn = (ll) mn * (a[i] + b[i] + 1) % M;
cout << mn << ' ' << mx << '\n';
}
}