== 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$.

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$