/* http://projecteuler.net/
 *
 * Problem 97
 * Find the last ten digits of 28433*2^7830457+1.
 *
 * Solution by Melkor (Filip Niksic, fniksic@gmail.com)
 *
 **/

#include <iostream>

using namespace std;

int main() {
    int exp = 7830457, p = 0;
    long long result = 1ll;

    // calculate 2^7830457 mod 10000000000
    while (exp >> p)
	++p;
    while (p > 0) {
	--p;
	//result *= result;
	// 64 bits are not enough to square a 10-digit number directly
	// so I have to split it into two 5-digit numbers:
	//   n = 100000*a + b
	// Now I have
	//   n^2 = 10000000000*a^2 + 200000*a*b + b*b
	// I can simply erase the first term.
	long long a = result / 100000ll, b = result % 100000ll;
	result = 200000ll * a * b + b * b;
	if (exp & 1<<p)
	    result *= 2ll;
	result %= 10000000000ll;
    }

    // calculate the rest
    result *= 28433ll;
    result += 1ll;
    result %= 10000000000ll;

    cout << result << endl;

    return 0;
}