Welcome to Android Central, and sorry to hear about your problem! Were all of your contacts saved in the Phone account or your Google account? If the latter, then they should all be in the Google Cloud. I don't know of an easy way to recover Phone account contacts-this is why I never recommend storing contacts in the Phone account.