Это сложная версия задачи. В этой версии ограничения на $$$n$$$ и на сумму $$$n$$$ по всем наборам входных данных равны $$$2 \cdot 10^5$$$, а количество наборов входных данных не превышает $$$10^4$$$.

Была перестановка $$$p$$$ размера $$$n$$$$$$^{\text{∗}}$$$.

Её отправили по каналу связи следующим образом: сначала отправили все $$$0$$$-е по счёту биты каждого числа $$$p_{i}$$$ в перестановке в виде строки из $$$n$$$ символов 0 и/или 1, потом отправили $$$1$$$-е по счёту биты в таком же формате и так далее до самого старшего бита числа $$$n$$$.

Например, для $$$p = [3, 1, 2, 4]$$$ были бы отправлены следующие три строки:

1. «1100»;
2. «1010»;
3. «0001».

Вы получили все эти строки, однако порядок, в котором какая строка за какой бит отвечает, был потерян, то есть строки пришли в произвольном порядке. Для примера выше строки могли прийти в порядке «1010», «0001» и «1100».

Ваша задача — сказать, сколько вариантов изначальной перестановки $$$p$$$ могло быть передано. Возможно, что данные в процессе повредились, и не существует ни одного варианта изначальной перестановки $$$p$$$.