import sys MOD = 10**9 + 7 MOD_EXP = MOD - 1 def main(): A, B, N = map(int, sys.stdin.readline().split()) max_d = B f = [0] * (max_d + 1) # Precompute mobius function using sieve max_k = B mobius = [1] * (max_k + 1) is_prime = [True] * (max_k + 1) for p in range(2, max_k + 1): if is_prime[p]: for multiple in range(p, max_k + 1, p): is_prime[multiple] = False if multiple != p else is_prime[multiple] mobius[multiple] *= -1 p_square = p * p for multiple in range(p_square, max_k + 1, p_square): mobius[multiple] = 0 result = 1 for d in range(1, max_d + 1): current_sum = 0 k_max = B // d if k_max == 0: continue for k in range(1, k_max + 1): mu = mobius[k] if mu == 0: continue m = (B // (d * k)) - ((A - 1) // (d * k)) if m < 0: m = 0 term = mu * pow(m, N, MOD_EXP) current_sum += term if current_sum >= MOD_EXP or current_sum <= -MOD_EXP: current_sum %= MOD_EXP exponent = current_sum % MOD_EXP result = (result * pow(d, exponent, MOD)) % MOD print(result) if __name__ == "__main__": main()