//#include "pch.h"
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("2sah.in");
ofstream fout("2sah.out");

static const int MOD = 100003;

long long solveOne(long long base, long long exp)
{
	long long ans = 1;
	
	while (exp)
	{
		if (exp % 2)
		{
			ans = (ans*base) % MOD;
			exp--;
		}
		else
		{
			base = (base*base) % MOD;
			exp /= 2;
		}
	}

	return ans;
}

void getMatrix(long long a[3][3], long long b[3][3])
{
	long long aux[3][3];

	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
			for (int k = 0; k < 3; ++k)
				aux[i][j] = 1LL * (aux[i][j] + (a[i][k] * b[k][j]))%MOD;

	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
			a[i][j] = aux[i][j];
}

 long long solveTwo(long long n, long long exp)
{
	long long ans[3][3];
	ans[0][0] = 0;
	for (int j = 1; j < 3; ++j) ans[j][0] = ans[j-1][0] + 1;

	long long base[3][3];
	base[0][0] = base[0][2] = base[1][0] = base[1][1] = 0;
	base[0][1] = base[1][2] = base[2][0] = base[2][1] = base[2][2] = 1;

	while (exp)
	{
		if (exp % 2)
		{
			getMatrix(base, ans);
			exp--;
		}
		else
		{
			getMatrix(base, base);
			exp /= 2;
		}
	}

	/*for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
			cout << ans[i][j] << " ";
		cout << '\n';
	}*/

	return ans[2][0];
}

int main()
{
	ios::sync_with_stdio(false);
	fin.tie(0); fout.tie(0);

	long long n, k;
	int type;

	fin >> type;
	fin >> n >> k;
	
	if (type == 1) fout<<solveOne(3, k-1)<<'\n';
	else fout<<solveTwo(n, n-k+2);
}