牛牛有一个长度为的数组，牛妹给出个询问，询问有种类型： :询问区间内有多少子序列的乘积为奇数 :询问区间内有多少子序列的乘积为偶数 某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

输入描述:

第一行个整数,表示数组长度和询问个数。接下来一行给出个空格隔开的数。接下来行每行三个整数表示操作类型。。

输出描述:

输出行，每行表示对应询问的答案，因为答案可能很大，输出对取模的结果。