(М. Шагитов) У исполнителя Калькулятор имеются три команды, которым присвоены номера:
1. Прибавь 3
2. Прибавь 5
3. Умножь на 2
Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – увеличивает на 5, выполняя третью – умножает число на 2.
Сколько существует программ, которые преобразуют число 1 в число 10000 и при этом траектория вычислений программы содержит число 3000 или 5000, но не оба эти числа одновременно? В ответе запишите последние 6 цифр этого числа.