Counting Valid Factor Sequences

Elly is studying an interesting property of a positive integer \(N\). She has observed that \(N\) has no more than 6 distinct prime factors. Using \(N\), she generates a list (initially empty) by repeatedly appending a divisor \(x\) (> 1) of \(N\) subject to the following rule: before appending \(x\), among all numbers already in the list there must not be more than one number which is not coprime with \(x\) (i.e. sharing a common factor greater than 1).

For example, when \(N = 12156144\) some legal lists include:

• (42)
• (616, 6, 91, 23)
• (91, 616, 6, 23)
• (66, 7)
• (66, 7, 7, 23, 299, 66)
• (143, 13, 66)
• (42, 12156144)

Illegal examples include:

• (5, 11) because 5 is not a divisor of \(N\);
• (66, 13, 143) because 143 is not coprime with both 66 and 13.

Your task is: given \(N\), count how many different legal lists can be generated by this process. Two lists are considered different if their lengths differ or there is at least one position at which the numbers are different.

Note: Every number you append must be a divisor of \(N\) (and greater than 1). Also, when appending a new number \(x\) with a set of prime factors \(S\), if you check every number \(y\) already in the list then the number of \(y\) with \(\gcd(x,y)>1\) must not exceed 1.

Formulas are written in LaTeX format.

inputFormat

The input consists of a single line containing the positive integer \(N\). It is guaranteed that \(N\) has no more than 6 distinct prime factors.

outputFormat

Output a single integer representing the number of different legal lists that can be generated.

sample

4

6