Cerința

Dându-se numărul natural nenul n, aflați câte cuvinte de exact n litere mici au proprietatea că orice două litere alăturate dintr-un cuvânt au diferența în modul a codurilor ASCII mai mare sau egală cu 2. Pentru că acest număr poate fi foarte mare, se va determina rezultatul modulo 3444449.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran un singur număr reprezentând rezultatul cerut.

Restricții și precizări

• 1 ≤ n ≤ 5000
• cuvintele vor fi formate numai din cele 26 de litere mici ale alfabetului englez

Exemplu:

Intrare

3

Ieșire

13848