All Tracks Math Number Theory Problem

Gold at Lolympics
Tag(s):

Dynamic Programming, Easy-Medium, Game Theory, Math, Prime Factorization

Problem
Editorial
Analytics

Troller dreams of going to the Lolympics to represent his newly formed country, Byteland. A new game has come up at the Lolympics, and Troller believes he has the skills to win a Gold for his country.

Let's learn the rules of the game. You are given $$N$$ numbers : $$A_1,A_2 ... A_N$$. Troller and his opponent take alternating turns, starting with Troller's turn. In every turn, one has to choose one of the $$N$$ numbers and reduce it to one of it's divisors. For example, if a number is $$6$$, then you can reduce it to $$1$$,$$2$$ or $$3$$ in a single step. It's easy to see that you can't reduce $$1$$ to anything.

Troller is smart, and hence knows beforehand if he is going to win or not if the game is played optimally. Hence, he's more interested in knowing how many non empty subsets of the N numbers leads him to a victory if the game is played optimally on the chosen subset. Help him with this problem, while he prepares for Gold!

Input Format:
The first line contains $$N$$, the count of numbers. The next line contains $$N$$ space separated integers $$A_1, A_2, A_3 ... A_N$$.

Output Format:
Output consists of one integer, the number of ways you can choose a non-empty subset such that you win the game if played optimally. Since this integer can be very big, output it modulo $$10^9$$ + 7.

Constraints:
$$1 \le N \le 500$$
$$1 \le Ai \le 10^{15}$$

SAMPLE INPUT
3
1 4 8
SAMPLE OUTPUT
6
Explanation

You can choose {4},{8},{1,4},{1,8},{4,8},{1,4,8}. If played optimally, each of these sets will favour Troller.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

October Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications