Розфарбовування куль#3376
Є білих куль на столі, розташованих у два рядки, утворюючи прямокутник розміром 2 \times N. У Джона є велике відро з чорною фарбою. (Не питайте чому.) Він хоче пофарбувати всі кулі в чорний колір, але прагне отримати трохи математичного задоволення під час цього. (Знову ж таки, не питайте чому.) Спочатку він підрахував кількість різних способів пофарбувати всі кулі в чорний колір. Швидко він зрозумів, що відповідь - це і подумав, що це занадто просто. Тому він ввів деякі правила, щоб зробити задачу цікавішою.
Перша куля, яку Джон фарбує, може бути будь-якою з куль.
Після цього кожна наступна куля, яку він фарбує, повинна бути суміжною з якоюсь чорною кулею (яка вже була пофарбована). Дві кулі вважаються суміжними, якщо вони знаходяться поруч одна з одною горизонтально, вертикально або діагонально.
Джон був дуже задоволений правилами, тому почав рахувати кількість способів пофарбувати всі кулі відповідно до них. Чи можете ви написати програму, яка знайде відповідь швидше, ніж Джон?
Вхід складається з кількох тестових випадків. Кожен тестовий випадок складається з одного рядка, що містить ціле число , де 1 \le N \le 1000. Вхід завершується рядком з N = 0.
Для кожного тестового випадку виведіть один рядок, що містить кількість можливих способів, якими Джон може пофарбувати всі куль відповідно до його правил. Число може стати дуже великим, тому виведіть число за модулем .
Приклад 1