// https://szkopul.edu.pl/problemset/problem/9G-lSeJl2QmOnKQprRR4ZJZv/site/?key=statement
#include <bits/stdc++.h>
using namespace std;
// #define GARY_DBG
#define GARY_LIB
// #define int long long
constexpr int sizik = 1000 * 1001;
#define ar std::array
constexpr int sizik1 = 607;
constexpr int m = 1000 * 1000;
int n;
int64_t nums[sizik1];
/**
*
* fast gcd
*
*/
int64_t fast_gcd(int64_t a, int64_t b) {
if (a == 0) return b;
if (b == 0) return a;
int64_t az = __builtin_ctz(a);
int64_t bz = __builtin_ctz(b);
int64_t shift = std::min(az, bz);
b >>= bz;
while (a != 0) {
a >>= az;
int64_t diff = b - a;
az = __builtin_ctz(diff);
b = std::min(a, b);
a = std::abs(diff);
}
return b << shift;
}
namespace nachia {
// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b) {
long long x = 1, y = 0;
while (b) {
long long u = a / b;
std::swap(a -= b * u, b);
std::swap(x -= y * u, y);
}
return std::make_pair(x, a);
}
} // namespace nachia
namespace nachia {
template<unsigned int MOD>
struct StaticModint {
private:
using u64 = unsigned long long;
unsigned int x;
public:
using my_type = StaticModint;
template<class Elem>
static Elem safe_mod(Elem x) {
if (x < 0) {
if (0 <= x + MOD) return x + MOD;
return MOD - ((-(x + MOD) - 1) % MOD + 1);
}
return x % MOD;
}
StaticModint() : x(0) {}
StaticModint(const my_type& a) : x(a.x) {}
StaticModint& operator=(const my_type&) = default;
template<class Elem>
StaticModint(Elem v) : x(safe_mod(v)) {}
unsigned int operator*() const noexcept { return x; }
my_type& operator+=(const my_type& r) noexcept {
auto t = x + r.x;
if (t >= MOD) t -= MOD;
x = t;
return *this;
}
my_type operator+(const my_type& r) const noexcept {
my_type res = *this;
return res += r;
}
my_type& operator-=(const my_type& r) noexcept {
auto t = x + MOD - r.x;
if (t >= MOD) t -= MOD;
x = t;
return *this;
}
my_type operator-(const my_type& r) const noexcept {
my_type res = *this;
return res -= r;
}
my_type operator-() const noexcept {
my_type res = *this;
res.x = ((res.x == 0) ? 0 : (MOD - res.x));
return res;
}
my_type& operator*=(const my_type& r) noexcept {
x = (u64)x * r.x % MOD;
return *this;
}
my_type operator*(const my_type& r) const noexcept {
my_type res = *this;
return res *= r;
}
my_type pow(unsigned long long i) const noexcept {
my_type a = *this, res = 1;
while (i) {
if (i & 1) {
res *= a;
}
a *= a;
i >>= 1;
}
return res;
}
my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
unsigned int val() const noexcept { return x; }
static constexpr unsigned int mod() { return MOD; }
static my_type raw(unsigned int val) noexcept {
auto res = my_type();
res.x = val;
return res;
}
my_type& operator/=(const my_type& r) { return operator*=(r.inv()); }
my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};
} // namespace nachia
namespace nachia {
template<unsigned int MOD>
struct PrimitiveRoot {
using u64 = unsigned long long;
static constexpr u64 powm(u64 a, u64 i) {
u64 res = 1, aa = a;
for (; i; i /= 2) {
if (i & 1) res = res * aa % MOD;
aa = aa * aa % MOD;
}
return res;
}
static constexpr bool ExamineVal(unsigned int g) {
u64 t = MOD - 1;
for (u64 d = 2; d * d <= t; d += 1 + (d & 1))
if (t % d == 0) {
if (powm(g, (MOD - 1) / d) == 1) return false;
while (t % d == 0)
t /= d;
}
if (t != 1)
if (powm(g, (MOD - 1) / t) == 1) return false;
return true;
}
static constexpr unsigned int GetVal() {
for (u64 x = 2; x < MOD; x++)
if (ExamineVal(x)) return x;
return 0;
}
static const unsigned int val = GetVal();
};
} // namespace nachia
namespace nachia {
template<class mint>
struct NttInterface {
template<class Iter>
void Butterfly(Iter, int) const {}
template<class Iter>
void IButterfly(Iter, int) const {}
template<class Iter>
void BitReversal(Iter a, int N) const {
for (int i = 0, j = 0; j < N; j++) {
if (i < j) std::swap(a[i], a[j]);
for (int k = N >> 1; k > (i ^= k); k >>= 1)
;
}
}
};
} // namespace nachia
namespace nachia {
int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
return __builtin_popcountll(c);
#else
c = (c & (~0ull / 3)) + ((c >> 1) & (~0ull / 3));
c = (c & (~0ull / 5)) + ((c >> 2) & (~0ull / 5));
c = (c & (~0ull / 17)) + ((c >> 4) & (~0ull / 17));
c = (c * (~0ull / 257)) >> 56;
return c;
#endif
}
// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return 63 - __builtin_clzll(x);
#else
using u64 = unsigned long long;
int q = (x >> 32) ? 32 : 0;
auto m = x >> q;
constexpr u64 hi = 0x88888888;
constexpr u64 mi = 0x11111111;
m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31;
q += (m & 0xf) << 2;
q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf;
return q;
#endif
}
// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return __builtin_ctzll(x);
#else
return MsbIndex(x & -x);
#endif
}
}
#include <array>
#include <iterator>
namespace nachia {
template<class mint>
struct NttFromAcl : NttInterface<mint> {
using u32 = unsigned int;
using u64 = unsigned long long;
static int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (u32)(n))
x++;
return x;
}
static constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x)))
x++;
return x;
}
struct fft_info {
static constexpr u32 g = nachia::PrimitiveRoot<mint::mod()>::val;
static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);
using RootTable = std::array<mint, rank2 + 1>;
RootTable root, iroot, rate3, irate3;
fft_info() {
root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for (int i = rank2 - 1; i >= 0; i--) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
};
template<class RandomAccessIterator>
void Butterfly(RandomAccessIterator a, int n) const {
int h = ceil_pow2(n);
static const fft_info info;
int len = 0;
if ((h - len) % 2 == 1) {
int p = 1 << (h - len - 1);
for (int i = 0; i < p; i++) {
mint l = a[i], r = a[i + p];
a[i] = l + r;
a[i + p] = l - r;
}
len++;
}
for (; len < h; len += 2) {
int p = 1 << (h - len - 2);
mint rot = 1, imag = info.root[2];
u64 mod2 = u64(mint::mod()) * mint::mod();
for (int s = 0; s < (1 << len); s++) {
if (s) rot *= info.rate3[LsbIndex(~(u32)(s - 1))];
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = (s << (h - len)) + p;
for (int i = offset - p; i < offset; i++) {
u64 a0 = u64(a[i].val());
u64 a1 = u64(a[i + p].val()) * rot.val();
u64 a2 = u64(a[i + 2 * p].val()) * rot2.val();
u64 a3 = u64(a[i + 3 * p].val()) * rot3.val();
u64 a1na3imag = u64(mint(a1 + mod2 - a3).val()) * imag.val();
u64 na2 = mod2 - a2;
a[i] = a0 + a2 + a1 + a3;
a[i + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + 2 * p] = a0 + na2 + a1na3imag;
a[i + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
}
}
}
}
template<class RandomAccessIterator>
void IButterfly(RandomAccessIterator a, int n) const {
int h = ceil_pow2(n);
static const fft_info info;
constexpr int MOD = mint::mod();
int len = h;
for (; 1 < len; len -= 2) {
int p = 1 << (h - len);
mint irot = 1, iimag = info.iroot[2];
for (int s = 0; s < (1 << (len - 2)); s++) {
if (s) irot *= info.irate3[LsbIndex(~(u32)(s - 1))];
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = (s << (h - len + 2)) + p;
for (int i = offset - p; i < offset; i++) {
u64 a0 = a[i].val();
u64 a1 = a[i + p].val();
u64 a2 = a[i + 2 * p].val();
u64 a3 = a[i + 3 * p].val();
u64 a2na3iimag = mint((a2 + MOD - a3) * iimag.val()).val();
a[i] = a0 + a1 + a2 + a3;
a[i + p] = (a0 + (MOD - a1) + a2na3iimag) * irot.val();
a[i + 2 * p] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val();
a[i + 3 * p] = (a0 + (MOD - a1) + (MOD - a2na3iimag)) * irot3.val();
}
}
}
if (len == 1) {
int p = 1 << (h - len);
for (int i = 0; i < p; i++) {
mint l = a[i], r = a[i + p];
a[i] = l + r;
a[i + p] = l - r;
}
}
}
};
} // namespace nachia
namespace nachia {
struct BigintDecMulManager {
using Int = int;
using Arr = std::vector<Int>;
using u32 = unsigned int;
using i64 = long long;
static const Int B = 1000000000;
static const u32 MOD0 = 0x1c000001;
static const u32 MOD1 = 0x6c000001;
static const u32 MOD2 = 0x78000001;
static const u32 I0_M1 = 1540148431;
static const u32 I01_M2 = 1050399624;
static const u32 I1_M2 = 10;
static const u32 IB_M1 = 1575545083;
static const u32 IB_M2 = 65929464;
template<u32 MOD>
static std::vector<u32> convMod(int z, int n, const Arr& a, const Arr& b) {
using Mint = StaticModint<MOD>;
static auto ntt = NttFromAcl<Mint>();
std::vector<Mint> a2(z);
for (int i = 0; i < (int)a.size(); i++)
a2[i] = a[i];
std::vector<Mint> b2(z);
for (int i = 0; i < (int)b.size(); i++)
b2[i] = b[i];
Mint c = Mint(z).inv();
ntt.Butterfly(a2.begin(), z);
ntt.Butterfly(b2.begin(), z);
for (int i = 0; i < z; i++)
a2[i] *= b2[i] * c;
ntt.IButterfly(a2.begin(), z);
std::vector<u32> res(n);
for (int i = 0; i < n; i++)
res[i] = a2[i].val();
return res;
}
template<u32 M>
static inline StaticModint<M> SubMod(u32 a, u32 b) {
return StaticModint<M>::raw(a < b ? a + M - b : a - b);
}
static Arr BigintDecMul(const Arr& a, const Arr& b) {
int n = a.size() + b.size();
int n2 = 1;
while (n2 < n)
n2 *= 2;
auto c0 = convMod<MOD0>(n2, n - 1, a, b);
auto c1 = convMod<MOD1>(n2, n - 1, a, b);
auto c2 = convMod<MOD2>(n2, n - 1, a, b);
std::vector<i64> c(n + 1);
using MintB = StaticModint<B>;
using Mint1 = StaticModint<MOD1>;
using Mint2 = StaticModint<MOD2>;
auto i0m1 = Mint1::raw(I0_M1);
auto i01m2 = Mint2::raw(I01_M2);
auto ibm1 = Mint1::raw(IB_M1);
auto ibm2 = Mint2::raw(IB_M2);
auto i1m2 = Mint2::raw(I1_M2);
auto m0_2 = Mint2::raw(MOD0);
auto m0_b = MintB::raw(MOD0);
auto m01_b = m0_b * MintB(MOD1);
for (int i = 0; i < n - 1; i++) {
u32 d0to1 = (i0m1 * SubMod<MOD1>(c1[i], c0[i])).val();
Mint2 x01m2 = Mint2::raw(c0[i]) + m0_2 * Mint2::raw(d0to1);
MintB x01mB = MintB::raw(c0[i]) + m0_b * MintB(d0to1);
MintB xmB = x01mB + m01_b * MintB((i01m2 * SubMod<MOD2>(c2[i], x01m2.val())).val());
c[i] += xmB.val();
Mint1 y1 = SubMod<MOD1>(c1[i], xmB.val()) * ibm1;
Mint2 y2 = SubMod<MOD2>(c2[i], xmB.val()) * ibm2;
i64 y12 = (i64)y1.val() + (i64)MOD1 * (i64)(i1m2 * SubMod<MOD2>(y2.val(), y1.val())).val();
c[i + 1] += y12 % B;
c[i + 2] += y12 / B;
}
Arr res(n);
for (int i = 0; i < n; i++) {
res[i] = c[i] % B;
c[i + 1] += c[i] / B;
}
if (res.back() == 0) res.pop_back();
return res;
}
};
};
namespace nachia {
struct BigIntDec {
using Int = int;
BigIntDec() : sign(0), A(0) {}
BigIntDec(int z) {
if (z == 0) {
sign = 0;
} else if (z < 0) {
sign = -1;
A = std::vector<int>(1, -z);
} else {
sign = 1;
A = std::vector<int>(1, z);
}
}
BigIntDec(const std::string& s) : sign(1) {
auto it = s.begin();
if (it != s.end()) {
if (*it == '-') {
sign = -1;
it++;
} else if (*it == '+') {
it++;
}
}
while (it != s.end() && *it == '0')
it++;
if (it == s.end()) {
sign = 0;
} else {
auto f = (s.end() - it);
int e = int((f - 1) / 9);
int d = int((f - 1) % 9);
A.assign(e + 1, 0);
for (; it != s.end(); it++) {
assert('0' <= *it && *it <= '9');
A[e] = A[e] * 10 + (*it - '0');
d--;
if (d < 0) {
d = 8;
e -= 1;
}
}
}
}
BigIntDec operator+(const BigIntDec& r) const {
if (r.isZero()) return *this;
if (isZero()) return r;
auto x = (sign == r.sign) ? uintSum(*this, r) : uintDiff(*this, r);
x.sign *= sign;
return x;
}
BigIntDec operator-() const { return raw(-sign, A); }
BigIntDec operator-(const BigIntDec& r) {
if (r.isZero()) return *this;
if (isZero()) return -r;
auto x = (sign == r.sign) ? uintDiff(*this, r) : uintSum(*this, r);
x.sign *= sign;
return x;
}
BigIntDec operator*(const BigIntDec& r) {
if (isZero() || r.isZero()) return Zero();
return raw(sign * r.sign, uintMul(*this, r));
}
static BigIntDec Zero() { return BigIntDec(); }
bool isZero() const { return sign == 0; }
std::string toString() const {
if (isZero()) return "0";
std::string s;
for (int i = 0; i < len() - 1; i++) {
int a = A[i];
for (int d = 0; d < 9; d++) {
s.push_back('0' + a % 10);
a /= 10;
}
}
for (int a = A[len() - 1]; a != 0; a /= 10)
s.push_back('0' + a % 10);
if (sign < 0) s.push_back('-');
std::reverse(s.begin(), s.end());
return s;
}
private:
using Arr = std::vector<int>;
using Self = BigIntDec;
using i64 = long long;
int sign;
std::vector<Int> A;
static const int B = 1000000000;
int len() const { return int(A.size()); }
Int dig(int z) const { return z < len() ? A[z] : 0; }
Int& operator[](int z) { return A[z]; }
const Int& operator[](int z) const { return A[z]; }
static int CmpUintPos(const Self& l, const Self& r) {
if (l.len() != r.len()) return std::max(l.len(), r.len()) - 1;
for (int i = l.len() - 1; i >= 0; i--)
if (l[i] != r[i]) return i;
return -1;
}
static Self raw(int sign, Arr a) {
if (a.empty()) sign = 0;
Self res;
res.sign = sign;
res.A = std::move(a);
return res;
}
static Self uintDiff2(const Self& l, const Self& r, int k) {
std::vector<Int> A(k + 1);
for (int i = 0; i <= k; i++)
A[i] = l[i];
int j = std::min(k + 1, r.len());
Int v = 0;
for (int i = 0; i < j; i++) {
v = v + A[i] - r[i];
if (v < 0) {
A[i] = v + B;
v = -1;
} else {
A[i] = v;
v = 0;
}
}
for (int i = j; v != 0; j++) {
v = v + A[i];
if (v < 0) {
A[i] = v + B;
v = -1;
} else {
A[i] = v;
v = 0;
}
}
return raw(1, std::move(A));
}
static Self uintDiff(const Self& l, const Self& r) {
int k = CmpUintPos(l, r);
if (k == -1) return Zero();
if (l.dig(k) > r.dig(k)) return uintDiff2(l, r, k);
auto x = uintDiff2(r, l, k);
x.sign = -x.sign;
return x;
}
static Self uintSum(const Self& l, const Self& r) {
if (l.len() > r.len()) return uintSum(r, l);
std::vector<Int> A(r.len() + 1);
for (int i = 0; i < l.len(); i++)
A[i] = l[i];
Int v = 0;
for (int i = 0; i < r.len(); i++) {
v = v + A[i] + r[i];
if (B <= v) {
A[i] = v - B;
v = 1;
} else {
A[i] = v;
v = 0;
}
}
if (v != 0)
A[r.len()] = v;
else
A.pop_back();
return raw(1, std::move(A));
}
static Arr uintMul(const Self& l, const Self& r) {
if (l.len() >= 30 && r.len() >= 30) {
return BigintDecMulManager::BigintDecMul(l.A, r.A);
}
int z = l.len() + r.len();
Arr a(z);
for (int i = 0; i < l.len(); i++)
for (int j = 0; j < r.len(); j++) {
i64 x = (i64)(l[i]) * r[j] + a[i + j];
a[i + j] = x % B;
a[i + j + 1] += x / B;
}
if (a.back() == 0) a.pop_back();
return a;
}
};
};
namespace {
std::istream& operator>>(std::istream& i, nachia::BigIntDec& d) {
std::string s;
i >> s;
d = nachia::BigIntDec(s);
return i;
}
std::ostream& operator<<(std::ostream& o, const nachia::BigIntDec& d) {
return o << d.toString();
}
}
int64_t k, c;
std::map<int64_t, int> res;
using u64 = uint64_t;
static inline u64 mul_mod(u64 a, u64 b, u64 mod) {
a %= mod;
b %= mod;
u64 res = 0;
while (b) {
if (b & 1) {
res += a;
if (res >= mod) res -= mod;
}
b >>= 1;
if (b) {
a += a;
if (a >= mod) a -= mod;
}
}
return res;
}
static inline u64 pow_mod(u64 a, u64 d, u64 mod) {
u64 res = 1;
while (d) {
if (d & 1) res = mul_mod(res, a, mod);
a = mul_mod(a, a, mod);
d >>= 1;
}
return res;
}
static constexpr u64 small[] = {2ull, 3ull, 5ull, 7ull, 11ull, 13ull, 17ull, 19ull, 23ull, 29ull, 31ull, 37ull};
// bases deterministic for 64-bit integers
static constexpr u64 bases[] = {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL};
// Miller-Rabin
bool is_prime(u64 n) {
if (n < 2) return false;
for (u64 p : small) {
if (n % p == 0) return n == p;
}
// write n-1 = d * 2^s
u64 d = n - 1, s = 0;
while ((d & 1) == 0) {
d >>= 1;
++s;
}
for (u64 a : bases) {
if (a % n == 0) continue;
u64 x = pow_mod(a, d, n);
if (x == 1 || x == n - 1) continue;
bool composite = true;
for (u64 r = 1; r < s; ++r) {
x = mul_mod(x, x, n);
if (x == n - 1) {
composite = false;
break;
}
}
if (composite) return false;
}
return true;
}
vector<int> smallPrimes;
// Sito
void build_small_primes() {
int limit = m + 1;
vector<char> is_comp(limit + 1, 0);
for (int i = 2; i <= limit; ++i)
if (!is_comp[i]) {
smallPrimes.push_back(i);
if ((long long)i * i <= limit)
for (int j = i * i; j <= limit; j += i)
is_comp[j] = 1;
}
}
void skrocenie(int p) {
int kr = 0;
for (int i = 1; i <= n; i++) {
while (nums[i] % p == 0) {
nums[i] = nums[i] / p;
kr++;
}
}
if (kr > k) {
k = kr;
c = 1;
} else if (kr == k)
c++;
}
void solve() {
std::cin >> n;
for (int i = 1; i <= n; i++) {
std::cin >> nums[i];
}
build_small_primes();
// faza I
for (const auto& p : smallPrimes) {
skrocenie(p);
}
// faza II
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
int64_t d = fast_gcd(nums[i], nums[j]);
if (d > 1 && d < std::max(nums[i], nums[j])) {
skrocenie(d);
}
}
}
// faza III
for (int i = 1; i <= n; i++) {
if (nums[i] > 1) {
int64_t d = sqrtl(nums[i]);
if (d * d == nums[i]) skrocenie(d);
}
}
// faza IV
for (int i = 1; i <= n; i++) {
if (nums[i] > 1) {
int kr = 1;
for (int j = i + 1; j <= n; j++) {
if (nums[j] == nums[i]) {
nums[j] = 1;
kr++;
}
}
int ile = 2;
if (is_prime(nums[i])) ile = 1;
nums[i] = 1;
if (kr > k) {
k = kr;
c = ile;
} else if (kr == k) {
c += ile;
}
}
}
std::cout << k << '\n';
nachia::BigIntDec ans2 = 1;
for (int i = 0; i < c; i++) {
ans2 = ans2 * 2;
}
ans2 = ans2 - 1;
std::cout << ans2 << '\n';
}
int32_t main() {
#ifndef GARY_DBG
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
#endif
int t = 1;
// std::cin >> t;
for (; t > 0; t--) {
solve();
}
return 0;
}