#include <iostream>
#include <cstring>
using namespace std;

class PatternGenerator2Exception {};

class PatternGenerator2
{
private:
	int *_src;
	int *_flag;
	int *_indexes;
	int *_list;
	int _srcsize;
	int _len;
	int _count;
	PatternGenerator2(int srcsize, int len, int c) 
				: _srcsize(srcsize), _len(len), _count(c) {

		if (_srcsize < 2 || _len < 2 || _srcsize < _len) {
			throw PatternGenerator2Exception();
		}		
		_src = new int[_srcsize];
		_flag = new int[_srcsize];

		_list = new int[_len];
		_indexes = new int[len];
		
		for (int i = 0; i < _srcsize; i++) {
			_flag[i] = 0;
		}		
	}
public:

	PatternGenerator2(int srcsize, int len) 
			: PatternGenerator2(srcsize, len, 0) {

		for (int i = 0; i < _srcsize; i++) {
			_src[i] = i + 1;
		}		
		
		reset();
	}
	
	PatternGenerator2(int size) 
			: PatternGenerator2(size, size) {
	}
	
	PatternGenerator2(const int *sortedsrc, int srcsize, int len)
			: PatternGenerator2(srcsize, len, 0) {

		memcpy(_src, sortedsrc, sizeof(int) * _srcsize);
		
		reset();
	}
	
	~PatternGenerator2() {
		delete [] _src;
		delete [] _flag;
		delete [] _list;
		delete [] _indexes;
	}
	
	int length()     const { return _len; }
	int sourcesize() const { return _srcsize; }
	int count()      const { return _count; }
	
	void reset() {
		for (int i = 0; i < _len; i++) {
			_flag[_indexes[i]] = 0;
		}
		for (int i = 0; i < _len; i++) {
			_indexes[i] = i;
			_list[i] = _src[_indexes[i]];
			_flag[_indexes[i]] = 1;
		}
		_count = 0;
	}
	
	int hasNext() {
		if (_count == 0) {
			return 1;
		}
		for (int i = 0; i < _len; i++) {
			if (_src[_indexes[i]] != _src[_srcsize - i - 1]) {
				return 1;
			}
		}
		return 0;
	}
	
	const int* next() {
		
		if (_count == 0) {
			_count++;
			return _list;
		}
		
		int i, j, b, f;
		
		i = _len - 1;
		_flag[_indexes[i]] = 0;
		
		f = 1;
		
		for (;;) {
			if (f) {
				b = _src[_indexes[i]];
				for (j = _indexes[i] + 1; j < _srcsize; j++) {
					if (_flag[j] == 0 && _src[j] != b) {
						break;
					}
				}
			} else {
				for (j = 0; j < _srcsize; j++) {
					if (_flag[j] == 0) {
						break;
					}
				}
				f = 1;
			}
			if (j == _srcsize) {
				i--;
				if (i < 0) {
					reset();
					break;
				} else {
					_flag[_indexes[i]] = 0;
				}
			} else {
				_indexes[i] = j;
				_list[i] = _src[_indexes[i]];
				_flag[_indexes[i]] = 1;
				i++;
				if (i == _len) {
					// kakutei
					break;
				} else {
					f = 0;
				}
			}
		}
		_count++;
		return _list;
	}
};

int nCr(int n, int r) {
	if (n < 0 || r < 0 || n < r) {
		return 0;
	}
	if (n - r < r) {
		r = n - r;
	}
	int c = 1;
	for (int i = 1; i <= r; i++) {
		c *= n;
		c /= i;
		n--;
	}
	return c;
}

int nPr(int n, int r) {
	if (n < 0 || r < 0 || n < r) {
		return 0;
	}
	int p = 1;
	while (r > 0) {
		p *= n;
		n--;
		r--;
	}
	return p;
}

int main() {
	
	PatternGenerator2 gen(15);
	
	for (;;) {
		const int *k = gen.next();
		if (gen.count() == 36690094) {
			cout << gen.count() << ": ";
			for (int i = 0; i < gen.length(); i++) {
				cout << "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[i]];
			}
			cout << endl;
			break;
		}
	}
	
	return 0;
}