1.4 KiB
1.4 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f50e1000cf542c510020 | Завдання 416: Подорож жабки | 5 | 302085 | problem-416-a-frogs-trip |
--description--
У ряді, що складається із n квадратів, жабка знаходиться у найлівішому. Стрибаючи, жабка прямує у найправіший, а потім повертається у найлівіший. Під час своєї подорожі туди та сюди, вона стрибає на 1, 2 або 3 квадрати праворуч, і таким самим чином назад ліворуч. Жабка не може вистрибнути за межі квадратів. Вона повторює подорож m разів.
Нехай F(m, n) — кількість способів, якими жабка може пресуватися, щоб щонайменш один квадрат залишився невідвіданим.
Наприклад, F(1, 3) = 4, F(1, 4) = 15, F(1, 5) = 46, F(2, 3) = 16 та F(2, 100)\bmod {10}^9 = 429\\,619\\,151.
Знайти останні 9 цифр з F(10, {10}^{12}).
--hints--
frogsTrip() має повернути 898082747.
assert.strictEqual(frogsTrip(), 898082747);
--seed--
--seed-contents--
function frogsTrip() {
return true;
}
frogsTrip();
--solutions--
// solution required