What to do with feature button in an app when user permanently rejects the runtime permission for it?

The permission model in Android allows a user to either grant, deny, or permanently deny a runtime permission. Also if the user denies a permission twice it is treated as a permanently deny.

I have a button for a feature that requires the permission. What do I do with it if the user has permanently denied the permission?

Showing a message on click that says: "To use this feature please uninstall the app, and reinstall it, and grant permission x when prompted" seems kind of terrible, but so does two different people having a radically different feature set based on a runtime permission.

This is a somewhat similar question to Show/hide actions when the user doesn't have permission except that if the user permanently denies the permission, there is no way to undo that other than reinstalling the app.