14115번 - Permutacije

Koliko ima različitih permutacija riječi A koje sadrže riječ B?

Ispišite ostatak pri dijeljenju tog broja sa 10007.

Prvi redak sadrži niz malih slova engleske abecede, riječ A. Duljina niza neće biti veća od 500.

Drugi redak sadrži niz malih slova engleske abecede, riječ B. Riječ B neće biti dulja od riječi A. 

U prvi i jedini redak ispišite ostatak pri dijeljenju traženog broja permutacija sa 10007. 

Šest permutacija koje sadrže riječ mir su: kmiro, komir, mirko, mirok, okmir i omirk.