BONUS - (Important Calculation)

#include <iostream>
#include <algorithm>
#include <numeric>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <climits>
#include <string>
#include <cstdio>
#include <cmath>
#define task "BONUS"
using namespace std;
const int mod =  111539768;
long long m, n, k, x, y, u, v;
void read()
{
   cin >> m >> n >> k >> x >> y >> u >> v;
}
long long power(long long a, long long b)
{
    if (b == 0)
    {
        return 1;
    }
    long long t = power(a, b/2);
    if (b % 2 == 0)
    {
        return (t * t)%mod;
    }
    else
    {
        return ((t * t) % mod * a) % mod;
    }
}
long long G(long long a, long long b) // 1 + a + a^1 + .. + a ^ b
{
    if (b == 0)
    {
        return 1;
    }
    if (b == 1)
    {
        return 1 + a;
    }
    if (b % 2 == 1)
    {
        return (1 + a * G(a, b - 1)) % mod;
    }
    if (b % 2 == 0)
    {
        return ( (1 + power(a, b/2)) * (G(a, b/2) - 1) + 1) % mod;
    }
}
long long F(long long a, long long b, long long c) // k ^ a + k^a + 1 +.. + k ^ b
{
    return (power(c, a) * G(c, b - a))%mod;
}
void solve()
{
   long long base1 = F((x - 1)*n + y - 1, (x - 1)*n + v - 1, k), base2 = power(k, n);
   cout << (base1 * G(base2, u - x)) % mod;
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   freopen(task".INP", "r", stdin);
   freopen(task".OUT", "w", stdout);
   read();
   solve();
}