Migrated from Lutece 2414 第四章：不要停下来啊！！！！

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

上一集：上一集

第四章：不要停下来啊！！！！

「啊！」一团代码能量向糖袭来。

为了救 Vingying ，显然不可能从正门进入监狱。而潜入监狱可能会遭遇各种各样的代码陷阱（bug）。如果稍没注意就可能被 bug 击中，轻则影响码力运行，重则直接封印码力（指编译失败）。而糖和狗在决定潜入之后，便遭到了 bug 的攻击。

正在这时，一道天蓝的码力从侧翼出现，与 bug 略作纠缠，随即一口吃下 bug ，然后以一种外人无法理解的神奇技法把 bug 消除了。

「什么人，为什么在监狱里胡乱走动。」 一个修长的身影显现。身影周围的码力厚度虽然不是很足，但是却有一股海蓝的气息，而他发出的码力波，则略带天蓝的味道。

在代码大陆上，普通人穷尽一身，也只能服从于标准的代码风格。在标准风格下，所有的码力都会是统一的乳白色。人们的力量只能通过白色的浓郁程度来比较。而纯白色的码力是有其极限的。在某些情况下，一些达到高等境界的人，会进化出自己的代码风格。代码风格根据人的不同，会显现出不同的颜色。但是无一例外，都是越深的颜色越强。现如今这位青年仅仅只用码力的浅色部分便可以成功化解 bug 。难以想象假如用上全部码力将会有多么强悍。

修长的身影缓缓走动，站立到糖的面前，右手轻托糖的下巴：「还是个标致的美人，说吧，根据你的目的，我可能不介意帮你。」

糖被猝不及防的攻势惊得愣住了，而后又突然反应过来，连忙后退三小步。捂着自己羞红的脸，略微低下头，看着青年说：“我只是来救一个人。”

「哦，我叫 Macaron_lin ，不介意的话可以叫我马，我是这里的一个小护卫，但是生活太过无聊，我不介意给你带个路。」

「谢...谢谢了。」糖红着脸，脚尖轻轻在地上画着小圈圈。

「那么这位小姐，还有边上这位先生，请这边走。」

糖一听，娇嗔道：「你这么帮我，是不是有什么图谋啊，我可不相信这天下有什么天上掉的馅饼。」

马微微一笑：「我图谋的东西啊，我想想。。。可能是图谋的你吧。」

糖从小到大并未有过情事，一直只是在锻炼码力。没想到此时遇见一个情场高手，顿时乱了方寸。

而此时旁边的狗，虽有点闷闷不乐，但是也在仔细观察，特别是抱持着对马的怀疑。但是眼下权宜之计是跟着马走。

果不其然，一路走来，并没有遇到什么 bug 。三人来到了一个咖啡厅。

「为什么这里会有咖啡厅啊？」 糖的玉指轻碰嘴唇，歪了歪头。在旁人看来甚是可爱，而在狗看来尤其如此。

监狱的看守也是需要休息的嘛。放心我带你们去的地方不会被发现的。

此时的糖早已被迷了魂，全然不在乎可能出现的危险，只顾着跟着马走。

来到咖啡厅，马在自己熟悉的位置坐下。糖刚要坐，马突然发问：

「糖，你，喜欢我吗？」

糖一听，顿时觉得心上小鹿乱撞。虽然只认识了几个小时，但是短短的旅程和从未有过的心跳感觉，让她觉得，自己就想跟他在一起。糖毕竟不是傲娇属性，虽然抿着嘴唇思考了一会，但最终还是：

马看完糖的表态，突然起身，把糖压在身下。手轻轻地摸上了糖的领带。

「不要，不要这么快。。。」糖用手捂住脸，无助地说。但是经验尚浅的她并不知道如何拒绝。

「答应我一件事好吗？」马用略为低沉，又带有些许磁性的嗓音说道。

「什。。什么事？」糖睁着水灵灵的大眼睛，眼角似乎还泛着一点泪花。

「不要去救人了，就这么和我在一起吧，待到这里，永远和我在一起。」马深情款款地说。

「好。。不对！」 糖刚想答应，突然猛地反应过来，因为按理来说，自己应该把救出 Vingying 看得比什么都重的。

「是吗，那可真是可惜了。」 马话音刚落，便打了一个响指。顷刻间，一个矫健的身影从侧翼杀出，直对着躺在马身下的糖。

「危险！！」 狗早有防备，之前看到糖被马压在身下，暗恋糖许久的狗早已经心如刀绞。但是他心里也明白，糖从来就未曾喜欢过自己。他只能默默地祝糖幸福。但是现在不一样了，糖被背叛了，所以他必须要站出来。

