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