A formula is satisfiable if there exists some variable assignment that makes it true; that is, there is some row in its truth table that comes out to true instead of false. Determining whether an arbitrary boolean formula is satisfiable is called the satisfiability problem. There is no known efficient solution to this problem, in fact, an efficient solution would earn you a million dollar prize. While this is hard problem in computer science, not all instances of the problem are hard, in fact, determining satisfiability for some types of boolean formulae is easy.

Now consider the following 500 variable formula: x1 (x1 x2) (x2 x3) . . . (x499 x500) Without constructing a truth table, how many satisfying assignments does this formula have? Explain your answer.