У Чанеки есть массив \([a_1,a_2,\ldots,a_n]\). Изначально все элементы покрашены в белый. Чанека выберет один или несколько различных индексов и покрасит элементы с этими индексами в черный цвет. Затем она выберет все белые элементы, чьи индексы кратны индексу по крайней мере одного черного элемента, и покрасит их в зеленый цвет. После этого ее оценка будет равна максимальному значению \(a_i\) среди всех черных и зеленых элементов.
Существует \(2^n-1\) способов выбрать черные индексы. Найдите сумму оценок для всех возможных способов, которыми Чанека может выбрать черные индексы. Поскольку ответ может быть очень большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число — сумму оценок по всем способам выбрать черные индексы по модулю \(998\,244\,353\).
Примечание
В первом примере ниже перечислены \(15\) возможных вариантов выбора черных индексов:
- Индекс \(1\) - черный. Индексы \(2\), \(3\) и \(4\) - зеленые. Максимальное значение среди них - \(19\).
- Индекс \(2\) - черный. Индекс \(4\) - зеленый. Максимальное значение среди них - \(14\).
- Индекс \(3\) - черный. Максимальное значение среди них - \(19\).
- Индекс \(4\) - черный. Максимальное значение среди них - \(9\).
- Индексы \(1\) и \(2\) - черные. Индексы \(3\) и \(4\) - зеленые. Максимальное значение среди них - \(19\).
- Индексы \(1\) и \(3\) - черные. Индексы \(2\) и \(4\) - зеленые. Максимальное значение среди них - \(19\).
- Индексы \(1\) и \(4\) - черные. Индексы \(2\) и \(3\) - зеленые. Максимальное значение среди них - \(19\).
- Индексы \(2\) и \(3\) - черные. Индекс \(4\) - зеленый. Максимальное значение среди них - \(19\).
- Индексы \(2\) и \(4\) - черные. Максимальное значение среди них - \(14\).
- Индексы \(3\) и \(4\) - черные. Максимальное значение среди них - \(19\).
- Индексы \(1\), \(2\) и \(3\) - черные. Индекс \(4\) - зеленый. Максимальное значение среди них - \(19\).
- Индексы \(1\), \(2\) и \(4\) - черные. Индекс \(3\) - зеленый. Максимальное значение среди них - \(19\).
- Индексы \(1\), \(3\) и \(4\) - черные. Индекс \(2\) - зеленый. Максимальное значение среди них - \(19\).
- Индексы \(2\), \(3\) и \(4\) - черные. Максимальное значение среди них - \(19\).
- Индексы \(1\), \(2\), \(3\) и \(4\) - черные. Максимальное значение среди них - \(19\).
Общая сумма составляет \(19+14+19+9+19+19+19+19+14+19+19+19+19+19+19 = 265\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
19 14 19 9
|
265
|
|
2
|
1
0
|
0
|
|
3
|
15
90000 9000 99000 900 90900 9900 99900 90 90090 9090 99090 990 90990 9990 99990
|
266012571
|