Problem:
 Score : 400 points    Problem Statement You are given an integer N . Among the divisors of N!  (= 1 \times 2 \times ... \times N) , how many Shichi-Go numbers (literally "Seven-Five numbers") are there?  Here, a Shichi-Go number is a positive integer that has exactly 75 divisors.      Note When a positive integer A divides a positive integer B , A is said to a divisor of B .
For example, 6 has four divisors: 1, 2, 3 and 6 .      Constraints  1 \leq N \leq 100  N is an integer.         Input Input is given from Standard Input in the following format:  N       Output Print the number of the Shichi-Go numbers that are divisors of N! .        Sample Input 1 9      Sample Output 1 0  There are no Shichi-Go numbers among the divisors of 9! = 1 \times 2 \times ... \times 9 = 362880 .       Sample Input 2 10      Sample Output 2 1  There is one Shichi-Go number among the divisors of 10! = 3628800 : 32400 .       Sample Input 3 100      Sample Output 3 543

Solution (Python):
N = int(input())

primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

import math
NK=math.factorial(N)
from itertools import permutations, combinations,combinations_with_replacement,product
L = combinations(range(0,len(primes)), 3)   
L = list(L)
ans = 0
for i in L:
  x = ((primes[i[0]]**4)*(primes[i[1]]**4)*(primes[i[2]]**2))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[1]]**4)*(primes[i[2]]**4)*(primes[i[0]]**2))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[2]]**4)*(primes[i[0]]**4)*(primes[i[1]]**2))
  if NK % x ==0:
    ans +=1

L = combinations(range(0,len(primes)), 2)   
L = list(L)
for i in L:
  x = ((primes[i[0]]**24)*(primes[i[1]]**2))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[1]]**24)*(primes[i[0]]**2))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[0]]**14)*(primes[i[1]]**4))
  if NK % x ==0:
    ans +=1
  x = ((primes[i[1]]**14)*(primes[i[0]]**4))
  if NK % x ==0:
    ans +=1

L = combinations(range(0,len(primes)), 1)   
L = list(L)
for i in L:
  x = ((primes[i[0]]**74))
  if NK % x ==0:
    ans +=1

print(ans)

Solution (Python):
N = int(input())

def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

plis = searchPrimeNum(100)

def pfact(N,dic):
    for p in plis:
        if N%p == 0:
            dic[p] += 1
            N = N//p
        while N%p == 0:
            dic[p] += 1
            N = N//p
        if N == 1:
            break
    return dic

dict = {}
for p in plis:
    dict[p] = 0

for i in range(1,N+1):
    dict = pfact(i,dict)

nlis = [0,0,0,0,0]
r = [75,25,15,5,3]
for i in dict.values():
    for j in range(len(r)):
        if i >= r[j]-1:
            nlis[j] += 1
ans = 0
ans += nlis[0]
ans += nlis[1]*(nlis[-1]-1)
ans += nlis[2]*(nlis[-2]-1)
ans += nlis[-2]*(nlis[-2]-1)*(nlis[-1]-2)//2
print(ans)

Solution (Python):
from collections import defaultdict

N = int(input())
prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,
        43,47,53,59,61,67,71,73,79,83,89,97]
ans = 0
factor = defaultdict(int)
for i in range(1,N+1):
    for j in prime:
        while i != 1:
            if i % j == 0:
                factor[j] += 1
                i = i // j
            else:
                break

fact_l = list(dict(factor).items())
fact_l.sort()
n_74 = 0
n_24 = 0
n_14 = 0
n_4 = 0
n_2 = 0
for i, x in enumerate(fact_l):
    if x[1] >= 74:
        n_74 = i + 1
    if x[1] >= 24:
        n_24 = i + 1
    if x[1] >= 14:
        n_14 = i + 1
    if x[1] >= 4:
        n_4 = i + 1
    if x[1] >= 2:
        n_2 = i + 1

