Thanks for posting your question in the Microsoft Q&A forum.
In the absence of a backup for restoration, the sole recourse is to utilize the account recovery methods provided by each service provider. The Microsoft Authenticator functions solely as a code generator.
I 'd call the global number for support and reset the access.
Global Customer Service Phone Numbers
** Please don't forget to close up the thread here by upvoting and accept it as an answer if it is helpful **