{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\nОпределим еще одну последовательность чисел, заданную следующей функцией:\n\n$$\nf(n) \u003d\n\\begin{cases}\na, \u0026 \\text{если $n$ \u003d 0} \\\\\\\\\nb, \u0026 \\text{если $n$ \u003d 1} \\\\\\\\\nf(n - 1) + f(n - 2), \u0026 \\text{если $n$ \u003e 1}\n\\end{cases}\n$$\n\nКогда **a \u003d 0** и **b \u003d 1**, эта последовательность дает последовательность Фибоначчи. Изменяя значения **a** и **b**, вы сможете получить много разных последовательностей.\n\nЗная значения **a, b**, вам нужно найти **m** наименее значимых цифр числа **f(n)**.\n"}},{"title":"Входные данные","value":{"format":"MD","content":"Входные данные начинаются с целого числа **T (\u0026#8804; 10000)**, обозначающего количество тестов.\n\nКаждый тест состоит из одной строки, содержащей четыре целых числа **a b n m**. Значения **a** и **b** находятся в диапазоне **[0,100]**, значение **n** находится в диапазоне **[0, 10\u003csup\u003e9\u003c/sup\u003e]** и значение **m** находится в диапазоне **[1, 4]**."}},{"title":"Выходные данные","value":{"format":"MD","content":"Для каждого случая выведите номер случая и последние **m** цифр числа **f(n)**. Однако, **НЕ** выводите ведущий ноль."}},{"title":"Пример","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eВходные данные\u003c/th\u003e\n \u003cth\u003eВыходные данные\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0 1 11 3\n0 1 42 4\n0 1 22 4\n0 1 21 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 89\nCase 2: 4296\nCase 3: 7711\nCase 4: 946\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}