#!/usr/bin/perl
 
use bigint;
$b = 49;
$max = 50;
$v124 = $v12_ = $v1_4 = $v1__ = $v_24 = $v_2_ = $v__4 = [1];
 
for $n ( 1 .. $max ) {
	$v124 = &next($v124, $b, 1, 2, 4);
	$v12_ = &next($v12_, $b, 1, 2   );
	$v1_4 = &next($v1_4, $b, 1,    4);
	$v_24 = &next($v_24, $b,    2, 4);
	$v1__ = &next($v1__, $b, 1      );
	$v_2_ = &next($v_2_, $b,    2   );
	$v__4 = &next($v__4, $b,       4);
	printf "%d %s\n", $n, $v124->[0] - $v12_->[0] - $v1_4->[0] - $v_24->[0] + $v1__->[0] + $v_2_->[0] + $v__4->[0];
}
 
sub next {
	my($v, $b, @d) = @_;
	my(@r) = ();
	for $i ( 0 .. $#$v ) {
		my $w = $v->[$i];
		for $d ( @d ) { $r[($i * 10 + $d) % $b] += $w; }
	}
	\@r;
}
 

IyEvdXNyL2Jpbi9wZXJsCgp1c2UgYmlnaW50OwokYiA9IDQ5OwokbWF4ID0gNTA7CiR2MTI0ID0gJHYxMl8gPSAkdjFfNCA9ICR2MV9fID0gJHZfMjQgPSAkdl8yXyA9ICR2X180ID0gWzFdOwoKZm9yICRuICggMSAuLiAkbWF4ICkgewoJJHYxMjQgPSAmbmV4dCgkdjEyNCwgJGIsIDEsIDIsIDQpOwoJJHYxMl8gPSAmbmV4dCgkdjEyXywgJGIsIDEsIDIgICApOwoJJHYxXzQgPSAmbmV4dCgkdjFfNCwgJGIsIDEsICAgIDQpOwoJJHZfMjQgPSAmbmV4dCgkdl8yNCwgJGIsICAgIDIsIDQpOwoJJHYxX18gPSAmbmV4dCgkdjFfXywgJGIsIDEgICAgICApOwoJJHZfMl8gPSAmbmV4dCgkdl8yXywgJGIsICAgIDIgICApOwoJJHZfXzQgPSAmbmV4dCgkdl9fNCwgJGIsICAgICAgIDQpOwoJcHJpbnRmICIlZCAlc1xuIiwgJG4sICR2MTI0LT5bMF0gLSAkdjEyXy0+WzBdIC0gJHYxXzQtPlswXSAtICR2XzI0LT5bMF0gKyAkdjFfXy0+WzBdICsgJHZfMl8tPlswXSArICR2X180LT5bMF07Cn0KCnN1YiBuZXh0IHsKCW15KCR2LCAkYiwgQGQpID0gQF87CglteShAcikgPSAoKTsKCWZvciAkaSAoIDAgLi4gJCMkdiApIHsKCQlteSAkdyA9ICR2LT5bJGldOwoJCWZvciAkZCAoIEBkICkgeyAkclsoJGkgKiAxMCArICRkKSAlICRiXSArPSAkdzsgfQoJfQoJXEByOwp9Cg==