La lunghissima parola di Simona

Simona ha 9 lettere X e 7 lettere Y. Considera tutte le parole (di lunghezza almeno 2) che può formare prendendone alcune e disponendole in fila; poi le scrive tutte di seguito, senza spazi, ottenendo un'unica lunghissima stringa. Da quante lettere è composta? (Dai come risposta le ultime 4 cifre del risultato.)