No system keyboard, unable to proceed after factory reset

I did quite a stupid thing yesterday - while de-bloating my S4, I removed samsung keyboard (via Titanium Backup) as I was only using the Google Keyboard. Today I had to factory reset the phone, and on the very first screen I realized that there is no keyboard as Google keyboard got deleted by wiping the phone. Duh... What are my options besides completely restocking the phone? I woudl really want to avoid that as I don't want to go through the whole de-bloating process again. Any ideas highly appreciated!