Відомі перші членів послідовності \(𝑎_1,𝑎_2,…,𝑎_𝑘\) (\(0≤𝑎_𝑖≤9\) , де \(𝑖=1,2,…,𝑘\) ). Інші члени послідовності обчислюються за таким правилом: \(𝑎_𝑖=\sum_{j=i-k}^{i-1}𝑎_𝑗 \), тобто кожен наступний член дорівнює сумі \(𝑘\) попередніх.

Необхідно знайти останні \(𝑟\) цифр числа \(𝑎_𝑛\) .

Формат вхідних даних

У першому рядку знаходяться 3 цілих числа - \(𝑘\) , \(𝑛\) і \(𝑟\) (\(1≤𝑘≤20\) , \(1≤𝑛≤10^{18}\) , \(1≤𝑟≤9\) ).

У наступному рядку знаходиться \(𝑘\) чисел – \(𝑎_1,𝑎_2,…,𝑎_𝑘 \).

Формат вихідних даних

Першим рядком виведіть \(𝑟\) цифр числа \(𝑎_𝑛\) . Провідні нулі слід опустити.

Приклад вхідних даних

2 5 1
1 2

Приклад вихідних даних

8

Приклад вхідних даних

1 100001 1
5

Приклад вихідних даних

5