SP11946 ZZPERM2 - Zig-Zag Permutation 2

See [ZZPERM](../ZZPERM/) problem description. This an improved version with more demanding test cases.

The input consists of at most 15 test cases. Each case contains a word (W) not longer than 64 letters and one positive number (D

For each case output all of the zig-zag permutations of W whose rank is divisible by D, in increasing lexicographic order, one word per line. In the next line print the total number of zig-zag permutations of W. There is no case that produces more than 365 lines of output. Print an empty line after each case.