Energy Table Decay

You are given a table with \( n \) rows and \( m \) columns. The rows are numbered from \(0\) to \(n-1\), and the columns from \(0\) to \(m-1\). Initially, the cell in row \(i\) and column \(j\) stores \(i \oplus j\) energy (where \(\oplus\) denotes bitwise XOR). Hence, the total energy initially stored in the table is

\(\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}(i \oplus j)\)

As time passes, every cell loses energy. After each time unit, every cell's energy decreases by \(1\), but it never goes below \(0\). In other words, after \(k\) time units, the energy in the cell at \((i, j)\) becomes

\(\max((i \oplus j)-k,\;0)\)

Your task is to compute the total energy stored in the table after \(k\) time units, that is,

\(\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}\max((i\oplus j)-k,\;0)\)

Since the answer can be large, output the result modulo \(p\).

inputFormat

The input consists of a single line containing four integers \(n\), \(m\), \(k\), and \(p\), where:

• n and m denote the number of rows and columns of the table respectively,
• k is the number of time units elapsed, and
• p is the modulus.

outputFormat

Output a single integer: the total remaining energy in the table after \(k\) time units, taken modulo \(p\).

sample

3 3 1 1000000007

6