A. 神奇的数

内存限制:256 MiB 时间限制:1000 ms 输入文件:number.in 输出文件:number.out
题目类型:传统 评测方式:文本比较

题目描述

LogeY 想告诉你一个神奇的数,为什么神奇呢?因为 …… 她也不知道这个数具体是多少!

LogeY 只能给你一个关于 x n 项多项式,并给定一个 x ,然后,这个多项式带入该 x 时的值的最后 k 位数字就是 LogeY 想给你的数字。

一个含有 n 项的多项式的值,指的是这 n 项每一项的值加起来的总和。例如,一个含有 3 项的多项式 f = 5x^4 + 3x^2 + 3x ,代入 x = 2 时,它的值为 5 \times 2^4 + 3 \times 2^2 + 3 \times 2 = 98.

输入格式

第一行两个整数 n k
之后的 n 行,每行两个数 a_i b_i ,表示多项式的一项 a_i x ^ {b_i}
最后一行一个整数 x

输出格式

输出 k 行,按顺序输出该多项式带入 x 后值的最后 k 位数字,若不足 k 位,则高位补零。

样例

输入样例

2 1
3 2
1 5
3

输出样例

0

数据范围与提示

对于 30\% 的数据, n, k, a_i, b_i \leq 3, x \leq 10
对于 100\% 的数据, 1 \leq n \leq 100000, 1 \leq a_i, b_i, x \leq 10 ^ 9, 1 \leq k \leq 8