#pragma region header #include // ソート, 二分探索, 最大・最小 #include // 固定長配列(C++11~) #include // ビット演算・フラグ管理 #include // デバッグ用の assert #include // 時間計測(C++11~) #include // int64_t, PRIu64 などのフォーマット指定 #include // INT_MAX, INT_MIN など #include // sqrt, pow, sin, cos など #include // FFT(高速フーリエ変換)など #include // printf, scanf(Cスタイル) #include // memset, memcpy #include // 両端キュー(deque) #include // 比較関数 (greater, less) #include // 小数点表示の調整(setprecision など) #include // 標準入出力 #include // イテレータ操作 #include // numeric_limits #include // std::map(連想配列) #include // gcd, lcm, accumulate など #include // 優先度付きキュー (priority_queue) #include // 乱数生成(乱択アルゴリズムなど) #include // std::set(集合) #include // 文字列ストリーム(stringstream) #include // スタック(LIFO) #include // 文字列操作 #include // tuple, tie #include // 型特性(C++11~) #include // ハッシュマップ(unordered_map) #include // ハッシュセット(unordered_set) #include // pair, swap, move など #include // 動的配列(最重要) using namespace std; struct Init{Init(){std::cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(20) << fixed;}}init; using ll = long long; using ull = unsigned long long; using ld = long double; #define all(x) begin((x)), end((x)) #define pb push_back #define mp make_pair #define mt make_tuple #define uq(v) v.erase(unique(begin(v), end(v)), end(v)) #define _overload4(_1,_2,_3,_4,name,...) name #define _overload3(_1,_2,_3,name,...) name #define _rep1(n) for(int i=0;i=0;i--) #define _rrep2(i,n) for(int i=(n)-1;i>=0;i--) #define _rrep3(i,a,b) for(int i=(b)-1;i>=(a);i--) #define _rrep4(i,a,b,c) for(int i=a+(b-a-1)/c*c;i>=a;i-=c) #define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__) template using pq = priority_queue; template using pq_g = priority_queue, greater>; template bool chmax(T &a, const T &b){if(a < b){a = b; return 1; } return 0;} template bool chmin(T &a, const T &b){if(a > b){a = b; return 1; } return 0;} template auto min(const T& a){ return *min_element(all(a)); } template auto max(const T& a){ return *max_element(all(a)); } constexpr ull INF = (1ULL << 61) + (1ULL << 30); constexpr int inf = (1 << 30); constexpr ld EPS = 1e-9; constexpr ld PI = std::acos(ld(-1)); constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[] = {0, 1 ,0, -1, 1, -1, 1, -1}; #pragma endregion header template struct MontgomeryModInt { private: using mint = MontgomeryModInt; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod_; for (i32 i = 0; i < 4; i++) ret *= 2 - mod_ * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod_) % mod_; static_assert(r * mod_ == 1, "invalid, r * mod != 1"); static_assert(mod_ < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod_ & 1) == 1, "invalid, mod % 2 == 0"); u32 x; public: MontgomeryModInt() : x{} {} MontgomeryModInt(const i64 &a): x(reduce(u64(fast ? a : (a % mod() + mod())) * n2)) {} static constexpr u32 reduce(const u64 &b) { return u32(b >> 32) + mod() - u32((u64(u32(b) * r) * mod()) >> 32); } mint &operator+=(const mint &p) { if (i32(x += p.x - 2 * mod()) < 0) x += 2 * mod(); return *this; } mint &operator-=(const mint &p) { if (i32(x -= p.x) < 0) x += 2 * mod(); return *this; } mint &operator*=(const mint &p) { x = reduce(u64(x) * p.x); return *this; } mint &operator/=(const mint &p) { *this *= p.inv(); return *this; } mint operator-() const { return mint() - *this; } mint operator+(const mint &p) const { return mint(*this) += p; } mint operator-(const mint &p) const { return mint(*this) -= p; } mint operator*(const mint &p) const { return mint(*this) *= p; } mint operator/(const mint &p) const { return mint(*this) /= p; } bool operator==(const mint &p) const { return (x >= mod() ? x - mod() : x) == (p.x >= mod() ? p.x - mod() : p.x); } bool operator!=(const mint &p) const { return (x >= mod() ? x - mod() : x) != (p.x >= mod() ? p.x - mod() : p.x); } u32 val() const { u32 ret = reduce(x); return ret >= mod() ? ret - mod() : ret; } mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } mint inv() const { return pow(mod() - 2); } friend ostream &operator<<(ostream &os, const mint &p) { return os << p.val(); } friend istream &operator>>(istream &is, mint &a) { i64 t; is >> t; a = mint(t); return is; } static constexpr u32 mod() { return mod_; } }; template using modint = MontgomeryModInt; using mint = modint<1000000007>; int main(){ int A, B, N; cin >> A >> B >> N; mint ans = 1; auto dfs = [&](auto self, int cur, int cnt) -> void { if(cnt == 0){ ans *= cur; return; } rep(i, A, B + 1) self(self, gcd(cur, i), cnt - 1); }; dfs(dfs, 0, N); cout << ans << "\n"; }