== include(page="template/taskheader" task_id="jupanul") ==

I-a luat Jupânului 4653 de zile să cureţe Londra de mafioţi. I-a ramas doar unul, anume burghezul metabalzacian Stănică Raţiu. De aceea Jupanul a venit in Bucuresti, pentru a isi indeplini odata pentru totdeauna telul.

I-a luat Jupânului 4653 de zile să cureţe Londra de mafioţi. I-a ramas doar unul, anume burghezul metabalzacian Stănică Raţiu. De aceea Jupanul a venit în Bucuresti, pentru a-şi îndeplini odată pentru totdeauna ţelul.

h2. Cerinta

h2. Cerinţă

Pentru un şir de numere $a$, definim _costul_ ca fiind suma gcdurilor{$†$} tututor prefixelor lui $a$. De exemplu, costul şirului $[12, 6, 9, 2]$ este $gcd(12) + gcd(12, 6) + gcd(12, 6, 9) + gcd(12, 6, 9, 2) = 12 + 6 + 3 + 1 = 22$.

Pentru un şir de numere $a$, definim _costul_ ca fiind suma gcd-urilor{$†$} tututor prefixelor lui $a$. De exemplu, costul şirului $[12, 6, 9, 2]$ este $gcd(12) + gcd(12, 6) + gcd(12, 6, 9) + gcd(12, 6, 9, 2) = 12 + 6 + 3 + 1 = 22$.

Definim $f(n,k)$ ca fiind suma costurilor tuturor partitiilor lui $n$ în $k$ termeni.{$‡$}

Definim $f(n,k)$ ca fiind suma costurilor tuturor partiţiilor lui $n$ în $k$ termeni.{$‡$}

Dându-se $n$ şi $m$, si un sir $k{~1~}, k{~2~}, ..., k{~m~}$, voi trebuie să calculaţi $f(n, k{~1~}), f(n, k{~2~}),..., f(n, k{~m~})$. Cum aceste numere pot fi foarte mari, Jupanul va roaga sa le afisati modulo $998244353$.

Dându-se $n$ şi $m$, şi un şir $k{~1~}, k{~2~}, ..., k{~m~}$, voi trebuie să calculaţi $f(n, k{~1~}), f(n, k{~2~}),..., f(n, k{~m~})$. Cum aceste numere pot fi foarte mari, Jupânul vă roagă să le afişaţi modulo $998244353$.

$†$ Prin $gcd(a{~1~}, a{~2~},..., a{~i~})$ s-a notat "cel mai mare divizor comun":https://en.wikipedia.org/wiki/Greatest_common_divisor al numerelor $a{~1~}, a{~2~},..., a{~i~}$.
$‡$ Prin o partiţie a lui $n$ în $k$ termeni, înţelegem un şir de numere pozitive $a{~1~}, a{~2~},..., a{~k~}$ cu proprietatea că $a{~1~} · a{~2~}· ... · a{~k~}=n$
h2. Date de intrare

Pe prima linie a fişierului $jupanul.în$ conţine numerele $n$ şi $m$ separate printr-un spaţiu. Pe a doua linie, se vor afla $m$ numere $k{~1~}, k{~2~}, ..., k{~m~}$.

Prima linie a fişierului $jupanul.în$ conţine numerele $n$ şi $m$ separate printr-un spaţiu. Pe a doua linie, se vor afla $m$ numere $k{~1~}, k{~2~}, ..., k{~m~}$.

h2. Date de ieşire

h2. Restricţii
* $1 ≤ n ≤ 10^12^$

* $1 ≤ m ≤ 1 000 000$
* $1 ≤ k{~i~} ≤ 200 000$, pentru orice $i$ care respecta $1 ≤ i ≤ m$

* $1 ≤ m ≤ 1 500 000$
* $1 ≤ k{~i~} ≤ 1 500 000$, pentru orice $i$ care respectă $1 ≤ i ≤ m$
* Din cauza dimensiunii mari a testelor, se recomandă "parsarea fişierelor de intrare":https://www.infoarena.ro/parsare-fisier-intrare şi a "fişierelor de ieşire":https://www.infoarena.ro/parsare-fisier-iesire

h2. Subtaskuri

* $Subtask %{color:#55DDE0; font-weight:bold} Esti un om norocos, Gavrilescule!% - 9 puncte: n ≤ 5 000$
* $Subtask %{color:#33658A; font-weight:bold} Cata luciditate atata drama% - 6 puncte: n ≤ 100 000$
* $Subtask %{color:#2F4858; font-weight:bold} Metoda Ungureasca% - 8 puncte: n ≤ 1 000 000$
* $Subtask %{color:#D4ADCF; font-weight:bold} Oppenheimer% - 7 puncte: m ≤ 5$
* $Subtask %{color:#F6AE2D; font-weight:bold} Aici ar trebui sa intre doar AIB% - 20 puncte: m ≤ 1 500$
* $Subtask %{color:#D62828; font-weight:bold} Du-te, dar nu mă vei uita% - 33 puncte: m ≤ 200 000$
* $Subtask %{color:#A82371; font-weight:bold} Drumul e lung, si tare as vrea s-ajung% - 17 puncte: Fără restricţii suplimentare$

* $Subtask %{color:#55DDE0; font-weight:bold} Eşti un om norocos, Gavrilescule!% - 11 puncte (testele 1-2): n ≤ 5 000, m ≤ 80 000, k{~i~} ≤ 100 000$
* $Subtask %{color:#33658A; font-weight:bold} Câtă luciditate atâta dramă% - 12 puncte (testele 3-4): n ≤ 100 000, m ≤ 80 000,  k{~i~} ≤ 100 000$
* $Subtask %{color:#2F4858; font-weight:bold} Dă-mi nopţile înapoi% - 10 puncte (testele 5-6): n ≤ 1 000 000, m ≤ 80 000, k{~i~} ≤ 100 000$
* $Subtask %{color:#F6AE2D; font-weight:bold} Aici ar trebui să intre doar AIB% - 24 puncte (testele 7-10): m ≤ 500, k{~i~} ≤ 200 000$
* $Subtask %{color:#D62828; font-weight:bold} Du-te, dar nu mă vei uita% - 42 puncte (testele 11-15): m ≤ 80 000, k{~i~} ≤ 200 000$
* $Subtask %{color:#A82371; font-weight:bold} Şi veşnicia chiar în dar s-o primim% - 1 punct (testul 16): Fără restricţii suplimentare$

h2. Exemplu