SP4458 RAINBOW2 - Rainbow

这次Blue Mary继续进行毫无意义的计算！她对计算非常大的N * N矩阵A 的K次幂感兴趣，其中 $\text A _{i,j}=i\ \times\ \ $**D**$+$**Q**$^j$ i和j分别是元素A的行和列的从0开始的索引 $\text A _{i,j}$。 现在，她需要您的帮助（再次）。 为了使输出保持较小，仅要求您输出其某些元素。

多组测试数据。 每个测试数据的第一行包含5个以空格分隔的整数**N，K，D，Q，M**。随后是M行，每行包含两个以空格分隔的整数$\text R _{i}$和$\text C _{i}$ 。

对于每个测试数据，输出M行，每行仅包含一个整数：$\text R _{i}$列 $\text C _{i}$行的 矩阵A的K次幂。 结果可能会很大，对1000000000+2015取模。