Cannot install ANY Facebook app. Be it regular, modded or even lite Patient:


Xiaomi Redmi 4 Prime
MIUI 10 v8.8.23 beta by xiaomi.eu
Android 6.0.1


What happened:


Annoyed with Facebook app burning my eyes, and unofficial mobile wrappers being generally slow and annoying to use, I installed a modded Facebook apk, one with black theme.
It was working perfectly fine, better than any unofficial app I had. The only annoyance was constant "WE DOWNLOADED NEW VERSION UPDATE NOW!!!"
Meanwhile, I decided to switch from SuperSU root to Magisk, since I've heard a lot of good things about it, and it can hide itself from apps like Pokemon GO which I always wanted to try (turns out PokeGO still detects root, go figure ¯\_(ツ)_/¯ )
I disabled AdAway, restored stock build.prop file, unrooted through SuperSU app, updated the ROM and flashed Magisk
That's when shenanigans started. Tapping the modded Facebook app icon was launching Sesame Shortcuts widget instead.
I held the icon, uninstalled, and it (seemingly) got rid of both modded Facebook and Sesame Shortcuts.
Here's where shit gets real. I tried installing:


Official Facebook app from Playstore (error 505)
Current Facebook app from apk (error parsing the package)
Older version of the Facebook app from apk (error parsing the package)
The modded, dark version Facebook app from apk (error parsing the package)
Facebook Lite from Playstore (error 505)

Of course, I tried a few methods to solve it, which didn't work:


SD Maid complete scan and clean
Cleaning Playstore and Play Services files
Uninstalling Playstore updates and updating it
Switching Google account
Wiping Downloads Manager files
Restarting the phone
Using Solid Explorer with root permissions to look for any leftovers and deleting them (two empty com.facebook.katana folders was all there was

At this point, I haven't tried (and would rather not try):


Factory reset
Reflashing the ROM



I'd be grateful for any help.
I've had issues installing apps after tweaking stuff before. I was sometimes able to resove it with pm set-install-location 0 in the terminal emulator (executed as superuser obviously).
Though after reading through the comments, it seems like the problem could be more deep then this. I'd also suggest to switch back to SuperSU and see if the problem persists, just like @gamermane-Marsh suggested.