SP11946 ZZPERM2 - Zig-Zag Permutation 2

请参阅 [ZZPERM](../ZZPERM/) 问题描述。这是该问题的一个改进版本，并且包含更具挑战性的测试用例。

输入最多包含 15 组测试数据。每组测试数据由一个由字母按字典序排列的单词 $W$ 和一个正整数 $D$（其中 $D \leq 1000000000$）组成。单词 $W$ 的长度不超过 64 个字符。输入以文件结尾（EOF）结束。

对于每组数据，输出每个能够被 $D$ 整除的、按字典序递增排列的 $W$ 的“zig-zag”排列。每行输出一个排列单词。接下来的一行，输出 $W$ 的所有可能“zig-zag”排列的总数。任何一组数据的输出行数不会超过 365 行。每组数据输出完毕后，请输出一个空行。 **本翻译由 AI 自动生成**