7fcb6bef04 2014-01-06 kinaba: #include <iostream> 7fcb6bef04 2014-01-06 kinaba: #include <sstream> 7fcb6bef04 2014-01-06 kinaba: #include <iomanip> 7fcb6bef04 2014-01-06 kinaba: #include <vector> 7fcb6bef04 2014-01-06 kinaba: #include <string> 7fcb6bef04 2014-01-06 kinaba: #include <map> 7fcb6bef04 2014-01-06 kinaba: #include <set> 7fcb6bef04 2014-01-06 kinaba: #include <algorithm> 7fcb6bef04 2014-01-06 kinaba: #include <numeric> 7fcb6bef04 2014-01-06 kinaba: #include <iterator> 7fcb6bef04 2014-01-06 kinaba: #include <functional> 7fcb6bef04 2014-01-06 kinaba: #include <complex> 7fcb6bef04 2014-01-06 kinaba: #include <queue> 7fcb6bef04 2014-01-06 kinaba: #include <stack> 7fcb6bef04 2014-01-06 kinaba: #include <cmath> 7fcb6bef04 2014-01-06 kinaba: #include <cassert> 7fcb6bef04 2014-01-06 kinaba: #include <tuple> 7fcb6bef04 2014-01-06 kinaba: using namespace std; 7fcb6bef04 2014-01-06 kinaba: typedef long long LL; 7fcb6bef04 2014-01-06 kinaba: typedef complex<double> CMP; 7fcb6bef04 2014-01-06 kinaba: 7fcb6bef04 2014-01-06 kinaba: static const unsigned MODVAL = 1000000007; 7fcb6bef04 2014-01-06 kinaba: struct mint 7fcb6bef04 2014-01-06 kinaba: { 7fcb6bef04 2014-01-06 kinaba: unsigned val; 7fcb6bef04 2014-01-06 kinaba: mint():val(0){} 7fcb6bef04 2014-01-06 kinaba: mint(int x):val(x%MODVAL) {} 7fcb6bef04 2014-01-06 kinaba: mint(unsigned x):val(x%MODVAL) {} 7fcb6bef04 2014-01-06 kinaba: mint(LL x):val(x%MODVAL) {} 7fcb6bef04 2014-01-06 kinaba: }; 7fcb6bef04 2014-01-06 kinaba: mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 7fcb6bef04 2014-01-06 kinaba: mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 7fcb6bef04 2014-01-06 kinaba: mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 7fcb6bef04 2014-01-06 kinaba: mint operator+(mint x, mint y) { return x+=y; } 7fcb6bef04 2014-01-06 kinaba: mint operator-(mint x, mint y) { return x-=y; } 7fcb6bef04 2014-01-06 kinaba: mint operator*(mint x, mint y) { return x*=y; } 7fcb6bef04 2014-01-06 kinaba: 7fcb6bef04 2014-01-06 kinaba: template<typename T> 7fcb6bef04 2014-01-06 kinaba: struct DP3x 7fcb6bef04 2014-01-06 kinaba: { 7fcb6bef04 2014-01-06 kinaba: int N1, N2, N3; 7fcb6bef04 2014-01-06 kinaba: vector<T> data; 7fcb6bef04 2014-01-06 kinaba: DP3x(int, int N2, int N3, const T& t = T()) 7fcb6bef04 2014-01-06 kinaba: : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<28)); } 7fcb6bef04 2014-01-06 kinaba: T& operator()(int i1, int i2, int i3) 7fcb6bef04 2014-01-06 kinaba: { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; } 7fcb6bef04 2014-01-06 kinaba: void swap(DP3x& rhs) 7fcb6bef04 2014-01-06 kinaba: { data.swap(rhs.data); } 7fcb6bef04 2014-01-06 kinaba: }; 7fcb6bef04 2014-01-06 kinaba: 7fcb6bef04 2014-01-06 kinaba: class WinterAndSnowmen { public: 7fcb6bef04 2014-01-06 kinaba: int getNumber(int N, int M) 7fcb6bef04 2014-01-06 kinaba: { 7fcb6bef04 2014-01-06 kinaba: const int MAX = max(N,M); 7fcb6bef04 2014-01-06 kinaba: mint total; 7fcb6bef04 2014-01-06 kinaba: for(int B=10; B>=0; --B) 7fcb6bef04 2014-01-06 kinaba: { 7fcb6bef04 2014-01-06 kinaba: int HH = 2048>>(B+1); 7fcb6bef04 2014-01-06 kinaba: DP3x<mint> dp(MAX+1, HH, 4); 7fcb6bef04 2014-01-06 kinaba: dp(0,0,0) = 1; 7fcb6bef04 2014-01-06 kinaba: for(int k=1; k<=MAX; ++k) { 7fcb6bef04 2014-01-06 kinaba: for(int high=0; high<HH; ++high) 7fcb6bef04 2014-01-06 kinaba: for(int key=0; key<4; ++key) 7fcb6bef04 2014-01-06 kinaba: dp(k, high, key) = dp(k-1, high, key); 7fcb6bef04 2014-01-06 kinaba: 7fcb6bef04 2014-01-06 kinaba: for(int high=0; high<HH; ++high) 7fcb6bef04 2014-01-06 kinaba: for(int key=0; key<4; ++key) { 7fcb6bef04 2014-01-06 kinaba: int kh = k>>(B+1); 7fcb6bef04 2014-01-06 kinaba: int kk = (k>>B)&1; 7fcb6bef04 2014-01-06 kinaba: if(k<=N) 7fcb6bef04 2014-01-06 kinaba: dp(k, high^kh, key^(kk<<1)) += dp(k-1,high,key); 7fcb6bef04 2014-01-06 kinaba: if(k<=M) 7fcb6bef04 2014-01-06 kinaba: dp(k, high^kh, key^kk) += dp(k-1,high,key); 7fcb6bef04 2014-01-06 kinaba: } 7fcb6bef04 2014-01-06 kinaba: } 7fcb6bef04 2014-01-06 kinaba: total += dp(MAX, 0, 1); 7fcb6bef04 2014-01-06 kinaba: } 7fcb6bef04 2014-01-06 kinaba: return total.val; 7fcb6bef04 2014-01-06 kinaba: } 7fcb6bef04 2014-01-06 kinaba: }; 7fcb6bef04 2014-01-06 kinaba: 7fcb6bef04 2014-01-06 kinaba: // BEGIN CUT HERE 7fcb6bef04 2014-01-06 kinaba: #include <ctime> 7fcb6bef04 2014-01-06 kinaba: double start_time; string timer() 7fcb6bef04 2014-01-06 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 7fcb6bef04 2014-01-06 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 7fcb6bef04 2014-01-06 kinaba: { os << "{ "; 7fcb6bef04 2014-01-06 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 7fcb6bef04 2014-01-06 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 7fcb6bef04 2014-01-06 kinaba: void verify_case(const int& Expected, const int& Received) { 7fcb6bef04 2014-01-06 kinaba: bool ok = (Expected == Received); 7fcb6bef04 2014-01-06 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 7fcb6bef04 2014-01-06 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 7fcb6bef04 2014-01-06 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 7fcb6bef04 2014-01-06 kinaba: #define END verify_case(_, WinterAndSnowmen().getNumber(N, M));} 7fcb6bef04 2014-01-06 kinaba: int main(){ 7fcb6bef04 2014-01-06 kinaba: 7fcb6bef04 2014-01-06 kinaba: CASE(0) 7fcb6bef04 2014-01-06 kinaba: int N = 2; 7fcb6bef04 2014-01-06 kinaba: int M = 2; 7fcb6bef04 2014-01-06 kinaba: int _ = 4; 7fcb6bef04 2014-01-06 kinaba: END 7fcb6bef04 2014-01-06 kinaba: CASE(1) 7fcb6bef04 2014-01-06 kinaba: int N = 1; 7fcb6bef04 2014-01-06 kinaba: int M = 1; 7fcb6bef04 2014-01-06 kinaba: int _ = 1; 7fcb6bef04 2014-01-06 kinaba: END 7fcb6bef04 2014-01-06 kinaba: CASE(2) 7fcb6bef04 2014-01-06 kinaba: int N = 3; 7fcb6bef04 2014-01-06 kinaba: int M = 5; 7fcb6bef04 2014-01-06 kinaba: int _ = 74; 7fcb6bef04 2014-01-06 kinaba: END 7fcb6bef04 2014-01-06 kinaba: CASE(3) 7fcb6bef04 2014-01-06 kinaba: int N = 7; 7fcb6bef04 2014-01-06 kinaba: int M = 4; 7fcb6bef04 2014-01-06 kinaba: int _ = 216; 7fcb6bef04 2014-01-06 kinaba: END 7fcb6bef04 2014-01-06 kinaba: CASE(4) 7fcb6bef04 2014-01-06 kinaba: int N = 47; 7fcb6bef04 2014-01-06 kinaba: int M = 74; 7fcb6bef04 2014-01-06 kinaba: int _ = 962557390; 7fcb6bef04 2014-01-06 kinaba: END 7fcb6bef04 2014-01-06 kinaba: CASE(5) 7fcb6bef04 2014-01-06 kinaba: int N = 2000; 7fcb6bef04 2014-01-06 kinaba: int M = 2000; 7fcb6bef04 2014-01-06 kinaba: int _ = -1; 7fcb6bef04 2014-01-06 kinaba: END 7fcb6bef04 2014-01-06 kinaba: /* 7fcb6bef04 2014-01-06 kinaba: CASE(6) 7fcb6bef04 2014-01-06 kinaba: int N = ; 7fcb6bef04 2014-01-06 kinaba: int M = ; 7fcb6bef04 2014-01-06 kinaba: int _ = ; 7fcb6bef04 2014-01-06 kinaba: END 7fcb6bef04 2014-01-06 kinaba: */ 7fcb6bef04 2014-01-06 kinaba: } 7fcb6bef04 2014-01-06 kinaba: // END CUT HERE