Это сложная версия этой задачи. Единственное различие между простой и сложной версиями заключается в ограничениях на $$$m$$$. Вы можете делать взломы, только если обе версии задачи сданы.

Chiori очень любит куклы и сейчас она собирается украсить свою спальню!

Так как Chiori коллекционирует куклы, всего у нее $$$n$$$ кукол, $$$i$$$-я из этих кукол имеет неотрицательное целое число $$$a_i$$$ ($$$a_i < 2^m$$$, $$$m$$$ дано). Chiori хочет выбрать некоторых кукол (возможно ноль) для украшения. Таким образом, всего существует $$$2^n$$$ способов.

Обозначим за $$$x$$$ побитовую xor сумму значений у кукол, выбранных Chiori (в случае, если Chiori не выбрала ни одной куклы, $$$x = 0$$$). Значением способа выбора кукол назовем количество битов равных $$$1$$$ в двоичном представлении $$$x$$$. Более формально, это число также равно количеству индексов $$$0 \leq i < m$$$, таких что $$$\left\lfloor \frac{x}{2^i} \right\rfloor$$$ нечетно.

Посчитайте для Chiori количество способов выбрать куклы со значением $$$i$$$ для всех целых $$$i$$$ от $$$0$$$ до $$$m$$$. Поскольку эти числа могут быть очень большими, вы должны посчитать их по модулю $$$998\,244\,353$$$.