给定一个长度为 的正整数序列 。接下来有 次独立查询，第 次查询给出一对下标 ，请你计算区间乘积 并对模数 取模后的结果。

输入描述:

第一行输入两个整数 ，分别表示序列长度与查询数量。第二行输入 个整数 ，表示序列元素。此后 行，第 行输入两个整数 ，表示一次查询的左右端点。

输出描述:

输出一行 个用空格隔开的整数，第 个整数为第 次查询的答案。