4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <functional>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: #include <cstring>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: typedef complex<double> CMP;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<typename T>
4fd800b3a8 2011-02-23        kinaba: struct DP4
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	int N1, N2, N3, N4;
4fd800b3a8 2011-02-23        kinaba: 	vector<T> data;
4fd800b3a8 2011-02-23        kinaba: 	DP4(int N1, int N2, int N3, int N4, const T& t = T())
4fd800b3a8 2011-02-23        kinaba: 		: N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(data.size()*sizeof(T)<(1<<26)); }
4fd800b3a8 2011-02-23        kinaba: 	T& operator()(int i1, int i2, int i3, int i4)
4fd800b3a8 2011-02-23        kinaba: 		{ return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
4fd800b3a8 2011-02-23        kinaba: 	void swap(DP4& rhs)
4fd800b3a8 2011-02-23        kinaba: 		{ data.swap(rhs.data); }
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: static const LL MODVAL = 1000000007;
4fd800b3a8 2011-02-23        kinaba: LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
4fd800b3a8 2011-02-23        kinaba: LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; }
4fd800b3a8 2011-02-23        kinaba: LL MUL(LL x, LL y) { return (x*y)%MODVAL; }
4fd800b3a8 2011-02-23        kinaba: LL POW(LL x, LL e) {
4fd800b3a8 2011-02-23        kinaba: 	LL v = 1;
4fd800b3a8 2011-02-23        kinaba: 	for(;e;x=MUL(x,x),e>>=1)
4fd800b3a8 2011-02-23        kinaba: 		if(e&1)
4fd800b3a8 2011-02-23        kinaba: 			v = MUL(v, x);
4fd800b3a8 2011-02-23        kinaba: 	return v;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: LL DIV(LL x, LL y) { return MUL(x, POW(y, MODVAL-2)); }
4fd800b3a8 2011-02-23        kinaba: LL C(LL n, LL k) {
4fd800b3a8 2011-02-23        kinaba: 	k = min(n, n-k);
4fd800b3a8 2011-02-23        kinaba: 	LL v = 1;
4fd800b3a8 2011-02-23        kinaba: 	for(LL i=1; i<=k; ++i)
4fd800b3a8 2011-02-23        kinaba: 		v = DIV(MUL(v, n-i+1), i);
4fd800b3a8 2011-02-23        kinaba: 	return v;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: LL FACT(LL n) {
4fd800b3a8 2011-02-23        kinaba: 	return n<=1 ? 1 : MUL(n, FACT(n-1));
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class TwoSidedCards { public:
4fd800b3a8 2011-02-23        kinaba: 	int theCount(vector <int> taro, vector <int> hanako)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int N = taro.size();
4fd800b3a8 2011-02-23        kinaba: 		vector<LL> loops;
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			vector<int> next(N);
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 				next[taro[i]-1] = hanako[i]-1;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			vector<bool> used(N);
4fd800b3a8 2011-02-23        kinaba: 			for(int s=0; s<N; ++s)
4fd800b3a8 2011-02-23        kinaba: 				if( !used[s] ) {
4fd800b3a8 2011-02-23        kinaba: 					used[s] = true;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 					LL looplen = 1;
4fd800b3a8 2011-02-23        kinaba: 					for(int v=next[s]; v!=s; v=next[v]) {
4fd800b3a8 2011-02-23        kinaba: 						used[v] = true;
4fd800b3a8 2011-02-23        kinaba: 						++looplen;
4fd800b3a8 2011-02-23        kinaba: 					}
4fd800b3a8 2011-02-23        kinaba: 					loops.push_back(looplen);
4fd800b3a8 2011-02-23        kinaba: 				}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		return (int)solve(N, loops);
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	LL solve(int N, const vector<LL>& loops)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		LL result = 1;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL rest = N;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<loops.size(); ++i) {
4fd800b3a8 2011-02-23        kinaba: 			result = MUL(result, MUL(singleloop(loops[i]), C(rest,loops[i])));
4fd800b3a8 2011-02-23        kinaba: 			rest -= loops[i];
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return result;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	map< pair< pair<int,int>,pair<int,int> >, LL > memo;
4fd800b3a8 2011-02-23        kinaba: 	LL num_downtrig(int first, int last, int i, int n, int c)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		if( i == n )
4fd800b3a8 2011-02-23        kinaba: 			return (last==1 && first==0 ? 1 : 0)==c ? 1 : 0;
4fd800b3a8 2011-02-23        kinaba: 		if( c < 0 )
4fd800b3a8 2011-02-23        kinaba: 			return 0;
4fd800b3a8 2011-02-23        kinaba: 		pair< pair<int,int>,pair<int,int> > key( make_pair(first,last), make_pair(i,c) );
4fd800b3a8 2011-02-23        kinaba: 		if( memo.count(key) )
4fd800b3a8 2011-02-23        kinaba: 			return memo[key];
4fd800b3a8 2011-02-23        kinaba: 		return memo[key] = ADD(
4fd800b3a8 2011-02-23        kinaba: 			num_downtrig(first, 0, i+1, n, c-(last==1)),
4fd800b3a8 2011-02-23        kinaba: 			num_downtrig(first, 1, i+1, n, c));
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	LL singleloop(int n)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		if( n == 1 )
4fd800b3a8 2011-02-23        kinaba: 			return 1;
4fd800b3a8 2011-02-23        kinaba: 		LL fn = FACT(n);
4fd800b3a8 2011-02-23        kinaba: 		LL result = 0;
4fd800b3a8 2011-02-23        kinaba: 		memo.clear();
4fd800b3a8 2011-02-23        kinaba: 		for(int c=0; c<n; ++c)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			LL z;
4fd800b3a8 2011-02-23        kinaba: 			if( c == 0 )
4fd800b3a8 2011-02-23        kinaba: 				z = num_downtrig(0, 0, 1, n, c);
4fd800b3a8 2011-02-23        kinaba: 			else
4fd800b3a8 2011-02-23        kinaba: 				z = ADD(
4fd800b3a8 2011-02-23        kinaba: 					num_downtrig(0, 0, 1, n, c),
4fd800b3a8 2011-02-23        kinaba: 					num_downtrig(1, 1, 1, n, c));
4fd800b3a8 2011-02-23        kinaba: 			result = ADD(result, DIV(MUL(z,fn), POW(2,c)));
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return result;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time; string timer()
4fd800b3a8 2011-02-23        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
4fd800b3a8 2011-02-23        kinaba:  { os << "{ ";
4fd800b3a8 2011-02-23        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
4fd800b3a8 2011-02-23        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
4fd800b3a8 2011-02-23        kinaba: void verify_case(const int& Expected, const int& Received) {
4fd800b3a8 2011-02-23        kinaba:  bool ok = (Expected == Received);
4fd800b3a8 2011-02-23        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
4fd800b3a8 2011-02-23        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
4fd800b3a8 2011-02-23        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
4fd800b3a8 2011-02-23        kinaba: #define END	 verify_case(_, TwoSidedCards().theCount(taro, hanako));}
4fd800b3a8 2011-02-23        kinaba: int main(){
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: CASE(0)
4fd800b3a8 2011-02-23        kinaba: 	int taro_[] = {1, 2, 3};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_));
4fd800b3a8 2011-02-23        kinaba: 	int hanako_[] = {1, 3, 2};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 12;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(1)
4fd800b3a8 2011-02-23        kinaba: 	int taro_[] = {1, 2, 3};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_));
4fd800b3a8 2011-02-23        kinaba: 	int hanako_[] = {1, 2, 3};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 6;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(2)
4fd800b3a8 2011-02-23        kinaba: 	int taro_[] = {1, 2};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_));
4fd800b3a8 2011-02-23        kinaba: 	int hanako_[] = {2, 1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 4;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(3)
4fd800b3a8 2011-02-23        kinaba: 	int taro_[] = {5, 8, 1, 2, 3, 4, 6, 7};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_));
4fd800b3a8 2011-02-23        kinaba: 	int hanako_[] = {1, 2, 3, 4, 5, 6, 7, 8};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 2177280;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(4)
4fd800b3a8 2011-02-23        kinaba: 	int taro_[] = {41, 22, 17, 36, 26, 15, 10, 23, 33, 48, 49, 9, 34, 6, 21, 2, 46, 16, 25, 3, 24, 13, 40, 37, 35,
4fd800b3a8 2011-02-23        kinaba: 50, 44, 42, 31, 12, 29, 7, 43, 18, 30, 19, 45, 32, 39, 14, 8, 27, 1, 5, 38, 11, 4, 20, 47, 28};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_));
4fd800b3a8 2011-02-23        kinaba: 	int hanako_[] = {19, 6, 23, 35, 17, 7, 50, 2, 33, 36, 12, 31, 46, 21, 30, 13, 47, 22, 44, 4, 25, 24, 3, 15, 20,
4fd800b3a8 2011-02-23        kinaba: 48, 10, 28, 26, 18, 5, 45, 49, 16, 40, 42, 43, 14, 1, 37, 29, 8, 41, 38, 9, 11, 34, 32, 39, 27};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 529165844;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(5)
4fd800b3a8 2011-02-23        kinaba: 	int taro_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
4fd800b3a8 2011-02-23        kinaba: 	31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_));
4fd800b3a8 2011-02-23        kinaba: 	int hanako_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
4fd800b3a8 2011-02-23        kinaba: 	31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = -1;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(6)
4fd800b3a8 2011-02-23        kinaba: int taro_[] = {1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_));
4fd800b3a8 2011-02-23        kinaba: 	  int hanako_[] = {1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 1;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(7)
4fd800b3a8 2011-02-23        kinaba: 	int taro_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
4fd800b3a8 2011-02-23        kinaba: 	31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_));
4fd800b3a8 2011-02-23        kinaba: 	int hanako_[] = {50,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
4fd800b3a8 2011-02-23        kinaba: 	31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_));
4fd800b3a8 2011-02-23        kinaba: 	int _ = 1;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE