Description

有一个整数序列A[]，长度为N，标号为1~N，初始值全部为1。

现有两种操作：

m i x ：给A[i]乘上一个数x。(0 < x < 50)

q a b ：计算（A[a],A[a+1],...,A[b]）的最小公倍数。答案模10007。(a <= b)

数据保证A[i]在计算过程中可能会暴long long :)

Input

多组数据；每组数据第一行两个整数N和Q，表示序列长度为N，操作数目是Q。(1<=N, Q<=10000). 然后是Q行，每行一个操作。

Output

首先输出case数，见样例。 然后每个q的操作输出结果。答案模10007。

Sample

Input

4 5
q 1 4
m 2 5
q 2 3
m 4 7
q 2 4

10 10
m 6 45
q 5 8
m 8 2
m 8 31
m 4 23
q 3 8
q 5 6
q 2 5
m 10 22
m 8 14

Output

Case 1:
1
5
35
Case 2:
45
4128
45
23

Source: zjut_DD