Ionel are de rezolvat o nouă problemă. El trebuie să construiască un șir de N numere naturale. Numerele din șir pot avea ca divizori primi doar numere prime de o cifră. După construirea șirului, Ionel a constatat că există subsecvențe în șir pentru care produsul elementelor este cubul unui număr natural.

Cerința

Ionel vrea să determine numărul subsecvențelor din șirul construit care au produsul elementelor o valoare ce este cubul unui număr natural.

Date de intrare

Fișierul de intrare cub.in va conține pe prima linie numărul natural N, iar pe linia următoare se vor afla N numere naturale separate prin câte un spațiu, elementele șirului construit de Ionel.

Date de ieșire

Fișierul de ieșire cub.out va conține pe prima linie un număr natural reprezentând numărul subsecvenţelor din șirul construit care au produsul elementelor egal cu o valoare ce este cubul unui număr natural.

Restricții și precizări

• N și elemente șirului sunt numere naturale din intervalul [2, 1.000.000].
• Prin subsecvenţă a unui șir se înțelege o succesiune de unul sau mai mulți termeni din șir aflați pe poziții consecutive.
• Pentru teste în valoare de 20 de puncte, N ≤ 1.000.
• Pentru teste în valoare de 40 de puncte, N ≤ 10.000.

Exemplu

cub.in

8
15 3 5 15 7 63 21 125

cub.out

6

Explicație

Sunt 6 subsecvențe în șir cu produsul elementelor egal cu o valoare care este cubul unui număr natural:
15 3 5 15
7 63 21
125
15 3 5 15 7 63 21
7 63 21 125
15 3 5 15 7 63 21 125

#include <bits/stdc++.h>
using namespace std;

ifstream cin("cub.in");
ofstream cout("cub.out");

int exp(int n , int x)
{
    int c = 0;
    while(n % x == 0)
    {
        n /= x;
        c++;
    }
    return c;

}

int main()
{
    int n , c2 = 0 , c3 = 0 , c5 = 0 , f[1001] = {0} , x , c7 = 0;
    unsigned long long c = 0;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        c2 = (c2 + exp(x , 2)) % 3;
        c3 = (c3 + exp(x , 3)) % 3;
        c5 = (c5 + exp(x , 5)) % 3;
        c7 = (c7 + exp(x , 7)) % 3;
        f[27*c2 + 9*c3 + 3*c5 + c7]++;
        //cout << 4*c2 + 2*c3 + c5 << endl;
    }
    c = f[0];
    for(int i = 0 ; i <= 80 ; i++)
        c = c + 1ll * f[i] * (f[i] - 1) / 2;
    cout << c;
}