#include <bits/stdc++.h>
using namespace std;
namespace lgh {
#define int long long

struct Bignum {
	#undef int
	int len, x[3010];
	Bignum& operator= (int b) {
		memset(x, 0, sizeof(x)); len = 0;
		do x[++len] = b % 10;
		while(b /= 10);
		return *this;
	}
	Bignum& operator= (const Bignum& b) {
		*this = 0; len = b.len;
		for(int i = 1; i <= len; ++i)
			x[i] = b.x[i];
		return *this;
	}
	Bignum() { *this = 0; }
	void read() {
		*this = 0; len = 0;
		static int c = 0;
		do ; while(c = getchar(), c < 48 || c > 57);
		do x[++len] = c ^ 48; while(c = getchar(), c >= 48 && c <= 57);
		reverse(x + 1, x + len + 1);
	}
	void write() {
		for(int i = len; i >= 1; --i) 
			printf("%d", x[i]);
	}
	Bignum& fix() {
		for(int i = 1; i <= len; ++i) {
			if(x[i] < 0) {
				x[i] += 10;
				x[i + 1]--;
			}
		}
		for(int i = 1; i < len; ++i) {
			x[i + 1] += x[i] / 10;
			x[i] %= 10;
		}
		while(x[len] > 9) {
			x[len + 1] += x[len] / 10;
			x[len] %= 10;
			len++;
		}
		while(x[len] == 0 && len > 1) len--;
		return *this;
	}
	Bignum operator+ (const int& b) const {
		static Bignum c; c = *this;
		c.x[1] += b;
		return c.fix();
	}
	Bignum operator+ (const Bignum& b) const {
		static Bignum c; c = 0;
		c.len = max(len, b.len);
		for(int i = 1; i <= c.len; ++i) 
			c.x[i] = x[i] + b.x[i];
		return c.fix();
	}
	Bignum operator* (const Bignum& b) const {
		static Bignum c; c = 0;
		c.len = len + b.len - 1;
		for(int i = 1; i <= len; ++i)
			for(int j = 1; j <= b.len; ++j)
				c.x[i + j - 1] += x[i] * b.x[j];
		return c.fix();
	}
	Bignum operator/ (const int& b) const {
		static Bignum c; c = 0;
		c.len = len;
		static long long r; r = 0;
		for(int i = len; i >= 1; --i) {
			r = r * 10 + x[i];
			c.x[i] = r / b;
			r %= b;
		}
		return c.fix();
	}
	long long operator% (const int& b) const {
		static Bignum c; c = 0;
		c.len = len;
		static long long r; r = 0;
		for(int i = len; i >= 1; --i) {
			r = r * 10 + x[i];
			c.x[i] = r / b;
			r %= b;
		}
		return r;
	}
	bool operator>= (const Bignum& b) const {
		if(len > b.len) return 1;
		if(len < b.len) return 0;
		for(int i = len; i >= 1; --i) {
			if(x[i] > b.x[i]) return 1;
			if(x[i] < b.x[i]) return 0;
		}
		return 1;
	}
	bool operator< (const Bignum& b) const {
		if(len > b.len) return 0;
		if(len < b.len) return 1;
		for(int i = len; i >= 1; --i) {
			if(x[i] > b.x[i]) return 0;
			if(x[i] < b.x[i]) return 1;
		}
		return 0;
	}
} n, t, m;

Bignum C(const Bignum& a, const int& b) {
	static Bignum c; c = 1;
	Bignum tmp; tmp = a + -b + 1;
	for(Bignum i = a; i >= tmp; i = i + -1)
		c = c * i;
	static int d; d = 1;
	for(int i = b; i >= 1; --i)
		d = d * i;
	return c / d;
}

Bignum pow(const Bignum& a, const int& b) {
	static Bignum c; c = 1;
	for(int i = 1; i <= b; ++i) 
		c = c * a;
	return c;
}

int a[3389];

map<Bignum, Bignum> b;

signed main() {
	// Bignum a; a.read();
	// int b; cin >> b;
	// Bignum c; c = a % b;
	// c.write();

	a[0] = 1;
	for(int i = 1; i < 3389; ++i)
		a[i] = (1234 * a[i - 1] + 5678) % 3389;
	n.read(); t.read(); m.read();
	
	// b[n - 0] = a[n - 0];
	// b[n - 1] = a[n - 1] + b[n - 0] * C(n - 0, 1) * pow(t, 1);
	// b[n - 2] = a[n - 2] + b[n - 1] * C(n - 1, 1) * pow(t, 1) + b[n - 0] * C(n - 0, 2) * pow(t, 2);
	// b[n - 3] = a[n - 3] + b[n - 2] * C(n - 2, 1) * pow(t, 1) + b[n - 1] * C(n - 1, 2) * pow(t, 2) - b[n - 0] * C(n - 0, 3) * pow(t, 3);
	// ...

	for(Bignum i = n; i >= m; i = i + -1) {
		b[i] = a[i % 3388];
		int cnt = 0;
		static Bignum tmp; tmp = n + 1;
		for(Bignum j = i + 1; j < tmp; j = j + 1) {
			cnt++;
			b[i] = b[i] + b[j] * C(j, cnt) * pow(t, cnt);
		}
	}
	
	b[m].write();
	return 0;
}
}
signed main() {
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);
	return lgh::main();
}