All Tracks Math Number Theory Basic Number Theory-1 Problem

Deadpool Set
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

You are given a Deadpool set A which contains N unique integers.

The speciality of a Deadpool set is that if you remove a integer from the set it reappears magically, just like Deadpool's body parts. :3

Given this set you have to print number of unique Deadpool trees that can be made by using integers from that set.

Note : As the integers reappear magically, they can be used several times in a particular Deadpool Tree.

Properties of Deadpool tree:

  1. Each node is either a leaf node or has exactly two children.

  2. If a node is not a leaf node then it's value is exactly equal to the product of its children.

  3. The value of each node is greater than '1'.

Constraints:

1<=N<=106
1<=A[i]<=106

It is guaranteed that numbers in the set are unique.

Input:

First line has a single number N.

Each of the following N lines has a single number denoting the values of numbers in the set A.

Output:

Print ans modulo 109+7 where ans is the number of unique Deadpool trees.

Problem Setter - Teja Vojjala

SAMPLE INPUT
4
2
3
4
6
SAMPLE OUTPUT
7
Explanation

The contents of deadpool set are 2,3,4,6. If we remove a number from this set it reappears magically so the contents of the set are always 2,3,4,6 no matter what and we have an infinite supply of 2,3,4,6. The following are the only trees which satisfy the deadpool tree properties.

Note that in each tree each node is either a leaf node or a node with exactly two children whose values is same as the product of its children and value in each node is greater than 1.

enter image description here

Time Limit: 2.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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications