How to recover data from formatted encrypted external hdd?
Unfortunately, it’s gone.

When you encrypt your drive, it gets scrambled with a randomized key so, if you were to look at the actual sectors of the drive, it would just be a jumbled mess.  The key is what takes that “mess” and turns it into usable data.

Recovery programs can’t rescue your data because a) they can’t distinguish between the encryption you did the first time versus the second, and b) being encrypted it can’t “see” the actual file structure to associate what blocks go with what.  This is why and how encryption protects your data from nefarious actors; your data can’t be recovered.

This is also why having a backup is extra critical when you go this route.