POWPOW2(hard) doubt

I got the concept but had a little doubt that when p goes above and we take (b % (p-1)). Now p-1 is 10^9+6. Then we divide p-1 into 2 factor:- 2 * (5* 10^9 + 3). We solve b%(5*10^9 + 3) seperately . But what about b%2?

we first divided our situation into two cases , b is odd or b is even , so for odd number b%2=1 and for even b%2=0

ok. It was (b^(2nCn)) % (2*(510^8+3))
If b is odd then b%2=1 (I got this)
but 2 and 5
10^8+3 are in multiplication.
Are you saying that b% (2 * (510^8+3)) = (b%2)(b%(5*10^8+3)) ?
If no, then can you please explain a little more? Thanks in advance.

yes you are right you can see the video around 12:00 to understand this rule

I still didn’t understand why b%2 is not considered

I still didn’t understand where is b%2. Can you please explain ? Thanks in advance.

okay try this
https://www.quora.com/How-do-I-solve-Power-with-Combinatorics-HARD-on-SPOJ
this has elaborate explanation

Thanks…I got it

please mark your doubt as resolved :slight_smile:

When b is odd (b^(2nCn)) % (2*(5 10^8+3)) becomes (b^( (2nCn) % (510^8+2)) % (mod)
Is mod 510^8+3 or 10^9 +6?
Sir wrote mod = (5
10^8+3) but after reading the blog i think it should be 10^9+6. Can you help?

(5 *10 ^8 +3)*2== 10^9 +6
so sir wrote correct