当前没有测试数据。

华华和秀秀在玩游戏。在他们面前有!个球排成一排，从左到右按 1 到!编号。每个球有一 个可正可负的权值。 每一轮， 秀秀会选定一个区间[#,%]， 将编号在这个区间内的所有球的权值 加上一个值'， 或者将编号在这个区间内的所有球的权值都设为其相反数。 华华则需从这!个球 中选出(个球来，他的得分为这(个球的权值的乘积。 华华每次都能快快地找出得分最优的选球方案来。秀秀想了想，决定提升游戏难度。她每 次会选定一个区间[#,%]，然后询问华华在这个区间内选出((1 ≤ ( ≤ 10)个球的所有方案的得 分之和。 这下可把华华难倒了，于是华华找到了聪明的你。你能帮帮他嘛？ 由于所有方案的得分之和可能很大，你只需要输出得分之和对1000000007(10 / + 7)取模 的结果（负数请加上10 / + 7变成非负数）即可。 【输入格式】 从文件 game.in 中读入数据。 输入第一行包含两个正整数!,1，分别表示球的个数和秀秀的操作条数。 接下来一行包含!个空格隔开的整数，表示每个球初始的权值。 接下来1行，每行表示秀秀的一个操作。 若该行形如“1 # % '”，则表示秀秀将编号属于[#,%]的所有球的权值都加上了'； 若该行形如“2 # %”，则表示秀秀将编号属于[#,%]的所有球的权值都置为了其相反数； 若该行形如“3 # % (”，则表示华华需要回答从[#,%]中选出(个球的所有取球方案的得分之 和。 【输出格式】 输出文件到 game.out 中。 对于秀秀宝宝的每一个询问操作，输出一行，表示该询问的答案。 【样例输入】 10 9 3 6 7 4 6 1 6 7 2 6 3 5 7 3 1 1 7 -9 1 2 3 5 3 2 6 1 2 5 8 3 5 7 3 2 2 3 3 1 10 2 3 1 2 2 【样例输出】 36 999999996 72 999999885 12 【样例说明】 第一个询问：6×1×6 = 36 第二个询问： 询问前各个球的权值为：-6 2 3 -5 -3 -8 -3 7 2 6 2 + 3 + −5 + −3 + −8 = −11 −11 + (10 / + 7) = 999999996 第三个询问： 询问前各个球的权值为：-6 2 3 -5 3 8 3 7 2 6 3×8×3 = 72