using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 1e9;
int main(void)
{
    int a, b;
    cin >> a >> b;
    if (a < b)
        swap(a, b);
    vvi dp(a + 1, vi(b + 1, 0));
    for (int r = 1; r <= a; ++r)
    {
        for (int c = 1; c <= b; ++c)
        {
            if (r == c)
                continue;
            int &ans = dp[r][c] = INF;
            for (int k = 1; k < r; ++k)
                ans = min(ans, dp[k][c] + dp[r - k][c] + 1);
            for (int k = 1; k < c; ++k)
                ans = min(ans, dp[r][k] + dp[r][c - k] + 1);
        }
    }
    cout << dp[a][b] << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
vi prefix_function(string s)
{
    int n = s.size();
    vi pi(n, 0);
    for (int i = 1; i < n; ++i)
    {
        int j = pi[i - 1];
        while (j > 0 and s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            ++j;
        pi[i] = j;
    }
    return pi;
}
void solve(string s)
{
    int n = s.size();
    vi pi = prefix_function(s), ans;
    int j = n - 1;
    while (pi[j])
    {
        ans.push_back(n - pi[j]);
        j = pi[j] - 1;
    }
    ans.push_back(n);
    for_each(ans.begin(), ans.end(), [](int x) { cout << x << " "; }),
        cout << endl;
}
int main(void)
{
    string s;
    cin >> s;
    solve(s);
    return 0;
}

using namespace std;
using vi = vector<int>;
vi prefix_function(string s)
{
    int n = s.size();
    vi pi(n, 0);
    for (int i = 1; i < n; ++i)
    {
        int j = pi[i - 1];
        while (j > 0 and s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            ++j;
        pi[i] = j;
    }
    return pi;
}
void solve(string s)
{
    int i = s.size() - 1;
    vi pi = prefix_function(s), ans;
    while (pi[i])
    {
        ans.push_back(pi[i]);
        i = pi[i] - 1;
    }
    for_each(ans.rbegin(), ans.rend(), [](int x) { cout << x << " "; });
    cout << endl;
}
int main(void)
{
    string s;
    cin >> s;
    solve(s);
    return 0;
}

using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
const int CMAX = 26;
ll add(ll a, ll b) { return ((a % MOD) + (b % MOD)) % MOD; }
struct node
{
    bool end;
    vector<node *> children;
    node()
    {
        children.assign(CMAX, nullptr);
        end = false;
    }
};
struct trie
{
    node *root;
    trie() { root = new node(); }
    void insert(string s)
    {
        node *cur = root;
        int n = s.size();
        for (int i = n - 1; i >= 0; --i)
        {
            int j = s[i] - 'a';
            if (cur->children[j] == nullptr)
                cur->children[j] = new node();
            cur = cur->children[j];
        }
        cur->end = true;
    }
    ll query(int l, string s, const vector<ll> &dp)
    {
        ll ans = 0;
        node *cur = root;
        for (int i = l - 1; i >= 0; --i)
        {
            int j = s[i] - 'a';
            if (cur->children[j] == nullptr)
                break;
            cur = cur->children[j];
            if (cur->end)
                ans = add(ans, dp[i]);
        }
        return ans;
    }
};
ll solve(const string &s, const vector<string> &pattern)
{
    int n = s.size();
    vector<ll> dp(n + 1, 0);
    trie t;
    dp[0] = 1;
    for (auto p : pattern)
        t.insert(p);
    for (int l = 1; l <= n; ++l)
        dp[l] = t.query(l, s, dp);
    return dp[n];
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int k;
    string s;
    vector<string> patterns;
    cin >> s;
    cin >> k;
    patterns.resize(k);
    for (auto &pattern : patterns)
        cin >> pattern;
    cout << solve(s, patterns) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int const MOD = 1e9 + 7;
using mat = vector<vector<ll>>;
template <typename T, size_t N>
void multiply(T A[N][N], T B[N][N])
{
    T C[N][N] = {};
    for (int i = 0; i < int(N); i++)
    {
        for (int j = 0; j < int(N); j++)
        {
            for (int k = 0; k < int(N); k++)
            {
                C[i][j] += (A[i][k] * B[k][j]) % MOD;
                if (C[i][j] >= MOD)
                    C[i][j] -= MOD;
            }
        }
    }
    for (int i = 0; i < int(N); i++)
    {
        for (int j = 0; j < int(N); j++)
        {
            A[i][j] = C[i][j];
        }
    }
}
template <typename T, size_t N>
void power(T A[N][N], T base[N][N], long long k)
{
    if (k == 0)
        return;
    else
    {
        power(A, base, k >> 1);
        multiply<T, N>(A, A);
        if (k & 1)
        {
            multiply<T, N>(A, base);
        }
    }
}
template <typename T, size_t N>
void solve(T transition[N][N], T cur[N], ll k, T next[N])
{
    T r[N][N] = {};
    for (size_t i = 0; i < N; i++)
        r[i][i] = 1;
    power<T, N>(r, transition, k);
    for (size_t i = 0; i < N; i++)
    {
        next[i] = 0;
        for (size_t j = 0; j < N; j++)
        {
            next[i] += (r[i][j] * cur[j]) % MOD;
            if (next[i] >= MOD)
                next[i] -= MOD;
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    long long A[2][2] = {{1, 1}, {1, 0}};
    long long cur[2] = {0, 1}, next[2];
    long long k;
    cin >> k;
    solve(A, cur, k, next);
    cout << next[0] << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <long long M, typename T = long long>
class NumMod
{
    static_assert(std::is_integral<T>::value, "Integral required.");
    using NM = NumMod<M, T>;
    T x;
  public:
    static const ll MOD = M;
    NumMod(T x) : x(x) {}
    NumMod() : x(0) {}
    NumMod(NM const &y) : x(y.v()) {}
    explicit operator T() const { return x; }
    T v(void) const { return (this->x + M) % M; }
    NM & operator=(NM const &y)
    {
        this->x = y.v();
        return *this;
    }
    NM &operator=(T const &y) { return this->operator=(NM(y)); }
    NM &operator+=(NM const &y) { return this->operator=(operator+(y)); }
    NM &operator-=(NM const &y) { return this->operator=(operator-(y)); }
    NM &operator*=(NM const &y) { return this->operator=(operator*(y)); }
    NM operator+(NM const &y) const { return (v() + y.v()) % M; }
    NM operator+(T const &y) const { return this->operator+(NM(y)); }
    NM operator-(NM const &y) const { return (v() - y.v()) % M; }
    NM operator-(T const &y) const { return this->operator-(NM(y)); }
    NM operator*(NM const &y) const { return (v() * y.v()) % M; }
    NM operator*(T const &y) const { return this->operator*(NM(y)); }
    NM operator/(NM const &y) const { return this->operator*(inverse(y)); }
    NM inverse(NM const &y) const { return binpow(y, M - 2); }
};
int const NMAX = 2e6 + 11;
int const MOD = 1e9 + 7;
using NM = NumMod<MOD, ll>;
NM fact[NMAX];
void precompute_fact(void)
{
    fact[0] = 1;
    for (int i = 1; i < NMAX; ++i)
        fact[i] = fact[i - 1] * i;
}
template <typename T>
T binpow(T a, ll b)
{
    T res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a;
        a *= a;
        b >>= 1;
    }
    return res;
}
ll C(ll n, ll k)
{
    if (k > n)
        return 1;
    return ll(fact[n] / (fact[n - k] * fact[k]));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    ll n;
    cin >> n;
    vector<NM> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 0;
    for (int i = 2; i <= n; ++i)
        dp[i] = (dp[i - 1] + dp[i - 2]) * (i - 1);
    cout << ll(dp[n]) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <long long M, typename T = long long>
class NumMod
{
    static_assert(std::is_integral<T>::value, "Integral required.");
    T x;
  public:
    NumMod<M, T>(T x) : x(x) {}
    NumMod<M, T>() : x(0) {}
    NumMod<M, T>(NumMod<M, T> &n) : x(n.x) {}
    explicit operator T() const { return x; }
    T v(void) const { return (this->x + M) % M; }
    NumMod<M, T> &operator=(NumMod<M, T> const &y)
    {
        this->x = y.v();
        return *this;
    }
    NumMod<M, T> &operator=(T const &y)
    {
        return this->operator=(NumMod<M, T>(y));
    }
    NumMod<M, T> operator+(NumMod<M, T> y) const { return (v() + y.v()) % M; }
    NumMod<M, T> operator+(T y) const
    {
        return this->operator+(NumMod<M, T>(y));
    }
    NumMod<M, T> operator-(NumMod<M, T> y) const { return (v() - y.v()) % M; }
    NumMod<M, T> operator-(T y) const
    {
        return this->operator-(NumMod<M, T>(y));
    }
    NumMod<M, T> &operator+=(NumMod<M, T> y)
    {
        return this->operator=(operator+(y));
    }
    NumMod<M, T> operator*(NumMod<M, T> y) const { return (v() * y.v()) % M; }
    NumMod<M, T> operator*(T y) const
    {
        return this->operator*(NumMod<M, T>(y));
    }
    NumMod<M, T> &operator*=(NumMod<M, T> y)
    {
        return this->operator=(operator*(y));
    }
    NumMod<M, T> operator/(NumMod<M, T> y)
    {
        return this->operator*(inverse(y));
    }
    NumMod<M, T> inverse(NumMod<M, T> y) { return binpow(y, M - 2); }
};
int const NMAX = 2e6 + 11;
int const MOD = 1e9 + 7;
NumMod<MOD, ll> fact[NMAX];
void precompute_fact(void)
{
    fact[0] = 1;
    for (int i = 1; i < NMAX; ++i)
        fact[i] = fact[i - 1] * i;
}
template <typename T>
T binpow(T a, ll b)
{
    T res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a;
        a *= a;
        b >>= 1;
    }
    return res;
}
ll C(ll n, ll k)
{
    if (k > n)
        return 1;
    return ll(fact[n] / (fact[n - k] * fact[k]));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    precompute_fact();
    ll n, k;
    cin >> n >> k;
    cout << C(n + k - 1, k) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
template <long long M, typename T = long long>
class NumMod
{
    static_assert(std::is_integral<T>::value, "Integral required.");
    using NM = NumMod<M, T>;
    T x;
  public:
    static const ll MOD = M;
    NumMod(T x) : x(x) {}
    NumMod() : x(0) {}
    NumMod(NM const &y) : x(y.v()) {}
    explicit operator T() const { return x; }
    T v(void) const { return (this->x + M) % M; }
    NM & operator=(NM const &y)
    {
        this->x = y.v();
        return *this;
    }
    NM &operator=(T const &y) { return this->operator=(NM(y)); }
    NM &operator+=(NM const &y) { return this->operator=(operator+(y)); }
    NM &operator-=(NM const &y) { return this->operator=(operator-(y)); }
    NM &operator*=(NM const &y) { return this->operator=(operator*(y)); }
    NM operator+(NM const &y) const { return (v() + y.v()) % M; }
    NM operator+(T const &y) const { return this->operator+(NM(y)); }
    NM operator-(NM const &y) const { return (v() - y.v()) % M; }
    NM operator-(T const &y) const { return this->operator-(NM(y)); }
    NM operator*(NM const &y) const { return (v() * y.v()) % M; }
    NM operator*(T const &y) const { return this->operator*(NM(y)); }
    NM operator/(NM const &y) const { return this->operator*(inverse(y)); }
};
int const NMAX = 1e6 + 11;
int const MOD = 1e9 + 7;
using NM = NumMod<MOD, ll>;
NM fact[NMAX];
void precompute_fact(void)
{
    fact[0] = 1;
    for (int i = 1; i < NMAX; ++i)
        fact[i] = fact[i - 1] * i;
}
template <typename T>
T binpow(T a, ll b)
{
    T ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}
NM inverse(NM const &y) { return binpow(y, y.MOD - 2); }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    string s;
    vi freq(26, 0);
    cin >> s;
    for (char c : s)
        freq[c - 'a']++;
    precompute_fact();
    ll n = (int)s.size();
    vector<NM> rep(26);
    transform(freq.begin(), freq.end(), rep.begin(), [](auto cnt) { return fact[cnt]; });
    cout << ll(fact[n] / accumulate(rep.begin(), rep.end(), NM(1), multiplies<NM>())) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int const PMAX = 1e7;
bitset<PMAX> is_prime;
vector<int> primes;
using mii = map<int, int>;
mii prime_factors(ll n)
{
    mii factors;
    ll i = 0, pf = primes[i];
    while (pf * pf <= n)
    {
        while (n % pf == 0)
        {
            ++factors[pf];
            n = n / pf;
        }
        pf = primes[++i];
    }
    if (n != 1)
        ++factors[n];
    return factors;
}
void sieve(void)
{
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (ll i = 2; i < PMAX; i++)
        if (is_prime[i])
        {
            for (ll j = i * i; j < PMAX; j += i)
                is_prime[j] = 0;
            primes.push_back(i);
        }
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    sieve();
    for (int i = 0; i < n; ++i)
    {
        int ai;
        cin >> ai;
        auto factors = prime_factors(ai);
        ll ans = accumulate(factors.begin(), factors.end(), 1LL, [](ll acc, ii kv) {
            return acc * (kv.second + 1);
        });
        cout << ans << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const MOD = 1e9 + 7;
int phi(int n)
{
    int result = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}
ll modpow(ll a, ll b, ll mod)
{
    a %= mod;
    ll ans = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main(void)
{
    int t, PHI = phi(MOD);
    cin >> t;
    while (t--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        cout << modpow(a, modpow(b, c, PHI), MOD) << endl;
    }
    return 0;
}