Pizza commercial claim of 34 million combinations

A pizza commercial claims that you can combine their ingredients to 34 million different combinations. I didn't believe it, so I dusted off my rusty combinatorics skills and tried to figure it out. Here's what I have so far:
From the online ordering site I got the choices

• crust (4 types, choose 1)

• size (4 types, choose 1) some crusts are limited to a certain size - not accounting for that, but would like to.

• cheese (5 types, choose 1)

• sauce (4 types, choose 1)

• sauce level (3 types, choose 1)

• meats (9 types, choose up to 9)

• non-meats (15 types, choose up to 15)

So I figured this was a combination problem (order is not important) and not an n choose k problem, null is allowed for anything but crust and crust, size, cheese, sauce and sauce level would all be choose only one. Meats and non-meats $2^?$? So that would be:

• crust $\binom{4}{1}=4$

• size $\binom{4}{1}=4$

• cheese $\binom{5}{1}=5$

• sauce $\binom{4}{1}=4$

• sauce level $\binom{3}{1}=3$

• meats $2^9 = 512$

• non-meats $2^{15} = 32768$

At this point I'm stuck, how do I combine these to arrive at the total number of possible combinations?

I found this site helpful.

ETA:
If I don't account for the limitations on crust size - some crusts are only available in certain sizes - there are over 16 billion; 16,106,127,360 combinations available, so they were off by quite a bit.

Ok, A bit more detailed answer than in the comments.

Choosing $k$ out of $n$ is done by ${n \choose k} = \frac{n!}{k!(n-k)!}$. So for things like the size of the pizza, where you have 4 options (and you need to choose one, coz pizza cannot be both medium and extra-large at the same times) you have only $4$ options. Indeed, ${4 \choose 1}=\frac{4!}{3!}=4$.

The interesting part are things like the non-meat options. You have 15 and can choose any set of up to 15. Mathematically, this means ${15 \choose 0} + {15 \choose 1} + \cdots + {15\choose 15}$.

As you mentioned, there is a nice formula for such sums:
$$\sum_{i=0}^n {n \choose i} = 2^i$$
thus, for the non-meat options you have $2^{15}=32768$ options, as you said.
(see here for more formulas).

Lastly, to combine all the options, you just multiply them. If you have 4 possible sizes, and, say, 4 possible crusts, then you have $4\times 4=16$ different combinations overall.

So, multiplying everything you get 16.106.127.360, which is larger than 34 million.

StackExchange Computer Science Q#3141, answer score: 19