ZZPERM  ZigZag Permutation
In the following we will deal with nonempty words consists only of lower case letters 'a','b',..., 'j' and we will use the natural 'a' < 'b' < ... < 'j' ordering. Your task is to write a program that generates almost all zigzag words (zigzag permutations) from a given collection of letters. We say that a word W=W(1)W(2)...W(n) is zigzag iff n = 1 or W(i) > W(i+1) and W(j) < W(j+1) for all odd 0 < i < n and for all even 0 < j < n or W(i) > W(i+1) and W(j) < W(j+1) for all even 0 < i < n and for all odd 0 < j < n. For example: "aabcc" is not zigzag, "acacb" is zigzag, "cac" is zigzag, "abababc" is not zigzag. If you imagine all possible zigzag permutations of a word in increasing lexicographic order, you can assign a serial number (rank) to each one. For example: the word "aabcc" generates the sequence: 1 <> "acacb", 2 <> "acbca", 3 <> "bacac", 4 <> "bcaca", 5 <> "cabac", 6 <> "cacab".
Input
The input file consists several test cases. Each case contains a word (W) not longer than 64 letters and one positive number (D). The letters of each word are in increasing order. Input terminated by EOF.
Output
For each case in the input file, the output file must contain all of the zigzag permutations of W whose zigzag serial is divisible by D, in increasing lexicographic order  one word per line. In the next line you have to print the total number of zigzag permutations of W. There is no case that produces more than 365 lines of output. Print an empty line after each case.
Example
Input: j 1 abc 2 aaabc 1 aaabb 2 aaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbcccdd 123456 Output: j 1 bac cab 4 abaca acaba 2 1 babacbcabacabadabababababababababadab 213216
hide comments
Min_25:
20140506 12:39:32
Some test cases have extra spaces at the end of the line. Last edit: 20140506 14:36:17 

Voyage:
20120523 00:21:50
Is BigInteger required for calculations? Plus, what's the limit of D?

Added by:  Noszi 
Date:  20050505 
Time limit:  1.516s 
Source limit:  12345B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Folklore 