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):
from collections import *

def factorize(n):
    fct = []
    
    for i in range(2, int(n**0.5)+1):
        c = 0
        
        while n%i==0:
            n //= i
            c += 1
            
        if c>0:
            fct.append((i, c))
    
    if n>1:
        fct.append((n, 1))
    
    return fct
    
N = int(input())
cnt = defaultdict(int)

for i in range(1, N+1):
    fct = factorize(i)
    
    for p, c in fct:
        cnt[p] += c

ov74, ov24, ov14, ov4, ov2 = 0, 0, 0, 0, 0

for v in cnt.values():
    if v>=74:
        ov74 += 1
    
    if v>=24:
        ov24 += 1
        
    if v>=14:
        ov14 += 1
    
    if v>=4:
        ov4 += 1
    
    if v>=2:
        ov2 += 1

ans = ov74+ov24*(ov2-1)+ov14*(ov4-1)+ov4*(ov4-1)//2*(ov2-2)
print(ans)

Solution (Python):
import collections

n = int(input())

div = []

for i in range(1,n+1):
    for j in range(2,int(n**0.5)+1):
        while i % j == 0:
            div.append(j)
            i //= j
    if i > 1:
        div.append(i)

c = collections.Counter(div)
    
n2,n4,n14,n24,n74 = 0,0,0,0,0

for k,v in c.items():
    if v >= 2:
        n2 += 1
    if v >= 4:
        n4 += 1
    if v >= 14:
        n14 += 1
    if v >= 24:
        n24 += 1
    if v >= 74:
        n74 += 1

ans = n74 + n24*(n2-1) + n14*(n4-1) + n4*(n4-1)*(n2-2)//2

print(ans)

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

def division(n):
    if n < 2:
        return []
    
    prime_factors = []
    
    for i in range(2,int(n**0.5)+1):
        while n % i == 0:
            prime_factors.append(i)
            n //= i
    if n > 1:
        prime_factors.append(n)
        
    return prime_factors

num = []

for i in range(1,n+1):
    div = division(i)
    num.extend(div)
c = collections.Counter(num)

div_num = 1

n2, n4, n14, n24, n74 = 0,0,0,0,0

for k,v in c.items():
    if 2<=v:
        n2 += 1
    if 4<=v:
        n4 += 1
    if 14<=v:
        n14 += 1
    if 24<=v:
        n24 += 1
    if 74<=v:
        n74 += 1

ans = n74 + n24*(n2-1) + n14*(n4-1) + n4*(n4-1)*(n2-2)//2

print(ans)

Solution (Python):
from collections import Counter
from copy import deepcopy

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 = [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]
dp = [[0] * 26 for _ in range(N)]
if N == 1:
    print(0)
