Migrating to API31 and com.google.android.gms.internal.zzbej not found error

Question

After hours of trying and analyzing I gave up :( I'm in the process of updating my Google Play app, so I was forced to switch to API31, and this is where the problem started.

I changed targetSdkVersion and compileSdkVersion to 31, the app of course launched without any problem, but notifications stopped coming. I added android:exported="true" to all firebase services and according to the answer in another thread I change firebase libraries to newer ones.

In build.gradle I replaced

implementation 'com.google.firebase:firebase-core:11.6.2'
implementation 'com.google.firebase:firebase-auth:11.6.2'
implementation 'com.google.firebase:firebase-messaging:11.6.2'

at

implementation 'com.google.firebase:firebase-core:21.1.1'
implementation 'com.google.firebase:firebase-auth:21.1.0'
implementation 'com.google.firebase:firebase-messaging:23.1.1'

The application correctly build OK, but when I try to run it I get an error

map.addMarker(new MarkerOptions().position(new LatLng(lat, lon))
                                                     ^  class file for com.google.android.gms.internal.zzbej not found

This is my build.gradle.

dependencies {

    implementation fileTree(dir: 'libs', include: ['*.jar'])

    implementation group: 'com.squareup.picasso', name: 'picasso', version: '2.5.2'

    implementation 'jp.wasabeef:picasso-transformations:2.2.0'

    implementation 'com.github.ticofab:android-gpx-parser:2.0.0'


    implementation 'com.github.bumptech.glide:glide:4.8.0'
    implementation 'androidx.work:work-runtime:2.7.1'


    implementation 'com.makeramen:roundedimageview:2.3.0'

    implementation 'androidx.appcompat:appcompat:1.0.0'

    implementation 'com.google.maps.android:android-maps-utils:0.5'

    implementation 'com.google.firebase:firebase-core:21.1.1'
    implementation 'com.google.firebase:firebase-auth:21.1.0'
    implementation 'com.google.firebase:firebase-messaging:23.1.1'

    implementation 'com.google.android.gms:play-services:11.6.2'
    implementation 'com.google.android.gms:play-services-auth:11.6.2'

    implementation "com.google.android.material:material:1.4.0-alpha02"
    implementation "androidx.viewpager2:viewpager2:1.1.0-alpha01"

    implementation 'androidx.constraintlayout:constraintlayout:1.1.3'
    implementation 'androidx.legacy:legacy-support-v4:1.0.0'

    implementation 'androidx.vectordrawable:vectordrawable:1.1.0'
    implementation 'androidx.annotation:annotation:1.5.0'
    testImplementation 'junit:junit:4.12'
    androidTestImplementation 'androidx.test.ext:junit:1.1.1'
    androidTestImplementation 'androidx.test.espresso:espresso-core:3.1.0'
}

apply plugin: 'com.google.gms.google-services'

I have updated all possible libraries, but the problem persists. I tried also implementation platform('com.google.firebase:firebase-bom:31.2.0') and still the same. Any ideas? Commenting on the code that causes the problem doesn't help, because new errors with the same content appear. I guess there is something wrong in build.gradle. Thanks in advance.