Лампочки

Джон має $n$ лампочок і щиток з $n$ вимикачами. Кожна лампочка може бути увімкнена або вимкнена; натискання $i$-го вимикача змінює стан лампочки $i$ (з увімкненої на вимкнену і навпаки). Він використовує цю установку для гри власного винаходу. За кожен хід Джон обирає деяку (можливо порожню) підмножину вимикачів і натискає їх, тим самим перемикаючи відповідні лампочки. Після рівно $m$ ходів Джон хоче, щоб перші $v$ лампочок світилися, а решта були вимкнені; якщо це не вдалося, він програє. Є лише одне обмеження: ту ж саму підмножину вимикачів не можна натискати у різних ходах.

Ця гра проста, оскільки існує багато способів перемогти. Це спонукало його спробувати всі можливі виграшні ігри. Допоможіть Джону порахувати кількість способів виграти. Дві ігри вважаються однаковими, якщо після перестановки ходів у кожній грі буде натиснуто однакові підмножини вимикачів у кожному ході.

Наприклад, якщо n = 4, m = 3, а v = 2, одним з можливих виграшних варіантів є натиснути вимикачі $1,2$ та $4$ у першому ході; $1$ та $3$ у другому; та $1,3$ і $4$ у третьому. Це вважається еквівалентним, наприклад, до першого натискання $1$ і $3$, потім $1,2,4$, а потім $1,3,4$.