[Description]

Kroulis君是MZOI 2012级的信奥班成员。以喜欢搞各种工程出名。

Gemini君送给Kroulis君一个活动的乘法表(p.s. Gemini君小时候真的有过这样一个乘法表),它的结构是这样的。

首先,是一张硬纸板,上面有9x18的方格:

还有一个纸套,上面有两个9x1的孔,纸套看起来是这样的:

把纸板放进纸套里,使之能够左右自由滑动,这个活动的乘法表就做好了,使用时把某一列对准左面的孔,就能从右面的孔里读出答案,比如第5列对准左面的孔的时候是这样的:

一天,无聊的Kroulis君在一条悠长悠长又寂寥的纸带上抄写了一遍硬纸板上的内容,发现这条纸带刚好可以配合纸套使用。但是当他把第10列对准左面的孔的时候,惊奇地发现右面的孔里是一片空白(九九乘法表本来就只有九列,第10列当然对应空列啦~)。患有强迫症的Kroulis君立马把答案填了出来:

高兴的Kroulis君把纸带向左拉了一个单位,发现第11列对应的也是空列,于是他又把答案填了出来。下面的事大家应该能想出来了,对,Kroulis君一直往右填,填了整整一下午,于是纸带变成了这样:

Kroulis君拿着这条悠长悠长又寂寥的纸带找到了你,要你帮忙解决以下两个问题(行和列的编号均从1开始):

  1. 第i行,第j列(坐标为(i,j))的数字是多少;
  2. 从(i,j)到(m,n)这个子矩阵的和是多少。

当然,由于答案可能很大,所以请输出答案对10007取模的结果。

另外,由于Kroulis君的变♂态心理,所有数字(除了x)均以三进制方式给出(我也不知道为什么)。

 

[Input]

第一行一个整数x,表示询问的是哪个问题;

如果x = 1,第二行两个三进制整数i, j;否则第二行四个三进制整数i, j, m, n。

 

[Output]

一行一个十进制整数,为答案对10007取模后的结果。

 

来源

原创