Complexity of counting paths in a graph Given a directed graph with n nodes such that each vertex has exactly two outgoing edges, and a natural number N encoded in binary, two vertices s and t, 

I want to count the number of (not necessarily simple) paths from s to t within N steps. 

Is this a #P-hard problem? Or generally, what's the complexity of this problem?
The output number of paths may be $\Omega(2^N/n)$ (choose $s$ arbitrarily and then choose $t$ as the vertex that is the endpoint of the largest number of the $2^N$ walks from $s$) which requires $\Omega(N)$ bits to write down explicitly; this is exponential in the input size. On the other hand, the matrix powering approach has complexity polynomial in the sum of the input and output sizes. So that seems to place it squarely in the class of counting problems that have exponential-sized output and may be solved deterministically in time polynomial in their output size, whatever the notation for that class is (it's some sort of counting analogue for EXP, and definitely not #EXP which is more analogous to NEXP).