* Pentru datele de test există întotdeauna soluţie.
* Dacă există mai multe soluţii optime de restaurare, va fi scrisă prima variantă în ordine lexicografică
(se ştie că ' '<'a').

* Ş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$) astfel încât x{~i~} = y{~i~} (pentru orice $1$ ≤ $i$ < $k$) şi x{~k~} < y{~k~}.

* Ş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$) astfel încât 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.