本蒟蒻看到这题时第一反应就是容斥再加一个KMP判重，打完后就寄了，因为其实仔细想想不难发现容斥需要处理多个段交叉，多个段不交叉，交叉中可能还会交叉，求组合数时还要用到拓展Lucas定理（因为模数不一定为质数），用容斥效率也会很低