OI XVII - naj

// 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;
}

class BigInt {
    std::vector<int> digits;

public:
    BigInt(int n = 0) {
        if (n == 0) digits.push_back(0);
        while (n > 0) {
            digits.push_back(n % 10);
            n /= 10;
        }
    }

    BigInt operator*(int n) const {
        BigInt res = *this;
        int carry = 0;
        for (size_t i = 0; i < res.digits.size() || carry; ++i) {
            if (i == res.digits.size()) res.digits.push_back(0);
            long long current = res.digits[i] * (long long)n + carry;
            res.digits[i] = current % 10;
            carry = current / 10;
        }
        return res;
    }

    BigInt operator-(int n) const {
        BigInt res = *this;
        res.digits[0] -= n;

        int i = 0;
        while (i < res.digits.size() && res.digits[i] < 0) {
            res.digits[i] += 10;
            res.digits[i + 1]--;
            i++;
        }

        while (res.digits.size() > 1 && res.digits.back() == 0) {
            res.digits.pop_back();
        }
        return res;
    }

    std::string to_string() const {
        if (digits.empty()) return "0";
        std::string s = "";
        for (int i = digits.size() - 1; i >= 0; --i) {
            s += std::to_string(digits[i]);
        }
        return s;
    }
};

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';

    BigInt ans2(1);
    for (int i = 0; i < c; i++) {
        ans2 = ans2 * 2;
    }
    ans2 = ans2 - 1;

    std::cout << ans2.to_string() << '\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;
}