Initially your code was taking about 19-20 secs to complete.
I added memoization, now it takes 2-3 secs to complete.
Hope it helps.
In case you have to rerun program many times. I have saved the 'mydict' object using 'pickle'. then reuse it.
In case of reuse, program takes less than 1 second
Repl link for the code