Задано деяке \(n\)-значне натуральне число \(x\).

Знайдіть суму всіх чисел, що виходять перестановкою цифр числа \(x\) .

Виведіть залишок від ділення цієї суми на число 366239.

Якщо одне й те саме число виходить за допомогою кількох перестановок, його необхідно враховувати відповідне число разів. Крім цього, в числах, що виходять за допомогою перестановок, можуть бути провідні нулі.

Наприклад, якщо \(x\) = 123 , то відповідні числа є: {123, 132, 213, 231, 312, 321} а їх сума дорівнює 1332. Якщо \(x\) = 122 , то відповідні числа є: {122, 122, 212, 212, 221, 221} а їх сума дорівнює 1110. Якщо \(x\) = 103 , то відповідні числа є: {013, 031, 103, 130, 301, 310} а їх сума дорівнює 888 .

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

Вхідний файл містить ціле число \(x\) ( \(1 ≤ x ≤ 10^{18}\) ). Воно задано в десятковій системі числення і не містить провідних нулів.

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

У вихідний файл виведіть залишок від ділення шуканої суми на число 366239.

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

122

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

1110

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

123

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

1332

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

103

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

888