2781d1e616 2016-07-09        kinaba: #include <iostream>
2781d1e616 2016-07-09        kinaba: #include <sstream>
2781d1e616 2016-07-09        kinaba: #include <iomanip>
2781d1e616 2016-07-09        kinaba: #include <vector>
2781d1e616 2016-07-09        kinaba: #include <string>
2781d1e616 2016-07-09        kinaba: #include <map>
2781d1e616 2016-07-09        kinaba: #include <set>
2781d1e616 2016-07-09        kinaba: #include <algorithm>
2781d1e616 2016-07-09        kinaba: #include <numeric>
2781d1e616 2016-07-09        kinaba: #include <iterator>
2781d1e616 2016-07-09        kinaba: #include <functional>
2781d1e616 2016-07-09        kinaba: #include <complex>
2781d1e616 2016-07-09        kinaba: #include <queue>
2781d1e616 2016-07-09        kinaba: #include <stack>
2781d1e616 2016-07-09        kinaba: #include <cmath>
2781d1e616 2016-07-09        kinaba: #include <cassert>
2781d1e616 2016-07-09        kinaba: #include <tuple>
2781d1e616 2016-07-09        kinaba: using namespace std;
2781d1e616 2016-07-09        kinaba: typedef long long LL;
2781d1e616 2016-07-09        kinaba: typedef complex<double> CMP;
2781d1e616 2016-07-09        kinaba: 
2781d1e616 2016-07-09        kinaba: int K;
2781d1e616 2016-07-09        kinaba: 
2781d1e616 2016-07-09        kinaba: static const unsigned MODVAL = 1000000007;
2781d1e616 2016-07-09        kinaba: struct mint
2781d1e616 2016-07-09        kinaba: {
2781d1e616 2016-07-09        kinaba: 	unsigned val;
2781d1e616 2016-07-09        kinaba: 	mint():val(0){}
2781d1e616 2016-07-09        kinaba: 	mint(int      x):val(x%MODVAL) {}
2781d1e616 2016-07-09        kinaba: 	mint(unsigned x):val(x%MODVAL) {}
2781d1e616 2016-07-09        kinaba: 	mint(LL       x):val(x%MODVAL) {}
2781d1e616 2016-07-09        kinaba: };
2781d1e616 2016-07-09        kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
2781d1e616 2016-07-09        kinaba: mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
2781d1e616 2016-07-09        kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
2781d1e616 2016-07-09        kinaba: mint operator+(mint x, mint y) { return x+=y; }
2781d1e616 2016-07-09        kinaba: mint operator-(mint x, mint y) { return x-=y; }
2781d1e616 2016-07-09        kinaba: mint operator*(mint x, mint y) { return x*=y; }
2781d1e616 2016-07-09        kinaba: 
2781d1e616 2016-07-09        kinaba: mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
2781d1e616 2016-07-09        kinaba: mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
2781d1e616 2016-07-09        kinaba: mint operator/(mint x, mint y) { return x/=y; }
2781d1e616 2016-07-09        kinaba: 
2781d1e616 2016-07-09        kinaba: vector<mint> solve(int N, vector<mint> q)
2781d1e616 2016-07-09        kinaba: {
2781d1e616 2016-07-09        kinaba: 	if(N == 1)
2781d1e616 2016-07-09        kinaba: 		return vector<mint>(1, mint(1));
2781d1e616 2016-07-09        kinaba: 
2781d1e616 2016-07-09        kinaba: 	vector<mint> p(N);
2781d1e616 2016-07-09        kinaba: 	for(int s=0; s<N; ++s) {
2781d1e616 2016-07-09        kinaba: 		int d = ((N+1-K)%N+N)%N;
2781d1e616 2016-07-09        kinaba: 		if(s == d) {
2781d1e616 2016-07-09        kinaba: 			p[s] = 2 * (d<N-1 ? q[d]/2 : mint(0));
2781d1e616 2016-07-09        kinaba: 			break;
2781d1e616 2016-07-09        kinaba: 		}
2781d1e616 2016-07-09        kinaba: 	}
2781d1e616 2016-07-09        kinaba: 	for(int s=0; s<N; ++s) {
2781d1e616 2016-07-09        kinaba: 		int d = ((N+1-K)%N+N)%N;
2781d1e616 2016-07-09        kinaba: 		if(s != d) {
2781d1e616 2016-07-09        kinaba: 			p[s] = p[d]/2 + (d<N-1 ? q[d]/2 : mint(0));
2781d1e616 2016-07-09        kinaba: 		}
2781d1e616 2016-07-09        kinaba: 	}
2781d1e616 2016-07-09        kinaba: 	return p;
2781d1e616 2016-07-09        kinaba: }
2781d1e616 2016-07-09        kinaba: 
2781d1e616 2016-07-09        kinaba: class BearCircleGame { public:
2781d1e616 2016-07-09        kinaba: 	int winProbability(int n, int k)
2781d1e616 2016-07-09        kinaba: 	{
2781d1e616 2016-07-09        kinaba: 		K = k;
2781d1e616 2016-07-09        kinaba: 		vector<mint> p;
2781d1e616 2016-07-09        kinaba: 		for(int nn=1; nn<=n; ++nn)
2781d1e616 2016-07-09        kinaba: 			p = solve(nn, p);
2781d1e616 2016-07-09        kinaba: 		return p[0].val;
2781d1e616 2016-07-09        kinaba: 	}
2781d1e616 2016-07-09        kinaba: };
2781d1e616 2016-07-09        kinaba: 
2781d1e616 2016-07-09        kinaba: // BEGIN CUT HERE
2781d1e616 2016-07-09        kinaba: #include <ctime>
2781d1e616 2016-07-09        kinaba: double start_time; string timer()
2781d1e616 2016-07-09        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
2781d1e616 2016-07-09        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
2781d1e616 2016-07-09        kinaba:  { os << "{ ";
2781d1e616 2016-07-09        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
2781d1e616 2016-07-09        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
2781d1e616 2016-07-09        kinaba: void verify_case(const int& Expected, const int& Received) {
2781d1e616 2016-07-09        kinaba:  bool ok = (Expected == Received);
2781d1e616 2016-07-09        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
2781d1e616 2016-07-09        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
2781d1e616 2016-07-09        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
2781d1e616 2016-07-09        kinaba: #define END	 verify_case(_, BearCircleGame().winProbability(n, k));}
2781d1e616 2016-07-09        kinaba: int main(){
2781d1e616 2016-07-09        kinaba: 
2781d1e616 2016-07-09        kinaba: CASE(0)
2781d1e616 2016-07-09        kinaba: 	int n = 2;
2781d1e616 2016-07-09        kinaba: 	int k = 1;
2781d1e616 2016-07-09        kinaba: 	int _ = 333333336;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: CASE(1)
2781d1e616 2016-07-09        kinaba: 	int n = 2;
2781d1e616 2016-07-09        kinaba: 	int k = 2;
2781d1e616 2016-07-09        kinaba: 	int _ = 1;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: CASE(2)
2781d1e616 2016-07-09        kinaba: 	int n = 3;
2781d1e616 2016-07-09        kinaba: 	int k = 2;
2781d1e616 2016-07-09        kinaba: 	int _ = 142857144;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: CASE(3)
2781d1e616 2016-07-09        kinaba: 	int n = 3;
2781d1e616 2016-07-09        kinaba: 	int k = 1;
2781d1e616 2016-07-09        kinaba: 	int _ = 238095240;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: CASE(4)
2781d1e616 2016-07-09        kinaba: 	int n = 4;
2781d1e616 2016-07-09        kinaba: 	int k = 4;
2781d1e616 2016-07-09        kinaba: 	int _ = 142857144;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: CASE(5)
2781d1e616 2016-07-09        kinaba: 	int n = 5;
2781d1e616 2016-07-09        kinaba: 	int k = 1000000000;
2781d1e616 2016-07-09        kinaba: 	int _ = 142857144;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: CASE(6)
2781d1e616 2016-07-09        kinaba: 	int n = 2000;
2781d1e616 2016-07-09        kinaba: 	int k = 123;
2781d1e616 2016-07-09        kinaba: 	int _ = 429232785;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: CASE(7)
2781d1e616 2016-07-09        kinaba: 	int n = 1987;
2781d1e616 2016-07-09        kinaba: 	int k = 987654321;
2781d1e616 2016-07-09        kinaba: 	int _ = 623410299;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: /*
2781d1e616 2016-07-09        kinaba: CASE(8)
2781d1e616 2016-07-09        kinaba: 	int n = ;
2781d1e616 2016-07-09        kinaba: 	int k = ;
2781d1e616 2016-07-09        kinaba: 	int _ = ;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: CASE(9)
2781d1e616 2016-07-09        kinaba: 	int n = ;
2781d1e616 2016-07-09        kinaba: 	int k = ;
2781d1e616 2016-07-09        kinaba: 	int _ = ;
2781d1e616 2016-07-09        kinaba: END
2781d1e616 2016-07-09        kinaba: */
2781d1e616 2016-07-09        kinaba: }
2781d1e616 2016-07-09        kinaba: // END CUT HERE