U461898 子串匹配

在一个神秘世界里，有一个名为“字符串之城”的地方。字符串之城以其独特的文字符号而闻名，这里的居民们每天都在研究各种字符串的奥秘。有一天，字符串之城的守护者小V遇到了一个难题：他们需要计算一个字符串 $s$ 中所有长度为 $w$ 的子串在另一个字符串 $t$ 中出现的次数总和。小V不会解决这个难题，为了守护城市，小V向实力高深的你寻求帮助，请你帮帮他。

给定字符串 $s$ 长度为 $n$，字符串 $t$ 长度为 $m$，请你回答在 $s$ 中每个长度为 $w$ 的子串在 $t$ 中出现次数的总和。答案对 $10^9+7$ 取模。

第一行三个整数 依次输入 $n,m,w$ 。 第二行一个字符串 输入 $s$ 。 第三行一个字符串 输入 $t$ 。

一行一个整数 $ans$。

对于 $30\%$ 的数据，$1 \le n,m,w\le 10^4$ 对于 $100\%$ 的数据，$1 \le n,m,w\le 10^6$