Well, hopefully you created a backup by storing a copy of the QR code somewhere :)

This literally happened to me and is the reason I no longer use Authenticator. Everything else on my entire phone restored, but not Authenticator.