Напишите программу, которая выводит все возможные варианты перестановок и возможное количество перестановок. чистый "С"

Напишите программу, которая выводит все возможные варианты перестановок и возможное количество перестановок. Программа должна запрашивать количество элементов, затем сами элементы (каждый элемент в отдельной строке), выводить возможные варианты перестановок (каждый вариант в отдельной строке) и возможное количество перестановок.
Пример работы программы:
Входные данные:
Введите количество элементов: 3
Введите элемент:1
Введите элемент:2
Введите элемент:3
Выходные данные:
123
132
213
231
312
321
Всего комбинаций: 6