  We give the first efficient algorithm to approximately count the number of
solutions in the random $k$-SAT model when the density of the formula scales
exponentially with $k$. The best previous counting algorithm for the permissive
version of the model was due to Montanari and Shah and was based on the
correlation decay method, which works up to densities $(1+o_k(1))\frac{2\log
k}{k}$, the Gibbs uniqueness threshold for the model. Instead, our algorithm
harnesses a recent technique by Moitra to work for random formulas. The main
challenge in our setting is to account for the presence of high-degree
variables whose marginal distributions are hard to control and which cause
significant correlations within the formula.
