时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
SolarPea thinks inversion is beautiful.
For a 01-sequence
with length 
and a constant 
, SolarPea defines the rating of is:
%3Dc%5E%7B%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7D%5Csum_%7Bj%3Di%2B1%7D%5En%5BZ_i%3EZ_j%5D%7D)
PolarSea has two integer sequences
and 
with length )
. PolarSea likes a 01-sequence with length if and only if 
.
SolarPea wrote all 01-sequences which have length and contain 
'1's on the paper. PolarSea saw it and crossed out all sequences that he doesn't like. Now you're given , please calculate the sum of the ratings of the remaining sequences on the paper.
For a 01-sequence
PolarSea has two integer sequences
SolarPea wrote all 01-sequences which have length
Since the answer could be very large, you should output it modulo 
(a prime number).
It is guaranteed that is generated randomly.
输入描述:
The first line contains four non-negative integers.
The nextlines, each line contains two non-negative intergers
and
.
It is guaranteed that all
输出描述:
Output the answer modulo