use std::io::{self, Read};

const MOD: i64 = 1_000_000_007;

// a^b mod m を計算する関数
fn mod_pow(mut a: i64, mut b: i64, m: i64) -> i64 {
    let mut res = 1i64;
    a %= m;
    while b > 0 {
        if b & 1 == 1 {
            res = res * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    res
}

fn main() {
    // 入力を読み込み
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();
    let a: i64 = it.next().unwrap().parse().unwrap();
    let b: i64 = it.next().unwrap().parse().unwrap();
    let n: i64 = it.next().unwrap().parse().unwrap();

    // X 配列
    let mut x = vec![0i64; (b + 1) as usize];

    for i in 2..=b {
        let ko = b / i - (a - 1) / i;
        x[i as usize] = mod_pow(ko, n, MOD);
    }

    for i in (1..=b).rev() {
        let mut score = 0i64;
        let mut j = i + i;
        while j <= b {
            score += x[j as usize];
            j += i;
        }
        x[i as usize] -= score;
        x[i as usize] = (x[i as usize] % MOD + MOD) % MOD; // 念のため正規化
    }

    let mut ans = 1i64;
    for i in 1..=b {
        if x[i as usize] != 0 {
            ans = ans * mod_pow(i as i64, x[i as usize], MOD) % MOD;
        }
    }

    println!("{}", ans);
}