else:
    for i in range(1,N):
        dp[i] = deepcopy(dp[i-1])
        temp = Counter(prime_factorize(i+1))
        for x in temp.items():
            if len(prime_factorize(x[0])) == 1:
                dp[i][prime.index(x[0])] += x[1]
        four = 0
        two = 0
        fourteen = 0
        twenty_four = 0
        seventy_four = 0
        for j in range(25):
            if dp[i][j] >= 74:
                seventy_four += 1
                twenty_four += 1
                fourteen += 1
                four += 1
                two += 1
            elif dp[i][j] >= 24:
                twenty_four += 1
                fourteen += 1
                four += 1
                two += 1
            elif dp[i][j] >= 14:
                fourteen += 1
                four += 1
                two += 1
            elif dp[i][j] >= 4:
                four += 1
                two += 1
            elif dp[i][j] >= 2:
                two += 1
        dp[i][25] = ((four*(four-1))//2) * (two-2) + twenty_four * (two-1) + fourteen * (four-1) + seventy_four
    print(dp[N-1][25])

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


def sieve(n):
    n += 1
    res = [i for i in range(n)]
    for p in range(2, int(n**.5)+1):
        if res[p] < p:
            continue
        for q in range(p**2, n, p):
            if res[q] == q:
                res[q] = p
    return res


U = 100
min_factor = sieve(U)


def prime_factor(n):
    res = defaultdict(int)
    while 1 < n:
        res[min_factor[n]] += 1
        n //= min_factor[n]
    return res


cnt = defaultdict(int)
for i in range(1, n+1):
    for k, v in prime_factor(i).items():
        cnt[k] += v

facts = cnt.keys()
ans = 0

for subset in combinations(facts, 3):
    for i in range(3):
        can_be = 1
        for j, prim in enumerate(subset):
            if i == j:
                if cnt[prim] < 2:
                    can_be = 0
                    break
            else:
                if cnt[prim] < 4:
                    can_be = 0
                    break
        if can_be:
            ans += 1


for subset in combinations(facts, 2):
    for i in range(2):
        can_be = 1
        for j, prim in enumerate(subset):
            if i == j:
                if cnt[prim] < 4:
                    can_be = 0
                    break
            else:
                if cnt[prim] < 14:
                    can_be = 0
                    break
        if can_be:
            ans += 1

        can_be2 = 1
        for j, prim in enumerate(subset):
            if i == j:
                if cnt[prim] < 2:
                    can_be2 = 0
                    break
            else:
                if cnt[prim] < 24:
                    can_be2 = 0
                    break
        if can_be2:
            ans += 1


if 74 <= cnt[2]:
    ans += 1

print(ans)

Solution (Python):
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


N = int(input())

prime_table = make_prime_table(N)
d = {}
for i in range(2, N + 1):
    for p, e in prime_factorize(i):
        d.setdefault(p, 0)
        d[p] += e





n74 = 0
n24 = 0
n14 = 0
n4 = 0
n2 = 0
for k in d:
    if d[k] >= 74:
        n74 += 1
    if d[k] >= 24:
        n24 += 1
    if d[k] >= 14:
        n14 += 1
    if d[k] >= 4:
        n4 += 1
    if d[k] >= 2:
        n2 += 1

result = 0

result += n4 * (n4 - 1) // 2 * (n2 - 2)

result += n14 * (n4 - 1)

result += n24 * (n2 - 1)

result += n74
print(result)

Solution (Python):
n = int(input())
l = [0]*101
i = 2
for i in range(2,n+1):
    j = 2
    while i >= 2:
        while i % j == 0:
            i = i//j
            l[j] += 1
        j += 1

ans = sum(x >= 74 for x in l)

a = sum(x >= 2 for x in l)
b = sum(x >= 24 for x in l)
ans += b*(a-1)

a = sum(x >= 4 for x in l)
b = sum(x >= 14 for x in l)
ans += b*(a-1)

a = sum(x >= 2 for x in l)
b = sum(x >= 4 for x in l)
ans += b*(b-1)*(a-2)//2

print(ans)

Solution (Python):
from collections import defaultdict
import math
def main():
    def factorization(num):
        nonlocal d
        if num in primes:
            d[num] += 1
            return
        for prime in primes:
            if num % prime == 0:
                count = 0
                while num % prime == 0:
                    count += 1
                    num //= prime
                d[prime] += count

    def generate_primes(num):
        if num == 1: return []
        primes = list(range(2, num + 1))
        i, p = 0, 1
        while p <= math.sqrt(num):
            if primes[i] != 0:
                p = primes[i]
                primes = [prime if (prime % p != 0 or prime == p) else 0 for prime in primes]
            i += 1
        return set(p for p in primes if p != 0)

    n = int(input())
    d = defaultdict(lambda :1)
    primes = generate_primes(100)
    for i in range(1, n + 1):
        factorization(i)
    c = [0] * 6
    for v in d.values():
        if v >= 3: c[0] += 1
        if v >= 75: c[5] -= 1
        elif v >= 25: c[4] -= 1
        elif v >= 15: c[3] -= 1
        elif v >= 5: c[2] -= 1
        elif v >= 3: c[1] -= 1
    s = 0
    for i in range(6):
        s += c[i]
        c[i] = s
    print(c[1] * (c[1] - 1) * (c[0] - 2) // 2 + c[3] * (c[0] - 1) + c[2] * (c[1] - 1) + c[4])
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
def factor(n, m=None):
    
    arr = {}
    temp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr
from collections import defaultdict
d = defaultdict(int)
for i in range(2, n+1):
    dd = factor(i)
    for k,v in dd.items():
        d[k] += dd[k]
n74 = sum(v>=74 for v in d.values())
n2 = sum(v>=2 for v in d.values())
n24 = sum(v>=24 for v in d.values())
n14 = sum(v>=14 for v in d.values())
n4 = sum(v>=4 for v in d.values())
ans = n74 + (n2-1)*n24 + (n4-1)*n14 + (n4*(n4-1)//2 * (n2-2) if n4>=1 else 0)
print(ans)

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):
import math
n = int(input())

div = [0]*101

for i in range(2,n+1):
    j=2
    t=i
    while i > 1 and j<=t:
        if i%j==0:
            div[j]+=1
            i//=j
        if i%j!=0:
            j+=1

n2=0
n4=0
n14=0
n24=0
n74=0

for i in range(n):
    if div[i]>=2:
        n2+=1
    if div[i]>=4:
        n4+=1
    if div[i]>=14:
        n14+=1
    if div[i]>=24:
        n24+=1
    if div[i]>=74:
        n74+=1

print(n24*(n2-1)+n14*(n4-1)+n4*(n4-1)//2*(n2-2)+n74)

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    d = defaultdict(int)
    
    def primes(n):
        if n == 1:
            return []
        else:
            tbl = [True]*(n+1)
            pri = [2]
            for i in range(2,n+1,2):
                tbl[i] = False
            k = 3
            while k <= n:
                if tbl[k]:
                    pri.append(k)
                    for i in range(k,n+1,k):
                        tbl[i] = False
                k += 2
            return pri
    p = primes(n)
    for i in range(2,n+1):
        ii = i
        for j in p:
            while True:
                if ii%j == 0:
                    d[j] += 1
                    ii //= j
                else:
                    break
            if ii == 1:
                break
    d2 = 0
    d4 = 0
    d14 = 0
    d24 = 0
    d74 = 0
    for i in d.values():
        if i >= 2:
            d2 += 1
            if i >= 4:
                d4 += 1
                if i >= 14:
                    d14 += 1
                    if i >= 24:
                        d24 += 1
                        if i >= 74:
                            d74 += 1

    print(d4*(d4-1)*(d2-2)//2+d14*(d4-1)+d24*(d2-1)+d74)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
P = 10**9+7
  
memo = [0]*(N+1)

for i in range(1,N+1):
  j = i
  while j % 2 == 0:
    memo[2] += 1
    j //= 2
  k = 3
  while k*k <= j:
    if j % k == 0:
      memo[k] += 1
      j //= k
    else:
      k += 2
  if j != 1:
    memo[j] += 1
  
rlt = 0
dic = {2:0, 4:0, 14:0, 24:0, 74:0}
for i in range(1, N+1):
  if memo[i] >= 74:
    dic[74] += 1
  if memo[i] >= 24:
    dic[24] += 1
  if memo[i] >= 14:
    dic[14] += 1
  if memo[i] >= 4:
    dic[4] += 1
  if memo[i] >=2:
    dic[2] += 1
    

rlt += dic[74]
rlt += dic[24]*(dic[2]-1)
rlt += dic[14]*(dic[4]-1)
rlt += dic[4]*(dic[4]-1)*(dic[2]-2)//2

print(rlt)

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

Solution (Python):
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


N = int(input())

prime = dict()
for i in range(2, N+1):
    prime_i = factorization(i)
    for p, num in prime_i:
        if p in prime:
            prime[p] += num
        else:
            prime[p] = num

divisor_75 = 0
divisor_25 = 0
divisor_15 = 0
divisor_5 = 0
divisor_3 = 0
for v in prime.values():
    if v >= 74:
        divisor_75 += 1
    if v >= 24:
        divisor_25 += 1
    if v >= 14:
        divisor_15 += 1
    if v >= 4:
        divisor_5 += 1
    if v >= 2:
        divisor_3 += 1

ans = 0
ans += divisor_75
ans = max(ans, ans + divisor_25 * (divisor_3 - 1))
ans = max(ans, ans + divisor_15 * (divisor_5 - 1))
ans = max(ans, ans + ((divisor_5 * (divisor_5 - 1)) // 2) * (divisor_3 - 2))

print(ans)

Solution (Python):
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


import collections
N = int(input())
c = collections.defaultdict(int)
for i in range(1, N + 1):
    factors = Prime().find_factors(i)
    for k, v in factors.items():
        c[k] += v
d = c.values()


n75 = sum(i >= 74 for i in d)
n25 = sum(i >= 24 for i in d)
n15 = sum(i >= 14 for i in d)
n5 = sum(i >= 4 for i in d)
n3 = sum(i >= 2 for i in d)

ans = n5 * (n5 - 1) * (n3 - 2) // 2
ans += n25 * (n3 - 1)
ans += n15 * (n5 - 1)
ans += n75
print(ans)

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

def sieve(N):
    p = 0
    prime = []
    is_prime = [1 for _ in range(N + 1)]
    is_prime[0], is_prime[1] = 0, 0
    for i in range(2, N + 1):
        if is_prime[i]:
            p += 1
            temp = i
            prime.append(i)
            while(temp <= N):
                is_prime[temp] = 0
                temp += i
            is_prime[i] = 1
    return p, prime

def fact_prime(n, p):
    ret = 0
    temp = p
    while(n >= p):
        ret += n // p
        p *= temp
    return ret

_, prime_list = sieve(N)
ans = 0

for a in prime_list:
    for b in prime_list:
        for c in prime_list:
            if a != b and b < c and a != c:
                if fact_prime(N, a) >= 2 and fact_prime(N, b) >= 4 and fact_prime(N, c) >= 4:
                    ans += 1
                    
for a in prime_list:
    for b in prime_list:
        if b != a:
            if fact_prime(N, a) >= 24 and fact_prime(N, b) >= 2:
                ans += 1
            if fact_prime(N, a) >= 4 and fact_prime(N, b) >= 14:
                ans += 1
                
for a in prime_list:
    if fact_prime(N, a) >= 74:
        ans += 1    

print(ans)

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def cal_divisors(N):
    divisors = []
    i = 1
    while i*i <= N:
        if N % i == 0:
            divisors.append(i)
            if i != N // i:
                divisors.append(N//i)
        i += 1
    divisors.sort()
    return divisors

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

def main():
    N = int(input())
    divisors = []
    for i in range(1,N+1):
        divisors.extend(prime_factorize(i))
    l = Counter(divisors)
    
    
    ans = 0
    nums = l.values()
    
    ans += len([*filter(lambda x: x >= 74, nums)])

    
    ans += len([*filter(lambda x: x >= 14, nums)]) * (len([*filter(lambda x: x >= 4, nums)])-1)

    
    ans += len([*filter(lambda x: x >= 24, nums)]) * (len([*filter(lambda x: x >= 2, nums)])-1)

    
    ans += len([*filter(lambda x: x >= 4, nums)]) * (len([*filter(lambda x: x >= 4, nums)])-1) * (len([*filter(lambda x: x >= 2, nums)])-2) // 2

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
import math

N = int(input())
D = defaultdict(int)

def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    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] = False
    return [i for i in range(n+1) if is_prime[i]]

def prime_cnt(p, n):
  cnt = 0
  temp = p
  while temp <= n:
    cnt += n//temp
    temp *= p
  return cnt

def conb(n, r):
  if n <= 0 or n < r:
    return 0
  elif r == 1:
    return n
  else:  
    return n * (n-1) // 2

for p in primes(N):
  D[p] += prime_cnt(p, N)

C = [0]*5
L = [3, 5, 15, 25, 75]

for i in D.values():
  for j in range(5):
    if i >= L[j] - 1:
      C[j] += 1

ans = 0
ans += conb(C[4], 1)
ans += conb(C[3], 1) * conb(C[0]-1, 1)
ans += conb(C[2], 1) * conb(C[1]-1, 1)
ans += conb(C[1], 2) * conb(C[0]-2, 1)

print(ans)

Solution (Python):

def soinsu_bunkai(m):
    pf={}

    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:
        pf[m]=1
    return pf



from collections import Counter
from collections import defaultdict
from itertools import permutations
import sys
input = sys.stdin.readline  
N = int(input())


c =defaultdict(int)
for i in range(1,N+1):
    x =soinsu_bunkai(i)
    for j,v in x.items():
        c[j] +=v


ans=set()
for p,q,r in permutations(c.keys(),3):
    if c[p] >=74:
        ans.add(p**74)
    if c[p] >=24 and c[q] >=2:
        ans.add((p**24)*(q**2))
    if c[p] >=14 and c[q] >=4:
        ans.add((p**14)*(q**4))
    if c[p] >=4 and c[q] >=4 and c[r] >=2:
        ans.add((p**4)*(q**4)*(r**2))
    
print(len(ans))

Solution (Python):
n = int(input())
def count_factors(n, factors):
    factors.setdefault(2, 0)
    while n%2 == 0:
        factors[2] += 1
        n //=2

    for f in range(3, int(n**0.5)+ 1, 2):
        factors.setdefault(f, 0)
        while n%f == 0:
            factors[f] += 1
            n //= f
    if n != 1:
        factors.setdefault(n, 0)
        factors[n] += 1


cf = {1: 1}
for i in range(1, n+1):
    count_factors(i, cf)


ans = 0
c25 = 0
c15 = 0
c5 = 0
c3 = 0
c2 = 0
for v in cf.values():
    if v >= 74:
        ans += 1
    if v >= 24:
        c25 += 1
    if v >= 14:
        c15 += 1
    if v >= 4:
        c5 += 1
    if v >= 2:
        c3 += 1
    if v >= 1:
        c2 += 1

ans += c25 *(c3 - 1)
ans += c15 *(c5 - 1)
ans += c5 * (c5-1) * (c3-2)//2
print(ans)

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

from collections import defaultdict
import itertools
def soinsu(n):
    arr = []
    now = n
    for i in range(2, int(n**0.5)+1):
        if now%i==0:
            cnt=0
            while now%i==0:
                cnt+=1
                now //= i
            arr.append([i, cnt])
    if now!=1:
        arr.append([now, 1])


    return arr

d = defaultdict(int)
for i in range(1,N+1):
    bunkai =soinsu(i)
    for b in bunkai:
        d[b[0]]+=b[1]

prime_list=[k for k in d.keys() if d[k]>=2]

N2 = sum(d[k]>=2 for k in d.keys())
N4 = sum(d[k]>=4 for k in d.keys())

N14 = sum(d[k]>=14 for k in d.keys())
N24 = sum(d[k]>=24 for k in d.keys())
N74 = sum(d[k]>=74 for k in d.keys())

pattern2_4_4 = N4*(N4-1)*(N2-2)//2
pattern2_24 = N24*(N2-1)
pattern4_14 = N14*(N4-1)
pattern74 = N74

print(pattern2_4_4 + pattern2_24 + pattern4_14+pattern74)

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):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(pow(n, 0.5)) + 1):
        if n % k == 0:
            return False
    return True


def resolve():
    n = int(input())
    primes = []
    for i in range(1, n + 1):
        if is_prime(i):
            primes.append(i)

    fact = []
    for prime in primes:
        ex = 0
        p = prime
        while n // p:
            ex += n // p
            p *= prime
        fact.append(ex)

    cnt_74 = cnt_24 = cnt_14 = cnt_4 = cnt_2 = 0
    for i in fact:
        if i >= 74:
            cnt_74 += 1
        if i >= 24:
            cnt_24 += 1
        if i >= 14:
            cnt_14 += 1
        if i >= 4:
            cnt_4 += 1
        if i >= 2:
            cnt_2 += 1

    res1 = max(0, cnt_24 * (cnt_2 - 1))
    res2 = (cnt_4 * (cnt_4 - 1)) // 2 * max(0, cnt_2 - 2)
    res3 = max(0, cnt_14 * (cnt_4 - 1))
    print(cnt_74 + res1 + res2 + res3)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

primes = [0]*100
def prime_factorize(n):
    while n % 2 == 0:
        primes[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            primes[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        primes[n] += 1

for i in range(1, N+1):
    prime_factorize(i)

up2 = 0
up4 = 0
up24 = 0
up14 = 0
up74 = 0
for i, p in enumerate(primes):
    if p>=2:
        up2 += 1
    if p>=4:
        up4 += 1
    if p>=24:
        up24 += 1
    if p>=14:
        up14 += 1
    if p>=74:
        up74 += 1

ans = 0
if up4>=2:
    ans += (up2-2)*(up4*(up4-1)//2)
if up24>=1:
    ans += (up2-1)*up24
if up14>=1:
    ans += (up4-1)*up14
if up74>=1:
    ans += up74

print(ans)

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

prime_factorization={}
for i in range(1,N+1):
	d=2
	orig=i
	while d< (int(orig**0.5)+1):
		while i%d==0:
			i=i//d
			if d in prime_factorization:
				prime_factorization[d]+=1
			else:
				prime_factorization[d]=1
		d+=1
	if i>1:
		if i in prime_factorization:
			prime_factorization[i]+=1
		else:
			prime_factorization[i]=1

greater2=0
greater4=0
greater14=0
greater24=0
greater74=0
for i in prime_factorization:
	if prime_factorization[i]>=2:
		greater2+=1
	if prime_factorization[i]>=4:
		greater4+=1
	if prime_factorization[i]>=14:
		greater14+=1
	if prime_factorization[i]>=24:
		greater24+=1
	if prime_factorization[i]>=74:
		greater74+=1
combi3=((greater4*(greater4-1))//2)*(greater2-2)
combi2=(greater14)*(greater4-1) + (greater24)*(greater2-1)
combi1=greater74
print(combi1+combi2+combi3)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def conb(n,r): 
    if n<r: return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def prime_factorize(n):
    if n == 1:
        return [1]
    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 = inp()
d = defaultdict(int)
for i in range(1,n+1):
    for x in prime_factorize(i):
        d[x] += 1

valist = d.values()
c = [2,4,14,24,74]
cnt = [0] * 5
for x in valist:
    if x >= 74: cnt[4] += 1
    elif x >= 24: cnt[3] += 1
    elif x >= 14: cnt[2] += 1
    elif x >= 4: cnt[1] += 1
    elif x >= 2: cnt[0] += 1

res = 0
a = sum(cnt[1:]); b = cnt[0]
res += conb(a,3)*3 + conb(a,2)*b
a = sum(cnt[2:]); b = cnt[1]
res += a*(a-1) + a*b
a = sum(cnt[3:]); b = sum(cnt[:3])
res += a*(a-1) + a*b
res += cnt[4]
print(res)

Solution (Python):
import itertools
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5) 
    data = [i + 1 for i in range(2, n, 2)] 
    while True:
        p = data[0]
        if limit < p: 
            return prime + data
        prime.append(p) 
        data = [e for e in data if e % p != 0] 

Sosu = get_sieve_of_eratosthenes(100)

N = int(input())
limit = 1
for i in range(N):
  limit *= i+1
ans = 0
A = [0]*len(Sosu)
for i in range(1,N+1):
  now = i*1
  for j in range(len(Sosu)):
    while now%Sosu[j] == 0:
      A[j] += 1
      now //= Sosu[j]
    if now == 1:
      break

ans = 0
for i in A:
  if i >= 74:
    ans +=1
T = list(itertools.permutations(A,2)) 
for L in T:
  first,second = L
  if first >= 4 and second >= 14:
    ans += 1
  if first >= 2 and second >= 24:
    ans += 1
T = list(itertools.permutations(A,3)) 

temp = 0
for L in T:
  first,second,third = L
  if first >= 2 and second >= 4 and third >= 4:
    temp += 1
temp = temp//2
ans += temp
print(ans)

Solution (Python):
from collections import Counter
from itertools import permutations

n=int(input())

def factorization(n):
    p=2
    fcr=[]
    while p*p<=n:
        while n%p==0:
            fcr.append(p)
            n//=p
        p+=1
    if n>1:
        fcr.append(n)
    return fcr


fcr_l=[]
for i in range(1,n+1):
  fcr=factorization(i)
  fcr_l+=fcr


c=Counter(fcr_l)
fcr_st=set(fcr_l)

ans=[]
for p,q,r in permutations(fcr_st,3):
  if c[p]>=74:
    ans.append(p**74)
  if c[p]>=24 and c[q]>=2:
    ans.append((p**24)*(q**2))
  if c[p]>=14 and c[q]>=4:
    ans.append((p**14)*(q**4))
  if c[p]>=4 and c[q]>=4 and c[r]>=2:
    ans.append((p**4)*(q**4)*(r**2))

print(len(set(ans)))