6174 — доволі цікаве число. Якщо розмістити його цифри у порядку зростання, отримаємо 1467; якщо розмістити його цифри у порядку спадання, вийде 7641. Результатом віднімання двох отриманих чисел буде $7641 - 1467 = 6174$.
Цікавим є й те, що якщо взяти будь-яке чотиризначне число та повторити попередні дії сортування цифр та віднімання, ми отримаємо 6174 або одразу 0, якщо всі цифри однакові.
Те саме відбувається з числами, які складаються з менше ніж із 4 цифр. Але для цього до них потрібно додати нулі, щоб утворити чотиризначні числа.
6174 називається сталою Капрекара. Сортування цифр, віднімання та повторення цього процесу поки не отримаємо 0 або сталу Капрекара, називається перетворенням Капрекара.
Можна розглядати рутину Капрекара і для інших систем числення та кількості цифр. На жаль, стала Капрекара існує не у всіх випадках. Перетворення закінчується циклом для деяких вхідних чисел або стала, отримана в результаті перетворення, інша для різних вхідних чисел. Однак для п'яти цифр та основи $b = 6t + 3 ≠ 9$ константа Капрекара існує.
Наприклад, основа 15: ${(10, 4, 14, 9, 5)}\_{15}$ основа 21: $(14, 6, 20, 13, 7)_{21}$
Нехай $C_b$ — стала Капрекара в основі $b$ для 5-ти цифр. Визначте функцію $sb(i)$:
- 0, якщо $i = C_b$, або якщо $i$, записаний в основі $b$, складається з 5-ти однакових цифр
- кількість повторень, здійснених під час перетворення Капрекара в основі $b$, щоб досягти $C_b$
Зверніть увагу, що ми можемо визначити $sb(i)$ для всіх цілих чисел $i < b^5$. Якщо $i$, записане в основі $b$ має менше, ніж 5 цифр, то до числа додаємо нулі, поки не воно не стане п'ятизначним. Аж тоді застосовуємо перетворення Капрекара.
Визначимо $S(b)$ як суму $sb(i)$ для $0 < i < b^5$. Наприклад, $S(15) = 5\\,274\\,369$ $S(111) = 400\\,668\\,930\\,299$
Знайдіть суму $S(6k + 3)$ для $2 ≤ k ≤ 300$. У відповіді запишіть 18 останніх цифр.
# --hints--
`kaprekarConstant()` має повернути `552506775824935500`.