print(n_74+(n_24*(n_2-1))+(n_14*(n_4-1))+(n_4*(n_4-1)*(n_2-2)//2))

Solution (Python):
N = int(input())

primenum = [0]*101

def make_divisor(n):
    res = []
    for i in range(1,int(n**0.5+1)):
        if i*i == n:
            res.append(i)
        else:
            res.append(i)
            res.append(n//i)
    return res

def fact(n):
    if n==1:
        return 
    else:
        divs = make_divisor(n)
        divs.sort()
        tmp = n
        idx = 1
        while(tmp>1):
            while (tmp%divs[idx]==0):
                primenum[divs[idx]] += 1
                tmp //= divs[idx]
            idx += 1
        fact(n-1)
        return 


fact(N)

ans = 0
primenum.sort(reverse = True)
idx = 0
while primenum[idx]>=74: idx += 1
ans += idx

idx2 = 0
while primenum[idx]>=24: idx += 1
while primenum[idx+idx2]>=2:idx2 += 1
ans += idx*(idx-1+idx2)

idx = 0
idx2 = 0
while primenum[idx]>=14: idx += 1
while primenum[idx+idx2]>=4:idx2 += 1
ans += idx*(idx-1+idx2)

idx = idx+idx2
idx2 = 0
while primenum[idx+idx2]>=2: idx2 += 1
ans += idx*(idx-1)//2*(idx-2+idx2)
print(ans)

Solution (Python):
import collections

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N = int(input())
Prime=[]
for i in range(2,N+1):
  Prime +=prime_factorize(i)
  
c=collections.Counter(Prime)
P_count=c.values()

count_2=len([1 for x in P_count if x>=2])
count_4=len([1 for x in P_count if x>=4])
count_14=len([1 for x in P_count if x>=14])
count_24=len([1 for x in P_count if x>=24])
count_74=len([1 for x in P_count if x>=74])
answer=(count_2-2)*(count_4-1)*count_4//2+(count_4-1)*count_14+(count_2-1)*count_24+count_74
print(answer)

Solution (Python):
N = int(input())
import math
import random
from itertools import permutations

res_dict = {i : 0 for i in range(1,101)}
class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        
        witnesses = self.get_witnesses(n)
        

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


prime = Prime()
for i in range(2,N+1):
    res = prime.find_factors(i)
    for k, v in res.items():
        res_dict[k] += v
res_dict = {i : j + 1 for i, j in res_dict.items() if j >= 2}
res = 0
for combi in permutations(res_dict.items(), 3):
    if combi[0][1] >= 5 and combi[1][1] >= 5:
        res += 1
res //= 2
for combi in permutations(res_dict.items(), 2):
    if combi[0][1] >= 25:
        res += 1
    if combi[0][1] >= 15 and combi[1][1] >= 5:
        res += 1
for combi in res_dict.items():
    if combi[1] >= 75:
        res += 1
print(res)

Solution (Python):

import sys
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    
    return table

def solve(N: int):
    from collections import Counter
    counter = Counter(prime_decomposition(math.factorial(N)))
    prime_counts = sorted(list(counter.values()),reverse=True)

    
    d = {74:[],24:[],14:[],4:[],2:[],1:[]}
    for i,count in enumerate(prime_counts):
        for key,_ in d.items():
            if count>=key:
                d[key].append(i)

    answer = 0
    
    if d.get(74):
        answer += len(d[74])
    
    if d.get(24):
        answer += len(d[24])*(len(d[2])-1)

    
    if d.get(14):
        answer += len(d[14])*(len(d[4])-1)

    if len(d.get(4))>=2:
        answer += combinations_count(len(d[4]),2)*(len(d[2])-2)

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
e=[0]*(n+1)
for i in range(2,n+1):
    cur=i
    for j in range(2,i+1):
        while cur%j==0:
            e[j]+=1
            cur//=j
def num(m):
    return len(list(filter(lambda  x: x>=m-1,e)))

print(num(75)+num(25)*(num(3)-1)+num(15)*(num(5)-1)+num(5)*(num(5)-1)*(num(3)-2)//2)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return {i for i in range(n + 1) if is_prime[i]}


n = I()
prime_set = primes(n)
prime_cnt = Counter()
for p in prime_set:
    pi = p
    while pi < n:
        prime_cnt[p] += n // pi
        pi *= p


prime_cnt = [v for k, v in prime_cnt.most_common()][::-1]
m = len(prime_cnt)
print(m - bisect_left(prime_cnt, 74) + (m - bisect_left(prime_cnt, 24)) * (m - bisect_left(prime_cnt, 2) - 1)
    + (m - bisect_left(prime_cnt, 14)) * (m - bisect_left(prime_cnt, 4) - 1)
    + (m - bisect_left(prime_cnt, 4)) * ((m - bisect_left(prime_cnt, 4)) - 1) // 2 * ((m - bisect_left(prime_cnt, 2)) - 2))

Solution (Python):
A=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a 

B=[0]*15
for i in range(1,int(input())+1):
    w=prime_factorize(i)
    for j in w:
        if j<=47:
            B[A.index(j)]+=1

def num(m):
    return len(list(filter(lambda x:x>=m,B)))

print((num(2)-2)*num(4)*(num(4)-1)//2+num(14)*(num(4)-1)+num(24)*(num(2)-1)+num(74))

Solution (Python):
n = int(input())
hurui = [1]*(n+1)
hurui[0] = 0
hurui[1] = 0
sq = int(n**(1/2))+3

for i in range(2,sq):
    for j in range(2,n//i+1):
        hurui[j*i] = 0
p = []

for i in range(n+1):
    if hurui[i]:
        p.append(i)

cnt = {pi:0 for pi in p}

for pi in p:
    tmp = n
    while tmp>0:
        tmp //= pi
        cnt[pi] += tmp
      
cnt2 = {2:0, 4:0, 14:0, 24:0,74:0}

for key in cnt:
    if cnt[key] >= 2:
        cnt2[2]+=1
    if cnt[key] >= 4:
        cnt2[4]+=1
    if cnt[key] >= 14:
        cnt2[14]+=1
    if cnt[key] >= 24:
        cnt2[24]+=1
    if cnt[key] >= 74:
        cnt2[74]+=1

ans = 0

ans += (cnt2[2]-1)*cnt2[24]
ans += (cnt2[4]-1)*cnt2[14]
ans += (cnt2[2]-2)*cnt2[4]*(cnt2[4]-1)//2
ans += cnt2[74]
print(ans)

Solution (Python):
"""
22:17:30

"""

from collections import defaultdict
N = int(input())


def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        
        data = [d for d in data if d%p != 0]

def factorization(N):
    factors = defaultdict(int)
    for n in range(1,N+1):
        if n <= 3:
            factors[n] += 1
            continue
        primes = getprime(int(n**0.5))
        for prime in primes:
            while n % prime == 0:
                factors[prime] += 1
                n //= prime
                
        if n != 1:
            factors[n] += 1
    return factors

d = factorization(N)

n_74 = 0
n_24 = 0
n_14 = 0
n_4 = 0
n_2 = 0
for k in d.keys():
    n = d[k]
    if n >= 2:
        n_2 += 1
    if n >= 4:
        n_4 += 1
    if n >= 14:
        n_14 += 1
    if n >= 24:
        n_24 += 1
    if n >= 74:
        n_74 += 1

cnt = 0

cnt += n_74

cnt += (n_2-1) * n_24

cnt += (n_4-1) * n_14

cnt += (n_2-2) * (n_4)*(n_4-1)//2
print(cnt)

Solution (Python):
from collections import defaultdict


n = int(input())
div = defaultdict(int)

for i in range(2, n+1):
    num = i
    while num != 1:
        for d in range(2, num+1):
            if num % d == 0:
                num //= d
                div[d] += 1
                break
            else:
                continue

values = list(div.values())
over2 = 0
over4 = 0
over14 = 0
over24 = 0
over74 = 0
for value in values:
    if value >= 2:
        over2 += 1
    if value >= 4:
        over4 += 1
    if value >= 14:
        over14 += 1
    if value >= 24:
        over24 += 1
    if value >= 74:
        over74 += 1

ans1 = max(0, over4 * (over4-1) * (over2-2) // 2)
ans2 = max(0, over14 * (over4-1))
ans3 = max(0, over24 * (over2-1))
ans4 = over74
res = sum([ans1, ans2, ans3, ans4])
print(res)

Solution (Python):
from collections import defaultdict


n = int(input())
div = defaultdict(int)

for i in range(2, n+1):
    num = i
    while num != 1:
        for d in range(2, num+1):
            if num % d == 0:
                num //= d
                div[d] += 1
                break
            else:
                continue

values = list(div.values())
over2 = 0
over4 = 0
over14 = 0
over24 = 0
over74 = 0
for value in values:
    if value >= 2:
        over2 += 1
    if value >= 4:
        over4 += 1
    if value >= 14:
        over14 += 1
    if value >= 24:
        over24 += 1
    if value >= 74:
        over74 += 1

ans1 = max(0, over4 * (over4-1) * (over2-2) // 2)
ans2 = max(0, over14 * (over4-1))
ans3 = max(0, over24 * (over2-1))
ans4 = over74
res = sum([ans1, ans2, ans3, ans4])
print(res)

Solution (Python):
n = int(input())
primeL = []
for i in range(2,n+1):
    key = 0
    for j in primeL:
        if i % j == 0:
            key = 1
    if key == 0:
        primeL.append(i)
l = []
for i in primeL:
    count = 0
    a = i
    while a <= n:
        count += n//a
        a *= i
    l.append(count)
p = 0
q = 0
r = 0
s = 0
t = 0
for i in range(len(l)):
    if l[i] >= 74:
        p += 1
    if l[i] >= 24:
        q += 1
    if l[i] >= 14:
        r += 1
    if l[i] >= 4:
        s += 1
    if l[i] >= 2:
        t += 1
ans = 0
ans += p
ans += q*(t-1)
ans += r*(s-1)
ans += s*(s-1)*(t-2)//2
print(ans)

Solution (Python):
import itertools
N = int(input())
prm = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
abc = list(itertools.permutations(prm,3))
ab  = list(itertools.permutations(prm,2))
ans = 0
for i in abc:
    a=0; b=0; c=0
    A=i[0]; B=i[1]; C=i[2]
    while A<=N:
        a += N//A
        A *= i[0]
    while B<=N:
        b += N//B
        B *= i[1]
    while C<=N:
        c += N//C
        C *= i[2]
    if a>=4 and b>=4 and c>=2:
        ans += 1
ans //= 2
for i in ab:
    a=0; b=0
    A=i[0]; B=i[1]
    while A<=N:
        a += N//A
        A *= i[0]
    while B<=N:
        b += N//B
        B *= i[1]
    if a>=14 and b>=4:
        ans += 1
    if a>=24 and b>=2:
        ans += 1
for i in prm:
    a=0; A=i
    while A<=N:
        a += N//A
        A *= i
    if a>=74:
        ans += 1
print(ans)

Solution (Python):
from collections import defaultdict
n = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
d = defaultdict(int)

for i in range(1,n+1):
    prime = prime_factorize(i)
    for p in prime:
        d[p] += 1






over4 = 0
over2 = 0
over14 = 0
over24 = 0
over74 = 0
for dd in d.values():
    if dd >= 4:
        over4 += 1
    if dd >= 2:
        over2 += 1
    if dd >= 14:
        over14 += 1
    if dd >= 24:
        over24 += 1
    if dd >= 74:
        over74 += 1

i1 = over74
i2 = over24 * (over2 - 1)
i3 = over14 * (over4 - 1)
i4 = over4 * (over4 - 1) * (over2-2) // 2
print(i1+i2+i3+i4)

Solution (Python):
n=int(input())
primelist=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
ll=[0,0,0,0,0]
for i in range(len(primelist)):
  a=primelist[i]
  t=n
  po=0
  while(t>0):
    t=int(t/a)
    po+=t
  if(po>=74):
    ll[4]+=1
  if(po>=24):
    ll[3]+=1
  if(po>=14):
    ll[2]+=1
  if(po>=4):
    ll[1]+=1
  if(po>=2):
    ll[0]+=1
ans=ll[4]+(ll[3])*(ll[0]-1)+(ll[2])*(ll[1]-1)+(ll[1])*(ll[1]-1)*(ll[0]-2)/2
print(int(ans))

Solution (Python):
n=int(input())
c=[0]*(n+1)
for i in range(2,n+1):
  num=i
  for j in range(2,i+1):
    while num%j==0:
      c[j]+=1
      num //= j
def cnt(x):
  count=0
  for i in range(n+1):
    if c[i]>=x-1:count+=1
  return count
      
print(cnt(75)+cnt(25)*(cnt(3)-1)+cnt(15)*(cnt(5)-1)+cnt(5)*(cnt(5)-1)*(cnt(3)-2) //2)

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
fact = [0]*(N+1)
for i in range(2, N+1):
    tmp = i
    for j in range(2, i+1):
        while tmp % j == 0:
            fact[j] += 1
            tmp //= j


def num(m):
    return len([i for i in fact if i >= m-1])

ans = 0
ans += num(75) + num(25)*(num(3)-1) 
ans += num(15)*(num(5)-1) 
ans += num(5)*(num(5)-1)*(num(3)-2)//2
print(ans)

Solution (Python):
n=int(input())
P=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
c=0
for i in range(15):
  a=n
  b=0
  while a>=P[i]:
    a=a//P[i]
    b=b+a
  if b>=74:
    c=c+1
for i in range(15):
  a=n
  b=0
  while a>=P[i]:
    a=a//P[i]
    b=b+a
  if b>=24:
    d=0
    for j in range(15):
      if j==i:
        continue
      a=n
      b=0
      while a>=P[j]:
        a=a//P[j]
        b=b+a
      if b>=2:
        c=c+1
for i in range(15):
  a=n
  b=0
  while a>=P[i]:
    a=a//P[i]
    b=b+a
  if b>=14:
    d=0
    for j in range(15):
      if j==i:
        continue
      a=n
      b=0
      while a>=P[j]:
        a=a//P[j]
        b=b+a
      if b>=4:
        c=c+1
for i in range(15):
  a=n
  b=0
  while a>=P[i]:
    a=a//P[i]
    b=b+a
  if b>=4:
    d=0
    for j in range(i+1,15):
      if j==i:
        continue
      a=n
      b=0
      while a>=P[j]:
        a=a//P[j]
        b=b+a
      if b>=4:
        d=0
        for k in range(15):
          if k==i or k==j:
            continue
          a=n
          b=0
          while a>=P[k]:
            a=a//P[k]
            b=b+a
          if b>=2:
            c=c+1
print(c)

Solution (Python):
n=int(input())
if n<=9:
    print(0)
    exit()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
ans=[]
l=[]
for i in range(2,n+1):
    c=factorization(i)
    for j in c:
        if not j[0] in l:
            l.append(j[0])
            ans.append(j[1])
        else:
            ans[l.index(j[0])]+=j[1]
kai=0
k24=0
k2=0
k14=0
k4=0
for i in ans:
    if i>=74:
        kai+=1
    if i>=24:
        k24+=1
    if i>=2:
        k2+=1
    if i>=14:
        k14+=1
    if i>=4:
        k4+=1
print(kai+k24*(k2-1)+k14*(k4-1)+(k2-2)*k4*(k4-1)//2)

Solution (Python):
N = int(input())
e = [0] * (N+1)

for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
            cur //= j

def num(m): 
    return len(list(filter(lambda x: x >= m-1, e)))

answer = num(75) + num(25) * (num(3)-1) + num(15) * (num(5) - 1)\
    + num(5) * (num(5) - 1) * (num(3) - 2) // 2
print(answer)

Solution (Python):




import collections, math

N = int(input())


def prime_set(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5) + 1):
        primes.difference_update(range(i*2, n+1, i))
    return primes


def prime_factors_duplicating_list(n):
    f = []
    for i in prime_set(int(n**0.5) + 1):
        while n % i == 0:
            f.append(i)
            n //= i
    if n > 1:
        f.append(n)
    return f

def comb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N_factorial_prime_factors = []
for i in range(1, N+1):
    N_factorial_prime_factors.extend(prime_factors_duplicating_list(i))

N_factorial_prime_factors = collections.Counter(N_factorial_prime_factors)

n_74plus_factors = set()
n_24plus_factors = set()
n_14plus_factors = set()
n_4plus_factors = set()
n_2plus_factors = set()

for key in N_factorial_prime_factors:
    for border in [2,4,14,24,74]:
        if N_factorial_prime_factors[key] >= border:
            eval("n_" + str(border) + "plus_factors.add(key)")

ans = 0
ans += comb(len(n_4plus_factors), 2) * (len(n_4plus_factors) - 2 + len(n_2plus_factors - n_4plus_factors)) 
ans += len(n_14plus_factors) * (len(n_14plus_factors) - 1 + len(n_4plus_factors - n_14plus_factors)) 
ans += len(n_24plus_factors) * (len(n_24plus_factors) - 1 + len(n_2plus_factors - n_24plus_factors)) 
ans += len(n_74plus_factors) 

print(ans)

Solution (Python):
N = int(input())


def fac(n):
    att = []
    t = n
    for i in range(2, int(-(-n ** 0.5 // 1) + 1)):
        while (t % i == 0):
            t //= i
            att += [i]
    if t > 1:
        att += [t]
    return att


def lnum(m):
    return len(list(filter(lambda x: memo[x] >= m - 1, memo)))


memo = {}
for i in range(2, N + 1):
    fl = fac(i)
    for f in fl:
        if f in memo:
            memo[f] += 1
        else:
            memo[f] = 1
s = []
for m in memo:
    if memo[m] == 1:
        continue
    s += [memo[m] + 1]
ans = lnum(75) + lnum(25) * (lnum(3) - 1) + lnum(15) * (lnum(5) - 1) \
    + lnum(5) * (lnum(5) - 1) // 2 * (lnum(3) - 2)
print(ans)

Solution (Python):
import os, sys, re, math

N = int(input())

factor = {}

def doit(n):
    ret = {}
    for i in range(2,11):
        while n % i == 0:
            n = n // i
            ret[i] = ret.get(i,0) + 1

    if n != 1:
        ret[n] = ret.get(n,0) + 1
    return ret

for i in range(2,N+1):
    tmp = doit(i)
    for k,v in tmp.items():
        factor[k] = factor.get(k,0) + v

d3 = 0
d5 = 0
d15 = 0
d25 = 0
d75 = 0

for k,v in factor.items():
    if v >= 74:
        d75 += 1
    if v >= 24:
        d25 += 1
    if v >= 14:
        d15 += 1
    if v >= 4:
        d5 += 1
    if v >= 2:
        d3 += 1

print(d75+d25*(d3-1)+d15*(d5-1)+d5*(d5-1)*(d3-2)//2)

Solution (Python):
n = int(input())
p = {}
for i in range(2, n + 1):
    j = i
    for d in range(2, j + 1):
        while j % d == 0:
            p[d] = p.get(d, 0) + 1
            j //= d

def doit(ds, ps):
    if ds == []:
        return 1
    if ps == []:
        return 0
    ret = doit(ds, ps[1:])
    if ps[0] + 1 >= ds[0]:
        ret += doit(ds[1:], ps[1:])
    return ret

ret = 0
for ds in ([3, 5, 5], [5, 3, 5], [5, 5, 3], [5, 15], [15, 5], [3, 25], [25, 3], [75]):
    ret += doit(ds, list(p.values()))
print(ret)

Solution (Python):
n = int(input())
f = [0]*(n+1)
for i in range(2,n+1):
    a = i
    for j in range(2,i+1):
        while a % j == 0:
            f[j] += 1
            a //= j
def number(m):
    c = 0
    for i in range(n):
        if f[i] >= m - 1:
            c += 1
    return c
print(number(75) + number(25)*(number(3) - 1) + number(15)*(number(5) - 1) 
+ number(5)*(number(5) - 1)*(number(3) - 2)//2)

Solution (Python):
import math
N = int(input())
e = [0] * (N+1)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

import collections

for i in range(2,N+1):
  c = collections.Counter(prime_factorize(i))
  for key,value in c.items():
    e[key] += value


def num(m):
  return len(list(filter(lambda x: x >= m-1,e)))

print(num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1)
     + num(5) * (num(5) - 1) * (num(3) - 2) // 2)

Solution (Python):
def prime_factor(n):
    p = {}
    for i in range(2,n):
        if n % i == 0:
            p[i] = 0
        while n % i == 0:
            n //= i
            p[i] += 1
        if i * i > n: break
    if n != 1:
        p[n] = 1
    return p

N = int(input())
if N == 1:
    print(0)
else:
    
    pN = {}
    for i in range(2,N+1):
        p = prime_factor(i)
        for x in p:
            if x not in pN:
                pN[x] = p[x]
            else:
                pN[x] += p[x]
    
    
    res = 0
    for x in pN:
        for y in pN:
            for z in pN:
                if (x < y and y < z):
                    if(pN[x]>=2 and pN[y]>=4 and pN[z]>=4):
                        res+=1
                    if(pN[x]>=4 and pN[y]>=2 and pN[z]>=4):
                        res+=1
                    if(pN[x]>=4 and pN[y]>=4 and pN[z]>=2):
                        res+=1
    
    
    for x in pN:
        for y in pN:
            if x < y:
                if(pN[x]>=24 and pN[y]>= 2):
                    res+=1
                if(pN[x]>= 2 and pN[y]>=24):
                    res+=1
    
    
    for x in pN:
        for y in pN:
            if x < y:
                if(pN[x]>=14 and pN[y]>= 4):
                    res+=1
                if(pN[x]>= 4 and pN[y]>=14):
                    res+=1
    
    if pN[2] >= 74:
        res += 1
        
    print(res)

Solution (Python):

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


n = int(input())
d = {}
for i in range(1, n+1):
    for j in prime_factorize(i):
        if j not in d:
            d[j] = 1
        else:
            d[j] += 1
l = d.values()

ans = 0

 
a = 0
b = 0
for i in l:
    if 2 <= i <= 3:
        a += 1
for j in l:
    if 4 <= j:
        b += 1
ans += a*b*(b-1)/2


a = 0
b = 0
for i in l:
    if 4 <= i:
        a += 1
ans += a*(a-1)*(a-2)/2


a = 0
b = 0
for i in l:
    if 4 <= i <= 13:
        a += 1
for j in l:
    if 14 <= j:
        b += 1
ans += a*b


a = 0
b = 0
for i in l:
    if 14 <= i:
        a += 1
ans += a*(a-1)


a = 0
b = 0
for i in l:
    if 2 <= i <= 23:
        a += 1
for j in l:
    if 24 <= j:
        b += 1
ans += a*b


a = 0
b = 0
for i in l:
    if 24 <= i:
        a += 1
ans += a*(a-1)


a = 0
b = 0
for i in l:
    if 74 <= i:
        a += 1
ans += a

print(int(ans))

Solution (Python):
from collections import Counter

N = int(input())


def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


divisors = []
for i in range(2, N + 1):
    divisors.extend(prime_factorize(i))

e = Counter(divisors)
e_list = [e[i] for i in e.keys() if i != 1]


def num(x):
    return len([i for i in e_list if i >= x])


l2 = num(2)
l4 = num(4)
answer = num(74) + \
         num(24) * (l2 - 1) + \
         num(14) * (l4 - 1) + \
         l4 * (l4 - 1) * max(0, (l2 - 2)) // 2
print(answer)