Proving special case of SAT is in P

Question

Let SAT-100 be the following problem:

Input: Any boolean logic formula

Output: True if there exists a combination of exactly 100 input variables that satisfy the formula.

This is the description of a problem that is apparently in $P$. (old exam question)

I have tried to design an algorithm but I got stuck, so here it goes:

Input: boolean logic formula F
    If(count(variables in F)) < 100:
       return false
    else
        # try all combinations of input variables

And here is the problem: building and evaluating all combinations of input variables can't seem to be polynomial because:

$$ { n \choose 100} = \frac{n! }{100! \cdot (n-100)!} \in \mathcal{O}(n!) $$

and this nasty factorial can't be bounded with any polynomial that I know of.

I don't think the exam is wrong, so I must have overlooked something.

Answer 1

Note that $$\frac{n!}{(n-100)!100!}<\frac{n!}{(n-100)!}= n \cdot (n-1)\cdot \ldots \cdot (n-99)< n^{100}.$$

Thus, your algorithm runs in polynomial time