def fft_suitable(N: int) -> bool:
    """Check whether `N` has only small prime factors. Return True if
    the prime factorization of `N` is suitable for efficient FFTs,
    that is contains only 2, 3, 5 and 7."""
    for p in [2, 3, 5, 7]:
        while N % p == 0:
            N //= p
    # All suitable prime factors taken out
    # --- a suitable N should be left with just 1
    return N == 1