SP13945 GHALIBC - GHALIBS CHALLENGE

"har ek baat pe kehte ho tum ke 'too kya hai?' tumheen kaho ke yeh andaaz-e-guftgoo kya hai?" Ghalib was a great poet and was very higly regarded by the emperor. Some of the nobles did not like this, so concocted a plan to reduce his influence on the emperor. They gave him a challenge, he could be given n bags of marbles. The first bag has 1 marble, second bag has 2 marbles and so on. Each of the marble has a unique radius between 1 and i, where i is the number of the bag. Ghalib has to tell the number of ways arranging these marbles. (The marbles in each of the bag have to be arranged separately and the number of ways summed up for all the bags). Ghalib complained to the king that this task is too difficult. So the king tried to help him a bit. (n+1) will only be divisible by a single prime - p (i.e. (n+1)=p^a) and he has to only find ways of rearranging those bags of marbles whose size is equal to r mod(p-1) and (p+1)/2

1

A single number representing the required answer