public class Euler491 {

    private static long countGenericPairsDiv11(int digitsCount) {
        int totalSlots = 2 * digitsCount;
        int oddSlots = digitsCount;
        int evenSlots = digitsCount;

        long[] fact = new long[totalSlots + 1];
        fact[0] = 1;
        fact[1] = 1;
        for (int i = 2; i <= totalSlots; ++i) {
            fact[i] = fact[i - 1] * i;
        }

        int[] oddTake = new int[digitsCount];
        long[] answer = { 0 };

        dfs(0, 0, 0, digitsCount, oddSlots, evenSlots, fact, oddTake, answer);

        return answer[0];
    }

    private static void dfs(int digit, int used, int weighted, int digitsCount, int oddSlots, int evenSlots,
            long[] fact, int[] oddTake, long[] answer) {
        if (digit == digitsCount) {
            if (used != oddSlots) {
                return;
            }
            int totalDigitSum = digitsCount * (digitsCount - 1) / 2;
            if ((weighted - totalDigitSum) % 11 != 0) {
                return;
            }

            long oddAll = fact[oddSlots];
            long oddZeroLead = 0;
            long evenAll = fact[evenSlots];

            for (int d = 0; d < digitsCount; ++d) {
                oddAll /= fact[oddTake[d]];
                evenAll /= fact[2 - oddTake[d]];
            }

            if (oddTake[0] > 0) {
                oddZeroLead = fact[oddSlots - 1];
                oddZeroLead /= fact[oddTake[0] - 1];
                for (int d = 1; d < digitsCount; ++d) {
                    oddZeroLead /= fact[oddTake[d]];
                }
            }

            long oddValid = oddAll - oddZeroLead;
            answer[0] += oddValid * evenAll;
            return;
        }

        for (int take = 0; take <= 2; ++take) {
            if (used + take > oddSlots) {
                continue;
            }
            oddTake[digit] = take;
            dfs(digit + 1, used + take, weighted + digit * take, digitsCount, oddSlots, evenSlots, fact, oddTake,
                    answer);
        }
    }

    public static void main(String[] args) {
        System.out.println(countGenericPairsDiv11(10));
    }
}