袭来的人身旁是淡紫色的码力，码力中隐约蕴含着他的名字，这是只有码力达到一定境界的人才可以看出来的，使用了密码学隐藏的名字。强如现在的糖，也只能勉强看出来，其中的名字是 cjj490168650 。

马笑了笑：「兔，你来解决那个舔狗，我负责牵制住这个少女。我还想好好和她玩玩。」 说罢马上汇集全身蓝色码力，向糖对着糖周身一番洗礼。

而狗这边，一个只有白色码力的人，自然难以抗拒这些已经形成特殊码风的人。眼看着糖被马一点一点侵蚀，自己却无能为力。

「是不是很意外为什么陪了她这么多年，却还不如我吗？」马对着节节败退的狗说。

「为，为什么？」狗强撑着。

「因为，我的码风叫做 面向对象 ，找对象的能力比你不知道高到哪去了。」

「现在好好看看她如何被我蹂躏吧。」

马的码力成功突破了糖的防御，马掐着糖的脖子，而糖动弹不得。

「救命。。」糖有气无力的说。

「你！！！！！！！」

狗的眼中布满血丝，牙把嘴唇咬出了血。正在这时，他突然感到自己浑身充满了力量，他的码力开始拥有了颜色！！！ 翠绿的颜色从他的头顶开始延伸到了全身。

「啊————」他直接以一敌二，守住了后面的糖。

「他居然会有这种力量！！」 兔惊了一下，「我们两人合力才能和他打个平局。」

「可恶！」

可是，事情的发展往往不随着人的想法而变好。这时，从监狱的深处传来慵懒的声音：「你们在干嘛啊，你们怎么还在打啊，你们都不摸鱼的嘛？」

兔马一听这声音，当场从狗身边退开。「参见詹皇。」 来的人虽然没有释放码力，但是肉眼可见他周围的空气都在产生波动，这是只有极为强大的能力才能产生的，直接对空间施加的影响。

「詹皇，詹皇，我好像听过。。。等等，难道是那个 DP 天尊詹皇吗？」狗突然反应过来，因为狗虽然跟着糖学了这么长时间，但是他最擅长的仍然是 DP ，任何学习 DP 的人都不可能不知道詹皇。

詹皇嘴角微微一笑，两掌一合，海量的鲜红色的码力涌了出来。虽然量大，但是却并不显得繁杂，甚至其中还有些许美感。这是只有足够优美的 DP 转移方程才能有的美感。

「无聊。」 詹皇手指一弹，巨量的码力便涌向狗。狗虽然已经进化出了有颜色的码力，但是不出一秒，便倒地不起。

「糖，你知道的，我这个人，不会说什么骚话。我也知道，青梅不敌天降，总有一天你会被别的男人带走。但是，我不后悔，我不后悔做你的舔狗。。。若有来世，请再叫我一声狗吧。。。你将来的路还很长，我是不会停下来的，只要你不停下来，我就会在前方等着你们！」狗喘息着说。

「所以，不要停下来啊....」

「啊——————」糖震惊地看着这一切

随后、、泪流了满面

「为什么。。。为什么。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。」

「能请你们。。。。给我个理由吗？」

詹皇会给出长度为 $n$ 的数字串 $s$ 和 $q$ 组询问。

每组询问给出两个长度均为 $c$ 的数字串 $a$ , $b$ 和一个数 $d$ 。询问对于 $t\in[a,b]$ ，有多少 $t$ 与 $s$ 有长度为 $d$ 的相同子串。

Input

第一行输入一个长度为 $n$ 的数字串 $s$ 第二行输入一个正整数 $q$ 代表询问组数 接下来 $3q$ 行询问 每组询问第一行输入串 $a$ , 第二行输入串 $b$ ，第三行输入正整数 $d$

Output

每行一个数代表这组询问的结果

Samples

31415926535
1
10
29
1

20

02
2
10
19
1
100
100
2

2
0

Constraints

$1\leq n\leq500,1\leq d\leq c\leq50,\sum c\leq200$ 答案对 $10^9+7$ 取模。输入保证 $b$ 在数字意义上大于或等于 $a$ 。 $a$ , $b$ 不含前导 $0$ 。

Note

对于第二个样例的第一次询问的解释：

在 $10$ 到 $19$ 这 $10$ 个数中，有 $10$ 和 $12$ 这两个数，分别存在长度为 $1$ 的子串 $0$ ，$2$ 为 $02$ 的子串。所以答案为 $2$。

Resources

2020 UESTC ICPC Training for String and Search Algorithm