There are many magical functions in the beautiful world of Mathematics and Computer Science. A magical function is defined as , for all
,
. It is known that
.
is defined as the greatest integer that is less than or equal to
.
Given the constants ,
,
,
,
, and some non-negative integer
, find the value of
modulo
.
Input Specification
On the first and only line of input, are given, separated by a single space.
are all integers.
Output Specification
Output .
Constraints
For all subtasks:
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [60%]
Sample Input
1 2 3 4 5 6
Sample Output
95
Comments