小C喜欢跑步，并且非常喜欢在微信步数排行榜上刷榜，为此他制定了一个刷微信步数的计划。
    他来到了一处空旷的场地，处于该场地中的人可以用k维整数坐标(a₁,a₂,···,a_k)来表示其位置。场地有大小限制，第i维的大小为w_i，因此处于场地中的人其坐标应满足1≤a_i≤w_i（1≤i≤k）。
    小C打算在接下来的P=w₁×w₂×···×w_k天中，每天从场地中一个新的位置出发，开始他的刷步数计划（话句话说，他将会从场地中每个位置都出发一次进行计划）。
    他的计划非常简单，每天按照事先规定好的路线行进，每天的路线由n步移动构成，每一步可以用ci与di表示：若他当前位于(a₁,a₂,···,a_ci,···,a_k)，则这一步他将会走到(a₁,a₂,···,a_ci+di,···,a_k)，其中1≤c_i≤k，d_i∈{−1,1}。小C将会不断重复这个路线，直到他走出了场地的范围才结束一天的计划。（即走完第n步后，若小C还在场内，他将回到第1步从头再走一遍）。
    小C对自己的速度非常有自信，所以他并不在意具体耗费的时间，他只想知道P天之后，他一共刷出了多少步微信步数。请你帮他算一算。

    第一行两个用单个空格分隔的整数n，k。分别表示路线步数与场地维数。
    接下来一行k个用单个空格分隔的整数w_i，表示场地大小。
    接下来n行每行两个用单个空格分隔的整数c_i，d_i，依次表示每一步的方向，具体意义见题目描述。

    仅一行一个整数表示答案。答案可能很大，你只需要输出其对10⁹+7取模后的值。
    若小C的计划会使得他在某一天在场地中永远走不出来，则输出一行一个整数-1。

【样例1解释】
    从(1,1)出发将走2步，从(1,2)出发将走4步，从(1,3)出发将走4步。
    从(2,1)出发将走2步，从(2,2)出发将走3步，从(2,3)出发将走3步。
    从(3,1)出发将走1步，从(3,2)出发将走1步，从(3,3)出发将走1步。
    共计21步。

NOIP