杭师大特别特别好 2535
Description
（摄影：谭洁）
汤姆来到了美丽的杭师大，当汤姆漫步在杭师大的校园中时，他听闻正有人在宣讲着杭师大的历史，杭州师范大学，百十年办学，弘文励教，青蓝相继，学校秉承“勤慎诚恕，博雅精进”的校训精神，弘扬“人文学堂，艺术校园”的办学特色，顺应创新创业教育的时代指向，不断深化教育教学改革。学校系教育部卓越教师培养计划改革项目实施单位、国家级大学生创新创业训练计划地方实施高校、全国创新创业典型经验高校、教育部首批深化创新创业教育改革示范高校，浙江省重点建设高校、浙江省双创示范基地。
聆听到这段演讲时，汤姆听到了许多女生的呼喊声，汤姆心中有点羡慕，“凭什么，我也很有才华的，掌握核心技术才会具有魅力。”汤姆作为一个密码学爱好者，他知道在随着数字广播电视，网络媒体的兴起，数字编解码及压缩技术在迅速的进步，这是一波技术的浪潮，因此他花费了很多时间去熟练的掌握了许多常见的编码解码方式，在汤姆的眼中，任何事物都可以变成一段编码，当杭师大这么多女生面前，单身的他也想展现一下自己的才华，就在此时，他听闻学校正在举办一个密室探险活动，规则如下：在n*m的房间中，你需要根据自己行走的步骤来模拟行走，并获取一定的幸运值。最后的幸运值作为自己的成绩。每个人起始都位于（0，0）点，幸运值为0.在n*m的房间中，每个房间可能存在一种编码或者不存在。(0,0)点肯定不存在编码。 每个编码都代表着一定幸运值。由于需要考验一下智商，所以编码都进行了加密，所以编码需解码。编码只由四种字母组成，分别为“h”“z”“n”“u”，而且现在我们规定存在一个“总串”S（起始为空），每次操作，我们会在这个“总串”S后加上该次操作的编码。解码的格式如下： 首先，我们需要了解一种01序列 :0，1，00，01，10，11，000，001，010，011，100，101，110，111，0000，0001，...,1110,1111,00000....，第一个是0，第二个是1，第三个是01......依次递推。如果我们得到的编码长度为u。则h代表第（u）个上述01序列，z代表第（u+1）个上述01序列，n代表第（u+2）个上述01序列，u代表第（u+3）个上述01序列。我们只需要对编码相应的字符用对应的01串代替。这样我们就可以得到一串相应编码的01串。 幸运值：如果该01串是一个回文串，则该编码的幸运值为0，否则幸运值为该01串对应的二进制编码的十进制值。 特殊操作：如果总串中存在“hznu”字符串，则进行删除“hznu”操作，直到该“总串”中不存在“hznu”，此时我们将幸运值变为删除的次数+1倍.（即在加上该房间的幸运值后，再将幸运值乘上K+1，K为删除操作的次数）。 如此时总串为“hhhhzhznunu”，则需要进行两次操作（第一次为删除中间的hznu，然后总串变为了”hhhhznu”,再删除“hznu”,总串变为了“hhh”，此时不存在“hznu”停止操作，并且将幸运值乘上3）。更特殊的是，汤姆比较讨厌素数（素数的定义为除1和自己本身之外没有其他因子） 。 规定如果在行走过程中：设幸运值为uk（进行完一个房间的所有操作后的幸运值），n=uk mod 100007. 若n为素数，汤姆会将自己当前的幸运值变为0.
汤姆构想的行走的步骤输入格式如下 ：包含两个字符串，由空格相隔。第一个字符串包括“left”，”up”,”down”,”right”. 代表走的方向。 第二个字符串由“0”-“9”组成 ， 代表走的步数。如“left 1”代表向左走一格，“up 03”代表向上走三格 （不存在走零格的操作）。 汤姆不想单身，他想在这么好的学校，这么多的女生面前展示一下自己，所以汤姆想知道根据自己的步骤能获得多少幸运值，请你输出最后汤姆获得的幸运值（最后结果可能很大，所以答案取模100007）。
Input
第一行输入n,m,k，0<n<100,0<m<100,0<=k<=n*m-1，n，m代表房间的行数和列数，k代表存在k个有编码的房间
然后输入n行，每行有m个字符分别为‘.’或者‘r’。 （r）代表这个房间有编码，(.)代表这个房间为空
然后输入k行
每行为一个非空字符串（字符数不超过100）（从左到右，从上到下的含编码的房间顺序输入编码）。
然后输入一个数字q(0<=q<100)，代表有q个行走步骤
接下来的q行，每行有两个非空字符串 (保证不会走到n*m的房间范围之外）
Output
输出最后的幸运值，答案取模100007.
Samples