output_description: Print the number of the Shichi-Go numbers that are divisors of N!.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: from collections import defaultdict
  from itertools import combinations
  
  
  # time complexity: O(√n)
  def prime_factorize(n, prime_factors=None):
      if prime_factors is None:
          prime_factors = defaultdict(int)
      i = 2
      while i * i <= n:
          if n % i == 0:
              while n % i == 0:
                  prime_factors[i] += 1
                  n //= i
          i += 1
      if n != 1:
          prime_factors[n] += 1
      return prime_factors
  
  
  N = int(input())
  prime_factors = defaultdict(int)
  for n in range(1, N + 1):
      prime_factors = prime_factorize(n, prime_factors)
  
  over_primes = defaultdict(list)
  for p, e in prime_factors.items():
      for threshold in (2, 4, 14, 24, 74):
          if e >= threshold:
              over_primes[threshold].append(p)
  num_shichigos = 0
  for p1 in over_primes[2]:
      # (2, 4, 4)
      for p2_1, p2_2 in combinations(over_primes[4], 2):
          if p1 != p2_1 and p1 != p2_2:
              num_shichigos += 1
      # (2, 24)
      for p3 in over_primes[24]:
          if p1 != p3:
              num_shichigos += 1
  for p1 in over_primes[4]:
      # (4, 14)
      for p2 in over_primes[14]:
          if p1 != p2:
              num_shichigos += 1
  # (74)
  num_shichigos += len(over_primes[74])
  print(num_shichigos)
  
problem_description: 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.
samples: [{"input": "9", "output": "0\n    \n\nThere are no Shichi-Go numbers among the divisors of 9! = 1 \\times 2 \\times\n... \\times 9 = 362880.\n\n* * *"}, {"input": "10", "output": "1\n    \n\nThere is one Shichi-Go number among the divisors of 10! = 3628800: 32400.\n\n* * *"}, {"input": "100", "output": "543"}]