题目描述
Rhezo calls a number good if the number is divisible by all numbers from 1 to 9. His father also likes good numbers, and has promised him to buy 1 chocolate per every good number he tells him. He doesn't want to make the task simple for Rhezo, therefore he gives him 2 strings T and P.
He tells Rhezo to find the number of ways to select one or more occurrences of P in T, so that the product of starting positions of all those occurrences is a good number. Rhezo likes chocolates and is not so good at programming. Help him. As the answer could be large, output the answer modulo 10^9+7.
Input:
First line contains the string P. Second line contains the string T.
Output:
Help Rhezo to find the number of ways to select one or more occurrences of P in T, so that the product of starting positions of all those occurrences is a good number.
Constraints:
Length of S, T ≤ 10^4
SAMPLE INPUT
a
aaaaaaa
SAMPLE OUTPUT
4
输入格式
见题面
输出格式
见题面
样例输入
lbvuoyjntdtevbgchbjxykxgwzuqrivcmrzapkpkniokmxovyyuykrfhqzxkkvmwonydxnpmxdzjcneanyzasghkfgurbhppwpuucjiaphlrxsumstmkztvgcpadypvvhrrjdzlshxlgrfsjafubapiceiifzfagwtszsdtbchhtocdphzqjoaoukwzmdbuzwmbpsuswdcssexhnwzymamimkkynltpkfqbzmtwqxokdlrqjsrvuddhqnfdbaslikmhzhfpftzigsbrmsmjxsqnhxtianviajpzrvqyqrgzljqxdfgdzyqgylpyzmgzwvansqllhtmsdcpijyliwepupgsqsaroyrdqhodokpipuaxfylowpftglnxfoqumixeroiiazqpvqobqzpnqwgxjtwohmivwiaqykayjspfjdgbfxovvwseqqszfdxdnxtnhtlsmczxfhykgpiblahdtafyfcbubxhksucewcddleqsvytiabotdtrkxveysnikhmrdqwicayuxwpgxsuqxpkhmhnmzawljicozzxbbvxzsmfrfbjeqvmecbsbeonnyrczqzcuwztqoahvbtztonzrprsthhihzkhrlllkneabgkyhdxcrnbkcufxbmfjnssfffqpsxsvdctnhtragtlknqjreqcsiwzqbrfuoxpubjjieajkvwujofcsvemgalwddbxtbppcaynebwowukhipjamppsraovfquztjqvjrkpsidqcpykgjntzclscapkskjlvbifstukbaberbqykdrlfeeketuwffjbguiznelqgmwypnwaspnattkapgyunivtcfurkghqugqktomndznztzbihzcujaqlhkersoknuczprlcwksxftynbysxhunvbabvsphhjjgaatdzgxwlqvbtvtrengzqgblbqskcetcemhfsgcgxzhsuajypqafybtztlkxpdawrjbmqfspezhybtzqlzxjaqlvextvcvttgvfycxnhwxhzqgpbfpmhhxfluyjwvcsbzxccvpltostebkhgbuqjtvuqvfmqiethevlbnwwbrriscrafnqohllxgqlyassiwpvxcsvgjnqdrhdwvulehydqoqopiizgaufeobkzoccfkgdhconlmsbdiqutavzarfhgithwwkdisgpwxehlwjqgbkzdfbgzinfqgmoeytmszdqyhakflaomnnrsqztymyqvneznxmizpaxzahglkuzxkrraqlzflpcawbotpyuhysgzbmknjkktdetvpsaakcbggrbvpycpskovzbjilvbqzulopmrbquhynkuekytcjiyijhswctmenxuelnfehocwzyajxuoiemspvklzdzdsyyxklcqvrstsrudqqryufqlaayafxfxvduhrzxosshkjdpbthzporaptapyxuvvasettejlwqxhwoipxjhmajbtksrhooeoijjbnsollnshccwzlfllpogzgzivnnlyyvbnpqyafshjugjhlwucnabtzkqozemzbomqgkrneaxyiihwebyrdancmfsnjfmkvaddmwqqwnqhvxdcabvddifrozezeskbspeelxujkmqijtkjvfmyqtsetwfzrpdjehqrgmbrzrbkllwiskiigaobxwcqlfbsprjvgkmheptrapzvahfiiwjhslxfryxisjdyvshbhaskqrfszmajilqcynirnhzfqdfovmpeniofzvxaizjsmzvkodccmbjfeptbbkgquwvusuwctiufjpqyuuchvnmcchfgrnymkuieoggkoapyshymdctzphduoiaiwywiugmjmuvbumboubbxdwyugbowmqeirasligwvaryuebjacmzhkabqbsnpirxzurncxlzxdxujaflcrkldmnuqfhfpafrwwebupatuanfauqfldqrpflfmslcuqvrozskquenursxmjczmuqdcdjovwssonjcmdnfxt
ailbvuoyjntdtevbgchbjxykxgwzuqrivcmrzapkpkniokmxovyyuykrfhqzxkkvmwonydxnpmxdzjcneanyzasghkfgurbhppwpuucjiaphlrxsumstmkztvgcpadypvvhrrjdzlshxlgrfsjafubapiceiifzfagwtszsdtbchhtocdphzqjoaoukwzmdbuzwmbpsuswdcssexhnwzymamimkkynltpkfqbzmtwqxokdlrqjsrvuddhqnfdbaslikmhzhfpftzigsbrmsmjxsqnhxtianviajpzrvqyqrgzljqxdfgdzyqgylpyzmgzwvansqllhtmsdcpijyliwepupgsqsaroyrdqhodokpipuaxfylowpftglnxfoqumixeroiiazqpvqobqzpnqwgxjtwohmivwiaqykayjspfjdgbfxovvwseqqszfdxdnxtnhtlsmczxfhykgpiblahdtafyfcbubxhksucewcddleqsvytiabotdtrkxveysnikhmrdqwicayuxwpgxsuqxpkhmhnmzawljicozzxbbvxzsmfrfbjeqvmecbsbeonnyrczqzcuwztqoahvbtztonzrprsthhihzkhrlllkneabgkyhdxcrnbkcufxbmfjnssfffqpsxsvdctnhtragtlknqjreqcsiwzqbrfuoxpubjjieajkvwujofcsvemgalwddbxtbppcaynebwowukhipjamppsraovfquztjqvjrkpsidqcpykgjntzclscapkskjlvbifstukbaberbqykdrlfeeketuwffjbguiznelqgmwypnwaspnattkapgyunivtcfurkghqugqktomndznztzbihzcujaqlhkersoknuczprlcwksxftynbysxhunvbabvsphhjjgaatdzgxwlqvbtvtrengzqgblbqskcetcemhfsgcgxzhsuajypqafybtztlkxpdawrjbmqfspezhybtzqlzxjaqlvextvcvttgvfycxnhwxhzqgpbfpmhhxfluyjwvcsbzxccvpltostebkhgbuqjtvuqvfmqiethevlbnwwbrriscrafnqohllxgqlyassiwpvxcsvgjnqdrhdwvulehydqoqopiizgaufeobkzoccfkgdhconlmsbdiqutavzarfhgithwwkdisgpwxehlwjqgbkzdfbgzinfqgmoeytmszdqyhakflaomnnrsqztymyqvneznxmizpaxzahglkuzxkrraqlzflpcawbotpyuhysgzbmknjkktdetvpsaakcbggrbvpycpskovzbjilvbqzulopmrbquhynkuekytcjiyijhswctmenxuelnfehocwzyajxuoiemspvklzdzdsyyxklcqvrstsrudqqryufqlaayafxfxvduhrzxosshkjdpbthzporaptapyxuvvasettejlwqxhwoipxjhmajbtksrhooeoijjbnsollnshccwzlfllpogzgzivnnlyyvbnpqyafshjugjhlwucnabtzkqozemzbomqgkrneaxyiihwebyrdancmfsnjfmkvaddmwqqwnqhvxdcabvddifrozezeskbspeelxujkmqijtkjvfmyqtsetwfzrpdjehqrgmbrzrbkllwiskiigaobxwcqlfbsprjvgkmheptrapzvahfiiwjhslxfryxisjdyvshbhaskqrfszmajilqcynirnhzfqdfovmpeniofzvxaizjsmzvkodccmbjfeptbbkgquwvusuwctiufjpqyuuchvnmcchfgrnymkuieoggkoapyshymdctzphduoiaiwywiugmjmuvbumboubbxdwyugbowmqeirasligwvaryuebjacmzhkabqbsnpirxzurncxlzxdxujaflcrkldmnuqfhfpafrwwebupatuanfauqfldqrpflfmslcuqvrozskquenursxmjczmuqdcdjovwssonjcmdnfxtnwoumwkohhyzaeagrjnadtditdzehbmwadrmbdcilajnflvwviylbvuoyjntdtevbgchbjxykxgwzuqrivcmrzapkpkniokmxovyyuykrfhqzxkkvmwonydxnpmxdzjcneanyzasghkfgurbhppwpuucjiaphlrxsumstmkztvgcpadypvvhrrjdzlshxlgrfsjafubapiceiifzfagwtszsdtbchhtocdphzqjoaoukwzmdbuzwmbpsuswdcssexhnwzymamimkkynltpkfqbzmtwqxokdlrqjsrvuddhqnfdbaslikmhzhfpftzigsbrmsmjxsqnhxtianviajpzrvqyqrgzljqxdfgdzyqgylpyzmgzwvansqllhtmsdcpijyliwepupgsqsaroyrdqhodokpipuaxfylowpftglnxfoqumixeroiiazqpvqobqzpnqwgxjtwohmivwiaqykayjspfjdgbfxovvwseqqszfdxdnxtnhtlsmczxfhykgpiblahdtafyfcbubxhksucewcddleqsvytiabotdtrkxveysnikhmrdqwicayuxwpgxsuqxpkhmhnmzawljicozzxbbvxzsmfrfbjeqvmecbsbeonnyrczqzcuwztqoahvbtztonzrprsthhihzkhrlllkneabgkyhdxcrnbkcufxbmfjnssfffqpsxsvdctnhtragtlknqjreqcsiwzqbrfuoxpubjjieajkvwujofcsvemgalwddbxtbppcaynebwowukhipjamppsraovfquztjqvjrkpsidqcpykgjntzclscapkskjlvbifstukbaberbqykdrlfeeketuwffjbguiznelqgmwypnwaspnattkapgyunivtcfurkghqugqktomndznztzbihzcujaqlhkersoknuczprlcwksxftynbysxhunvbabvsphhjjgaatdzgxwlqvbtvtrengzqgblbqskcetcemhfsgcgxzhsuajypqafybtztlkxpdawrjbmqfspezhybtzqlzxjaqlvextvcvttgvfycxnhwxhzqgpbfpmhhxfluyjwvcsbzxccvpltostebkhgbuqjtvuqvfmqiethevlbnwwbrriscrafnqohllxgqlyassiwpvxcsvgjnqdrhdwvulehydqoqopiizgaufeobkzoccfkgdhconlmsbdiqutavzarfhgithwwkdisgpwxehlwjqgbkzdfbgzinfqgmoeytmszdqyhakflaomnnrsqztymyqvneznxmizpaxzahglkuzxkrraqlzflpcawbotpyuhysgzbmknjkktdetvpsaakcbggrbvpycpskovzbjilvbqzulopmrbquhynkuekytcjiyijhswctmenxuelnfehocwzyajxuoiemspvklzdzdsyyxklcqvrstsrudqqryufqlaayafxfxvduhrzxosshkjdpbthzporaptapyxuvvasettejlwqxhwoipxjhmajbtksrhooeoijjbnsollnshccwzlfllpogzgzivnnlyyvbnpqyafshjugjhlwucnabtzkqozemzbomqgkrneaxyiihwebyrdancmfsnjfmkvaddmwqqwnqhvxdcabvddifrozezeskbspeelxujkmqijtkjvfmyqtsetwfzrpdjehqrgmbrzrbkllwiskiigaobxwcqlfbsprjvgkmheptrapzvahfiiwjhslxfryxisjdyvshbhaskqrfszmajilqcynirnhzfqdfovmpeniofzvxaizjsmzvkodccmbjfeptbbkgquwvusuwctiufjpqyuuchvnmcchfgrnymkuieoggkoapyshymdctzphduoiaiwywiugmjmuvbumboubbxdwyugbowmqeirasligwvaryuebjacmzhkabqbsnpirxzurncxlzxdxujaflcrkldmnuqfhfpafrwwebupatuanfauqfldqrpflfmslcuqvrozskquenursxmjczmuqdcdjovwssonjcmdnfxtabbjwhkaomplmseytlbvuoyjntdtevbgchbjxykxgwzuqrivcmrzapkpkniokmxovyyuykrfhqzxkkvmwonydxnpmxdzjcneanyzasghkfgurbhppwpuucjiaphlrxsumstmkztvgcpadypvvhrrjdzlshxlgrfsjafubapiceiifzfagwtszsdtbchhtocdphzqjoaoukwzmdbuzwmbpsuswdcssexhnwzymamimkkynltpkfqbzmtwqxokdlrqjsrvuddhqnfdbaslikmhzhfpftzigsbrmsmjxsqnhxtianviajpzrvqyqrgzljqxdfgdzyqgylpyzmgzwvansqllhtmsdcpijyliwepupgsqsaroyrdqhodokpipuaxfylowpftglnxfoqumixeroiiazqpvqobqzpnqwgxjtwohmivwiaqykayjspfjdgbfxovvwseqqszfdxdnxtnhtlsmczxfhykgpiblahdtafyfcbubxhksucewcddleqsvytiabotdtrkxveysnikhmrdqwicayuxwpgxsuqxpkhmhnmzawljicozzxbbvxzsmfrfbjeqvmecbsbeonnyrczqzcuwztqoahvbtztonzrprsthhihzkhrlllkneabgkyhdxcrnbkcufxbmfjnssfffqpsxsvdctnhtragtlknqjreqcsiwzqbrfuoxpubjjieajkvwujofcsvemgalwddbxtbppcaynebwowukhipjamppsraovfquztjqvjrkpsidqcpykgjntzclscapkskjlvbifstukbaberbqykdrlfeeketuwffjbguiznelqgmwypnwaspnattkapgyunivtcfurkghqugqktomndznztzbihzcujaqlhkersoknuczprlcwksxftynbysxhunvbabvsphhjjgaatdzgxwlqvbtvtrengzqgblbqskcetcemhfsgcgxzhsuajypqafybtztlkxpdawrjbmqfspezhybtzqlzxjaqlvextvcvttgvfycxnhwxhzqgpbfpmhhxfluyjwvcsbzxccvpltostebkhgbuqjtvuqvfmqiethevlbnwwbrriscrafnqohllxgqlyassiwpvxcsvgjnqdrhdwvulehydqoqopiizgaufeobkzoccfkgdhconlmsbdiqutavzarfhgithwwkdisgpwxehlwjqgbkzdfbgzinfqgmoeytmszdqyhakflaomnnrsqztymyqvneznxmizpaxzahglkuzxkrraqlzflpcawbotpyuhysgzbmknjkktdetvpsaakcbggrbvpycpskovzbjilvbqzulopmrbquhynkuekytcjiyijhswctmenxuelnfehocwzyajxuoiemspvklzdzdsyyxklcqvrstsrudqqryufqlaayafxfxvduhrzxosshkjdpbthzporaptapyxuvvasettejlwqxhwoipxjhmajbtksrhooeoijjbnsollnshccwzlfllpogzgzivnnlyyvbnpqyafshjugjhlwucnabtzkqozemzbomqgkrneaxyiihwebyrdancmfsnjfmkvaddmwqqwnqhvxdcabvddifrozezeskbspeelxujkmqijtkjvfmyqtsetwfzrpdjehqrgmbrzrbkllwiskiigaobxwcqlfbsprjvgkmheptrapzvahfiiwjhslxfryxisjdyvshbhaskqrfszmajilqcynirnhzfqdfovmpeniofzvxaizjsmzvkodccmbjfeptbbkgquwvusuwctiufjpqyuuchvnmcchfgrnymkuieoggkoapyshymdctzphduoiaiwywiugmjmuvbumboubbxdwyugbowmqeirasligwvaryuebjacmzhkabqbsnpirxzurncxlzxdxujaflcrkldmnuqfhfpafrwwebupatuanfauqfldqrpflfmslcuqvrozskquenursxmjczmuqdcdjovwssonjcmdnfxthadsdmhlbvuoyjntdtevbgchbjxykxgwzuqrivcmrzapkpkniokmxovyyuykrfhqzxkkvmwonydxnpmxdzjcneanyzasghkfgurbhppwpuucjiaphlrxsumstmkztvgcpadypvvhrrjdzlshxlgrfsjafubapiceiifzfagwtszsdtbchhtocdphzqjoaoukwzmdbuzwmbpsuswdcssexhnwzymamimkkynltpkfqbzmtwqxokdlrqjsrvuddhqnfdbaslikmhzhfpftzigsbrmsmjxsqnhxtianviajpzrvqyqrgzljqxdfgdzyqgylpyzmgzwvansqllhtmsdcpijyliwepupgsqsaroyrdqhodokpipuaxfylowpftglnxfoqumixeroiiazqpvqobqzpnqwgxjtwohmivwiaqykayjspfjdgbfxovvwseqqszfdxdnxtnhtlsmczxfhykgpiblahdtafyfcbubxhksucewcddleqsvytiabotdtrkxveysnikhmrdqwicayuxwpgxsuqxpkhmhnmzawljicozzxbbvxzsmfrfbjeqvmecbsbeonnyrczqzcuwztqoahvbtztonzrprsthhihzkhrlllkneabgkyhdxcrnbkcufxbmfjnssfffqpsxsvdctnhtragtlknqjreqcsiwzqbrfuoxpubjjieajkvwujofcsvemgalwddbxtbppcaynebwowukhipjamppsraovfquztjqvjrkpsidqcpykgjntzclscapkskjlvbifstukbaberbqykdrlfeeketuwffjbguiznelqgmwypnwaspnattkapgyunivtcfurkghqugqktomndznztzbihzcujaqlhkersoknuczprlcwksxftynbysxhunvbabvsphhjjgaatdzgxwlqvbtvtrengzqgblbqskcetcemhfsgcgxzhsuajypqafybtztlkxpdawrjbmqfspezhybtzqlzxjaqlvextvcvttgvfycxnhwxhzqgpbfpmhhxfluyjwvcsbzxccvpltostebkhgbuqjtvuqvfmqiethevlbnwwbrriscrafnqohllxgqlyassiwpvxcsvgjnqdrhdwvulehydqoqopiizgaufeobkzoccfkgdhconlmsbdiqutavzarfhgithwwkdisgpwxehlwjqgbkzdfbgzinfqgmoeytmszdqyhakflaomnnrsqztymyqvneznxmizpaxzahglkuzxkrraqlzflpcawbotpyuhysgzbmknjkktdetvpsaakcbggrbvpycpskovzbjilvbqzulopmrbquhynkuekytcjiyijhswctmenxuelnfehocwzyajxuoiemspvklzdzdsyyxklcqvrstsrudqqryufqlaayafxfxvduhrzxosshkjdpbthzporaptapyxuvvasettejlwqxhwoipxjhmajbtksrhooeoijjbnsollnshccwzlfllpogzgzivnnlyyvbnpqyafshjugjhlwucnabtzkqozemzbomqgkrneaxyiihwebyrdancmfsnjfmkvaddmwqqwnqhvxdcabvddifrozezeskbspeelxujkmqijtkjvfmyqtsetwfzrpdjehqrgmbrzrbkllwiskiigaobxwcqlfbsprjvgkmheptrapzvahfiiwjhslxfryxisjdyvshbhaskqrfszmajilqcynirnhzfqdfovmpeniofzvxaizjsmzvkodccmbjfeptbbkgquwvusuwctiufjpqyuuchvnmcchfgrnymkuieoggkoapyshymdctzphduoiaiwywiugmjmuvbumboubbxdwyugbowmqeirasligwvaryuebjacmzhkabqbsnpirxzurncxlzxdxujaflcrkldmnuqfhfpafrwwebupatuanfauqfldqrpflfmslcuqvrozskquenursxmjczmuqdcdjovwssonjcmdnfxtiycgvkexnfikmtkbfzmtrstmzvpuyebgeemboqycyhmkaynhybcrtvgtqxnpbovhskijahlaqzlsxybvadptyvoqsbfwqddknmtpvgslfdfddgadjrzjmpzhrhdjkgtzspqpviabnhgrniwyaxhonhveoypahibbxrrvctwpbciqmfpmewbrfyxtzmvgxwjwqaruwnlzrupgbesfbvzgwwcvlxdiwmgmpygnnrmhnbnoihwlfvtbrvyevbmrptfetntggfnwjcktkgepdxsxtqbqrqjglqnefimlochzeusqcwfgvxdqngggwrphhenmmaaccjbidvzitgopgthvzoeyhtfrxvfjvfozprjunicirszxlhunxylersvqnbckiqlzhvwwdyfwtgtgnqtmogrgzoyorazcqkbyhzwlabjtidzxtvkjddrctqtnqupjgshosfzshinrnoqijcupflrbbmougfdnzmbrrclamatcpkmamgpusjvvvlpeqsrpeujywwyizsmqezqqfimxtjvqwkumfnejhphfniqmaceebxwjfjiaudqronftclekcorqwjewmjcpgyynjhnemfxascvvqahsoakmkpiyaknikoxuxmajrxmmbhjrjsmzswlenvcpfqxsgwmdkomelyqoibirturnqcseyutfmtxsrlxczmgmmybuzlouffjxjdbjaxpmsohjcgnbsvqftrbuepqjuaggdkpdjesbvbmxhcacxqhrjklnaewwefcjpupyajbvkpstrtvplegvptirxfpdmupboebopekzteslzqaluigjdoadvqijkxmadnostatnfoygearykzkpqksncdxoajogzdasdufkifrohkmrmwhcjbpneochaspzxptbjzntgghotuhfsohdsyrypthpnwqlmjmvibrriyfbumindrqvrjvgcdxqznblxpjhscycadfvsnkxecuwmpeqsciurlhocswvuuxvadsuserxglvucbnvfvrxhyljrjgnegigjcabgtapexjgbwdguuddvrooavbgbmmmoopvhsmnpxuqwzzqwctrvjhweichurtjflgndscupwllymduoynmiuioemwzdrklcsyhmccdbppzbuvrtkddenrkaplfjvqnpqvbtxfuowtpsqilamqgbkqbzchkzzyrqtsjszdivyzoqhbqvuwxeoafsjqujolzjfidhnlcnksdrwtpsrmwhobcytwhhjisqsvxficuswxmusdmlpiudmwdfumpfujwmfvtpznkwmwsezfrqpmvdkblfnakijiwqgqgfdqdsoyypdqhueeyofjvtlidwqzpypvgvnlndjlsodbjhfjylutghbjduissypatemijxtdmzexgkigxcadldmqxujsuauphgxqetussyrakzhjdjmomaemvpgrsahbhetnxnhroysazbkemyuazamwqsnkvuncbgryuaskamkbpwfbvzbuzqqridddaqhbxabtctfcfrfuokxjlzfnpxezakfccodbrfutabyitdehqcsbdzouwvtyfabjpelglfbojzycfclvgfwjendakzyrbzasglattcjcdheikrfswecarhcbiaumcu
样例输出
143328