Προετοιμάζομαι για τον xtreme που θα γίνει 22 Οκτωβρίου 2022 και έχω κολλήσει σε αυτό το πρόβλημα.
Προς το παρόν παίρνω 40/100 (με python) στο csacademy οπότε έψαχνα online να βρω ποια είναι η λύση που παίρνει 100. Ευτυχώς, βρήκα αυτό το repo αλλά δεν έχω καταλάβει τον τρόπο επίλυσης, ούτε κατάφερα να τον μεταφέρω στην python.

Η σκέψη μου ήταν ότι αρκεί να υπολογίσω το ${n\choose r} mod (10^9 + 6)$ και μετά να πάρω το α σε αυτήν τη δύναμη mod 10**9 + 7 (που το κάνει η python εύκολα μέσω της pow())

Δυσκολεύομαι όμως να το υπολογίσω αποτελεσματικά. Σε αυτήν τη λύση βλέπω ότι βρίσκετε το modular inverse (νομίζω) του παρονομαστή mod (MOD - 1)/2 και μετά όλο mod MOD-1 που μου φαίνεται περίεργο γιατί τι σχέση έχει το (MOD - 1)/2?

Γνωρίζω ότι το MOD-1 δεν είναι πρώτος οπότε δεν υπάρχει πάντα το modular inverse και εκεί είναι που κολλάω. Μπορείτε να εξηγήσετε γιατί δουλεύει το (MOD - 1)/2 ή να με κατευθύνετε σε κάποια πηγή?

Ευχαριστώ