257929a5e9 2013-01-21        kinaba: #include <iostream>
257929a5e9 2013-01-21        kinaba: #include <sstream>
257929a5e9 2013-01-21        kinaba: #include <iomanip>
257929a5e9 2013-01-21        kinaba: #include <vector>
257929a5e9 2013-01-21        kinaba: #include <string>
257929a5e9 2013-01-21        kinaba: #include <map>
257929a5e9 2013-01-21        kinaba: #include <set>
257929a5e9 2013-01-21        kinaba: #include <algorithm>
257929a5e9 2013-01-21        kinaba: #include <numeric>
257929a5e9 2013-01-21        kinaba: #include <iterator>
257929a5e9 2013-01-21        kinaba: #include <functional>
257929a5e9 2013-01-21        kinaba: #include <complex>
257929a5e9 2013-01-21        kinaba: #include <queue>
257929a5e9 2013-01-21        kinaba: #include <stack>
257929a5e9 2013-01-21        kinaba: #include <cmath>
257929a5e9 2013-01-21        kinaba: #include <cassert>
257929a5e9 2013-01-21        kinaba: using namespace std;
257929a5e9 2013-01-21        kinaba: typedef long long LL;
257929a5e9 2013-01-21        kinaba: typedef long double LD;
257929a5e9 2013-01-21        kinaba: typedef complex<LD> CMP;
257929a5e9 2013-01-21        kinaba: 
257929a5e9 2013-01-21        kinaba: static const unsigned MODVAL = 1000000007;
257929a5e9 2013-01-21        kinaba: struct mint
257929a5e9 2013-01-21        kinaba: {
257929a5e9 2013-01-21        kinaba: 	unsigned val;
257929a5e9 2013-01-21        kinaba: 	mint():val(0){}
257929a5e9 2013-01-21        kinaba: 	mint(int      x):val(x%MODVAL) {}
257929a5e9 2013-01-21        kinaba: 	mint(unsigned x):val(x%MODVAL) {}
257929a5e9 2013-01-21        kinaba: 	mint(LL       x):val(x%MODVAL) {}
257929a5e9 2013-01-21        kinaba: };
257929a5e9 2013-01-21        kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
257929a5e9 2013-01-21        kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
257929a5e9 2013-01-21        kinaba: mint operator+(mint x, mint y) { return x+=y; }
257929a5e9 2013-01-21        kinaba: mint operator*(mint x, mint y) { return x*=y; }
257929a5e9 2013-01-21        kinaba: 
257929a5e9 2013-01-21        kinaba: template<typename T>
257929a5e9 2013-01-21        kinaba: vector<T> MATMULxx(const vector<T>& a, const vector<T>& v)
257929a5e9 2013-01-21        kinaba: {
257929a5e9 2013-01-21        kinaba: 	int N = a.size();
257929a5e9 2013-01-21        kinaba: 	vector<T> u(N);
257929a5e9 2013-01-21        kinaba: 	for(int i=0; i<N; ++i)
257929a5e9 2013-01-21        kinaba: 	for(int j=0; j<N; ++j)
257929a5e9 2013-01-21        kinaba: 		u[i] += a[(j-i+N)%N]*v[j];
257929a5e9 2013-01-21        kinaba: 	return u;
257929a5e9 2013-01-21        kinaba: }
257929a5e9 2013-01-21        kinaba: 
257929a5e9 2013-01-21        kinaba: template<typename T>
257929a5e9 2013-01-21        kinaba: vector<T> MATMULxx(const vector<T>& a)
257929a5e9 2013-01-21        kinaba: {
257929a5e9 2013-01-21        kinaba: 	int N = a.size();
257929a5e9 2013-01-21        kinaba: 	vector<T> c(N);
257929a5e9 2013-01-21        kinaba: 	for(int j=0; j<N; ++j)
257929a5e9 2013-01-21        kinaba: 	for(int k=0; k<N; ++k)
257929a5e9 2013-01-21        kinaba: 		c[j] += a[k]*a[(j-k+N)%N];
257929a5e9 2013-01-21        kinaba: 	return c;
257929a5e9 2013-01-21        kinaba: }
257929a5e9 2013-01-21        kinaba: 
257929a5e9 2013-01-21        kinaba: template<typename T>
257929a5e9 2013-01-21        kinaba: vector<T> MATPOWMULxx(vector<T> a, LL e, vector<T> v)
257929a5e9 2013-01-21        kinaba: {
257929a5e9 2013-01-21        kinaba: 	for(; e; e>>=1, a=MATMULxx(a))
257929a5e9 2013-01-21        kinaba: 		if(e&1)
257929a5e9 2013-01-21        kinaba: 			v = MATMULxx(a, v);
257929a5e9 2013-01-21        kinaba: 	return v;
257929a5e9 2013-01-21        kinaba: }
257929a5e9 2013-01-21        kinaba: 
257929a5e9 2013-01-21        kinaba: class PenguinEmperor { public:
257929a5e9 2013-01-21        kinaba: 	int countJourneys(int N, long long daysPassed)
257929a5e9 2013-01-21        kinaba: 	{
257929a5e9 2013-01-21        kinaba: 		vector<mint> v(N), u(N);
257929a5e9 2013-01-21        kinaba: 		u[0] = 1;
257929a5e9 2013-01-21        kinaba: 		for(int i=0; i<N; ++i) {
257929a5e9 2013-01-21        kinaba: 			if(i == daysPassed % N)
257929a5e9 2013-01-21        kinaba: 				v = u;
257929a5e9 2013-01-21        kinaba: 			vector<mint> uu(N);
257929a5e9 2013-01-21        kinaba: 			for(int x=0; x<N; ++x) {
257929a5e9 2013-01-21        kinaba: 				int f = (x+i+1)%N;
257929a5e9 2013-01-21        kinaba: 				int b = (x-i-1+N)%N;
257929a5e9 2013-01-21        kinaba: 				uu[x] += u[f];
257929a5e9 2013-01-21        kinaba: 				if(f!=b)
257929a5e9 2013-01-21        kinaba: 					uu[x] += u[b];
257929a5e9 2013-01-21        kinaba: 			}
257929a5e9 2013-01-21        kinaba: 			u = uu;
257929a5e9 2013-01-21        kinaba: 		}
257929a5e9 2013-01-21        kinaba: 
257929a5e9 2013-01-21        kinaba: 		v = MATPOWMULxx(u, daysPassed/N, v);
257929a5e9 2013-01-21        kinaba: 		return v[0].val;
257929a5e9 2013-01-21        kinaba: 	}
257929a5e9 2013-01-21        kinaba: };
257929a5e9 2013-01-21        kinaba: 
257929a5e9 2013-01-21        kinaba: // BEGIN CUT HERE
257929a5e9 2013-01-21        kinaba: #include <ctime>
257929a5e9 2013-01-21        kinaba: double start_time; string timer()
257929a5e9 2013-01-21        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
257929a5e9 2013-01-21        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
257929a5e9 2013-01-21        kinaba:  { os << "{ ";
257929a5e9 2013-01-21        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
257929a5e9 2013-01-21        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
257929a5e9 2013-01-21        kinaba: void verify_case(const int& Expected, const int& Received) {
257929a5e9 2013-01-21        kinaba:  bool ok = (Expected == Received);
257929a5e9 2013-01-21        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
257929a5e9 2013-01-21        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
257929a5e9 2013-01-21        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
257929a5e9 2013-01-21        kinaba: #define END	 verify_case(_, PenguinEmperor().countJourneys(numCities, daysPassed));}
257929a5e9 2013-01-21        kinaba: int main(){
257929a5e9 2013-01-21        kinaba: 
257929a5e9 2013-01-21        kinaba: CASE(0)
257929a5e9 2013-01-21        kinaba: 	int numCities = 3;
257929a5e9 2013-01-21        kinaba: 	long long daysPassed = 2LL;
257929a5e9 2013-01-21        kinaba: 	int _ = 2;
257929a5e9 2013-01-21        kinaba: END
257929a5e9 2013-01-21        kinaba: CASE(1)
257929a5e9 2013-01-21        kinaba: 	int numCities = 4;
257929a5e9 2013-01-21        kinaba: 	long long daysPassed = 3LL;
257929a5e9 2013-01-21        kinaba: 	int _ = 2;
257929a5e9 2013-01-21        kinaba: END
257929a5e9 2013-01-21        kinaba: CASE(2)
257929a5e9 2013-01-21        kinaba: 	int numCities = 5;
257929a5e9 2013-01-21        kinaba: 	long long daysPassed = 36LL;
257929a5e9 2013-01-21        kinaba: 	int _ = 107374182;
257929a5e9 2013-01-21        kinaba: END
257929a5e9 2013-01-21        kinaba: CASE(3)
257929a5e9 2013-01-21        kinaba: 	int numCities = 300;
257929a5e9 2013-01-21        kinaba: 	long long daysPassed = 751LL;
257929a5e9 2013-01-21        kinaba: 	int _ = 413521250;
257929a5e9 2013-01-21        kinaba: END
257929a5e9 2013-01-21        kinaba: CASE(4)
257929a5e9 2013-01-21        kinaba: 	int numCities = 300;
257929a5e9 2013-01-21        kinaba: 	long long daysPassed = 750LL;
257929a5e9 2013-01-21        kinaba: 	int _ = 0;
257929a5e9 2013-01-21        kinaba: END
257929a5e9 2013-01-21        kinaba: CASE(5)
257929a5e9 2013-01-21        kinaba: 	int numCities = 350;
257929a5e9 2013-01-21        kinaba: 	long long daysPassed = 1000000000000000000LL;
257929a5e9 2013-01-21        kinaba: 	int _ = 667009739;
257929a5e9 2013-01-21        kinaba: END
257929a5e9 2013-01-21        kinaba: CASE(6)
257929a5e9 2013-01-21        kinaba: 	int numCities = 5;
257929a5e9 2013-01-21        kinaba: 	long long daysPassed = 7LL;
257929a5e9 2013-01-21        kinaba: 	int _ = 12;
257929a5e9 2013-01-21        kinaba: END
257929a5e9 2013-01-21        kinaba: /*
257929a5e9 2013-01-21        kinaba: CASE(7)
257929a5e9 2013-01-21        kinaba: 	int numCities = ;
257929a5e9 2013-01-21        kinaba: 	long long daysPassed = LL;
257929a5e9 2013-01-21        kinaba: 	int _ = ;
257929a5e9 2013-01-21        kinaba: END
257929a5e9 2013-01-21        kinaba: CASE(8)
257929a5e9 2013-01-21        kinaba: 	int numCities = ;
257929a5e9 2013-01-21        kinaba: 	long long daysPassed = LL;
257929a5e9 2013-01-21        kinaba: 	int _ = ;
257929a5e9 2013-01-21        kinaba: END
257929a5e9 2013-01-21        kinaba: */
257929a5e9 2013-01-21        kinaba: }
257929a5e9 2013-01-21        kinaba: // END CUT HERE