# Complexity for nested #P?

Consider a problem such as weighted model counting for propositional logic. The problem of enumerating all models M of a logic formula f and summing their weights w(M) is #P. What happens if the weight is a function of the model and the task of computing the weight w(M) given M is in itself #P? Whats the complexity of the total problem?

The result is in #P. Suppose there are 50 states, and each state has 10 cities. Then how many cities are there in total?

Now suppose we have a polytime verifier for states: $S(x)$ outputs 1 iff $x$ is a state. We also have a polytime verifier for cities: $C(x,y)$ outputs 1 iff $y$ is a city in state $x$. Then counting the number of states is in #P: it's the number of $x$ such that $S(x)=1$. If you think a bit, you can see that counting the number of cities is also in #P: it's the number of pairs $(x,y)$ such that $S(x)=1 \land C(x,y)=1$. Can you come up with a polytime verifier $V$ such that $V(x,y)=1$ iff $x$ is a state and $y$ is a cities in that state? I bet you can. Consequently, counting the number of such pairs (i.e., counting the number of cities) is in #P.

Now apply the same idea to your problem, and you should be able to figure out the answer.