Coco is playing with white and dark chocolate pieces as usual. A chocolate array is a one-dimensional arrangement of white and dark chocolate pieces. Let's call a chocolate array containing white and dark pieces pretty if it satisfies the following. and denote a single white and dark piece respectively, is a pretty chocolate array, and is the concatenation of chocolate arrays .
The score of a chocolate array is calculated as follows. Start with an integer . Then, for each chocolate from left to right, add if it is white, and multiply if it is dark. Finally, take the remainder modulo .
Coco wants to find the pretty chocolate array with the highest score. Calculate the score of the best-scoring pretty chocolate array.
The first line of input contains the integers , , , and , separated by spaces. (, )
Output the highest score achievable with a pretty chocolate array containing white and dark chocolate pieces.