I had the same problem initially, very frustrating.
I then installed google drive on my phone, I ran the initial virus scan, went to avast backup > browse backup > Device (archived) > Restore all
Everything good as new! All my contacts, messages, files there. Awesome!