410274: GYM103999 C Prime

Besides the delicacy that is freshmen blood drank during the Halloween night, Luna also enjoys prime numbers a lot... and the number 3... so she gives you a number $$$N$$$ and demands the number of different ways that the number $$$N$$$ can be written as a sum of 3 prime numbers.

Because you won't risk getting your blood drank by Luna, you decide to answer her demands.

The only line of input contains one integer $$$N$$$ ($$$ 1 \leq N \leq 5\cdot 10^4$$$)

Output a single integer - the number of ways to write $$$N$$$ as sum of 3 prime numbers.

• for 40 points it is guaranteed that $$$N \leq 100$$$
• for another 30 points it is guaranteed that $$$N \leq 5000$$$
• for the other 30 points, $$$N \leq 5\cdot 10^4$$$

7

1

The only correct way of expressing 7 as sum of 3 prime numbers is $$$7=2+2+3$$$. Permutations of the same prime numbers won't count (such as $$$2+3+2$$$)