Given a directed multigraph $G=(V,E)$ , with $|V|=n$ nodes and $|E|=m$ edges, and an integer $z$, we are asked to assess whether the number #$ET$($G$) of node-distinct Eulerian trails of $G$ is at least $z$; two trails are called node-distinct if their node sequences are different. This problem has been formalized by Bernardini et al. [ALENEX 2020] as it is the core computational problem in several string processing applications. It can be solved in $O$($nω$) arithmetic operations by applying the well-known BEST theorem, where $ω<2.373$ denotes the matrix multiplication exponent. The algorithmic challenge is: Can we solve this problem faster for certain values of m and $z$? Namely, we want to design a combinatorial algorithm for assessing whether #$ET$($G$)≥$z$ , which does not resort to the BEST theorem and has a predictably bounded cost as a function of $m$ and $z$. We address this challenge here by providing a combinatorial algorithm requiring $O$($m⋅min${$z$,#$ET$($G$)}) time.