Testing navigation - IncompatibleClassChangeError -TestNavHostController is declared final

I'm trying to test navigation in my sample app. I've taken the google navigation testing tutorial. Here's my code:

    @RunWith(AndroidJUnit4::class)
    @LargeTest
    class NavigationTest {
        @get:Rule
        val activityRule = ActivityScenarioRule(MainActivity::class.java)
    
        @Test
        fun checkNavigation() {
            // -------- crash --------
            val navController = 
                TestNavHostController(ApplicationProvider.getApplicationContext())
            // -----------------------

            navController.setGraph(R.navigation.nav_graph)
            val fragmentScenario = launchFragmentInContainer<FirstFragment>()
            fragmentScenario.onFragment { frag ->
                Navigation.setViewNavController(frag.requireView(), navController)
            }
   
            onView(withId(R.id.button_first)).perform(click())
            assertEquals(navController.currentDestination?.id, R.id.SecondFragment)
        }
    }

I'm getting a crash on first line of test:

java.lang.IncompatibleClassChangeError: Superclass androidx.navigation.NavHostController of androidx.navigation.testing.TestNavHostController is declared final (declaration of 'androidx.navigation.testing.TestNavHostController' appears in /data/app/myApp.test-2vutApQLPNgS6e58B0_9tQ==/base.apk)

my test-related build.gradle lines:

    androidTestImplementation 'androidx.test.espresso:espresso-core:3.3.0'
    androidTestImplementation 'androidx.test:runner:1.3.0'
    androidTestImplementation 'androidx.test:rules:1.3.0'
    androidTestImplementation "androidx.navigation:navigation-testing:2.3.1"
    androidTestImplementation "androidx.fragment:fragment-testing:1.2.5"
    testImplementation 'junit:junit:4.13.1'
    androidTestImplementation 'androidx.test.ext:junit:1.1.2'

I've tried this on two phones and it's the same on both (Samsung with Android 8.0 and Huawei with Android 10)

I only saw this crash in relation to firebase, and the answer was to update my sdk-tools. I did, but no luck. I can't find any answers on this topic. Any idea how can I solve this issue?