Unity push notifications error (Can't enable legacy cloud messaging in Firebase)

I am trying to enable the push notifications in my game, but when I try to retrieve the push notification token I get this error:

Failed to initialize Push Notification Plugin java.lang.NoClassDefFoundError: Failed resolution of: Lcom/google/firebase/messaging/RemoteMessage;

I have done all the other steps in the documentation but in Firebase I can’t enable the Cloud Messaging (legacy) because it seems to no longer be available!
I’m completely stuck with this since I can’t get it on. I tried with multiple projects.

Is this something that will cause this error or can I use push notifications without this legacy cloud messaging?

What documentation or instructions are you basing this off of? The legacy APIs for Firebase Cloud Messaging have been disabled and replaced with the V1 Send API.

Please go through the guide Set up a Firebase Cloud Messaging client app with Unity and if necessary try Debugging the Game Build, Install and Run Process