Дана машина Тьюринга. В алфавит входят символы 0, 1 и пустой символ Λ (пробел). Команды записываются в виде: <текущее состояние> <текущий символ> → <новый символ> <направление> <новое состояние>.
Начальное состояние — q1. Головка находится над левым символом входной строки.
q1 0 → 1 П q1
q1 1 → 0 П q2
q1 Λ → Λ Л q3
q2 0 → 0 П q2
q2 1 → 1 П q1
q2 Λ → Λ Л q3
q3 0 → 0 Л q3
q3 1 → 1 Л q3
q3 Λ → Λ П q0
Здесь П — вправо, Л — влево, q0 — конечное (допускающее) состояние.
Сколько существует пятибитных входных строк (от 00000 до 11111), для которых в результате работы машины Тьюринга количество единиц в выходной строке не менее трёх?