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

Dintr-o regretabilă eroare, redactorul Vasile a şters toate spaţiile din textul la care lucra. Textul este scris într-o limbă necunoscută, numai cu litere mici ale alfabetului englez. Vasile ştie că un cuvânt trebuie să conţină cel puţin o vocală şi că nu poate avea lungimea mai mare de $20$ de litere. De asemenea, fiind un tip meticulos, el ştie că în text erau (înainte de ştergerea spaţiilor) exact $N$ cuvinte.

Dintr-o regretabilă eroare, redactorul Vasile a şters toate spaţiile din textul la care lucra. Textul este scris într-o limbă necunoscută, numai cu litere mici ale alfabetului englez. Vasile ştie că un cuvânt trebuie să conţină cel puţin o vocală şi că nu poate avea lungimea mai mare de $20$ de litere. De asemenea, fiind un tip meticulos, el ştie că în text erau (înainte de ştergerea spaţiilor) exact $N$ cuvinte.
 

Vasile trebuie să restaureze textul, inserând spaţii între cuvinte. Cum există numeroase modalităţi de restaurare a textului, Vasile a hotărât să aleagă varianta în care literele sunt distribuite în cuvinte într-un mod cât mai armonios. Pentru a măsura armonia, Vasile a calculat suma pătratelor lungimilor cuvintelor. Textul este cu atât mai armonios, cu cât suma obţinută este mai mică.
h2. Cerinta

* Şirul ({$x$}{~1~}, $x${~2~}, ..., $x${~n~}) este mai mic lexicografic decât (y{~1~}, y{~2~}, ..., y{~n~}) dacă există $k$ ({$1$} &le; k &le; $N$) a.i x{~i~} = y{~i~} (pentru orice $1$ ≤ $i$ < $k$) şi x{~k~} < y{~k~}.
* Pentru $40$% dintre teste lungimea textului este < $70$ şi $N$ ≤ $7$.
* Punctajul pe test se va acorda astfel:

$50$% pentru numărul total de modalităţi de restaurare modulo $1000003$;
$80$% pentru numărul de modalităţi de restaurare modulo $1000003$ şi suma minimă;
$100$% pentru rezolvarea corectă a tuturor cerinţelor.

** $50$% pentru numărul total de modalităţi de restaurare modulo $1000003$;
** $80$% pentru numărul de modalităţi de restaurare modulo $1000003$ şi suma minimă;
** $100$% pentru rezolvarea corectă a tuturor cerinţelor.

h2. Exemplu

3926