a(n) = Sum_{k=1..n} gcd(k,n)^(k-1).

Terms

a(0) =1a(1) =3a(2) =11a(3) =68a(4) =629a(5) =7797a(6) =117655a(7) =2097254a(8) =43046979a(9) =1000000799a(10) =25937424611a(11) =743008402000