# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Is It Perfect

Bob has an initial array **D** of length **n** . Alice is a good friend of Bob. So Bob challenges Alice to finish the following task with this array D.

A Sequence G is called **PERFECT** if elements of G are **distinct** and one of the two following properties hold :

1. If product of elements of G is a **perfect-square** then number of elements of G should be **even** .

2. If product of elements of is not a **perfect-square** then number of elements of G should be **odd** .

Alice’s task is to find out the number of different ways to construct non-empty **PERFECT** sub-sequences of D. Alice is not an expert programmer. So now he wants your help. Can you find it?

A sub-sequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Two ways are considered different if sets of indexes of elements chosen by these ways are different. You have to find the answer
modulo **993344777**.

#### Input

First line contains one integer n (1 ≤ n ≤ 10^6) — the number of elements in the array.

Second line contains n integers - the elements of the array D where 1≤ D[i] ≤ 60 for 1 ≤ i ≤ n .

#### Output

Print one integer — the number of different ways modulo **993344777**.

#### Samples

Input | Output |
---|---|

2 2 8 | 3 |

3 3 2 7 | 4 |

For the first test case, you can make three sub-sequences :

1. you can choose only 2

2. you can choose only 8

3. you can choose both 2 and 8 because 2 * 8 = 16 is a perfect-square

Login to submit