# NMNMX whats wrong

I have used that total occurance of an element in subsequence will be (n-1)C(k-1) and total times it will be min will be (x)C(k-1) where x is number of element greater than element and total times it will be max will be (y)C(k-1) where y is number of element lesser than element.

So total occurance of any element will be (n-1)C(k-1)-(x)C(k-1)-(y)C(k-1)

but i am getting only 20 points and cant able to figure out whats wrong please help

https://www.codechef.com/viewsolution/19194234

Hi @rk_221b
I too am using same logic and facing same problem as you are.
I am afraid we are not using the right method to calculate nCr%p, and that is the only reason for WA.
I found this comment on other discussion , but wasnt able to make anything out of it, If you are able to make something out of it. Please Do reply.

Here’s the comment:

you can use Fermat’s little theorem to optimize ncr for the solution and do this without using big int. I was using big int and getting 20 marks and 3 test cases were not passing due to TLE.

Fermat’s little theorem

ab-1 (modulo b) = 1 (modulo b)

if b is prime

if you would like to see my solution

## I understood you are calculating :-

Click to view

m=10^9 + 7

### FOR each element :

#### R= number of elements on left side of “element (whose power we r calculating)”

occurrences=( ( \binom{n-1}{k-1}\mod m ) - (\binom {L}{k−1} \mod m) - ( \binom {R}{k−1} \mod m) )\mod m
(element)^{occurrences}\mod m

### ONLY WHEN a and b are co-prime

#### And if (x is prime) , phi(x)==x-1

2 Likes

basically phi(n) shows the positive integers up to a given integer n that are relatively prime to n
so when n is prime
phi(n) is always n-1

#### U can also see that using Fermat’s little theorem

7 is also prime hence
( 2^{(10 \mod 6)} \mod 7 ) = (2^4 \mod 7 ) = ( 16 \mod 7 ) = 2
2==2

Euler’s theorem generalises Fermat’s theorem

i m calculating
Occurrences=(((n−1k−1)modm)-((Lk−1)modm)-((Rk−1)modm))modm
(element)occurrencesmodm

yeah and that’s where u r wrong… replace m by m-1 in
Occurrences=(((n−1k−1)modm)-((Lk−1)modm)-((Rk−1)modm))modm

#### ALSO IN C++ don’t forget to make power positive if it goes negative in following way

(a-b-c)\mod m == ( ((a\mod m) - (b\mod m) -(c\mod m))\mod m )+m)\mod m