#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
typedef long long LL;
vector< vector<LL> > mMul( const vector< vector<LL> >& A, const vector< vector<LL> >& B )
{
const int n = A.size();
vector< vector<LL> > C(n, vector<LL>(n));
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j) {
LL Cij = 0;
for(int k=0; k<n; ++k)
Cij += A[i][k] * B[k][j];
C[i][j] = Cij % 1000003;
}
return C;
}
vector< vector<LL> > mPow( vector< vector<LL> > M, int t ) // t>0
{
vector< vector<LL> > R;
for(; t; t>>=1, M=mMul(M,M))
if( t&1 )
R = (R.empty() ? M : mMul(R,M));
return R;
}
class DrivingAround
{
public:
int numberOfWays(vector <string> adj, int start, int finish, int time)
{
int n = adj.size()*5;
vector< vector<LL> > M(n, vector<LL>(n));
for(int u=0; u<adj.size(); ++u)
for(int d=0; d<4; ++d)
M[u*5+d+1][u*5+d] = 1;
for(int u=0; u<adj.size(); ++u)
for(int v=0; v<adj.size(); ++v)
if( adj[u][v] != '.' )
M[u*5][v*5+adj[u][v]-'0'-1] = 1;
return int( mPow(M, time)[start*5][finish*5] );
}
// BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { string Arr0[] = {".12",
"2.1",
"12."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 2; int Arg3 = 5; int Arg4 = 8; verify_case(0, Arg4, numberOfWays(Arg0, Arg1, Arg2, Arg3)); }
void test_case_1() { string Arr0[] = {"....52....",
"..5.......",
"..........",
".......1..",
"......42.2",
"5...4.....",
".5...4...1",
"......5...",
".3244.....",
".........."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2; int Arg2 = 2; int Arg3 = 10; int Arg4 = 0; verify_case(1, Arg4, numberOfWays(Arg0, Arg1, Arg2, Arg3)); }
void test_case_2() { string Arr0[] = {"...14....1",
"......13..",
".2...4....",
"....52.5..",
"1.3..4....",
".3....35.5",
"4......1.1",
"..4.4.1.54",
"....4.11.5",
"31144.2.4."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 7; int Arg2 = 2; int Arg3 = 100; int Arg4 = 316984; verify_case(2, Arg4, numberOfWays(Arg0, Arg1, Arg2, Arg3)); }
void test_case_3() { string Arr0[] = {".555555555", "5.55555555", "55.5554555", "555.555555", "5555.55555", "55555.5555", "555555.555", "5555555.55", "55553555.5", "555555555."};
vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 7; int Arg3 = 1000000000; int Arg4 = 255218; verify_case(3, Arg4, numberOfWays(Arg0, Arg1, Arg2, Arg3)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main() { DrivingAround().run_test(-1); }
// END CUT HERE