Frangolino ali na mesa

Washington, um chef entusiasta da inteligência artificial e amante da culinária, decidiu construir um robô-garçom para o seu novo restaurante, o Frangolino, especializado em frangos empanados. Washington abrirá o restaurante para uma noite especial entre amigos e decidiu testar o robô-garçom nessa ocasião.

O restaurante atenderá $N$ mesas, numeradas de $1$ a $N$, e servirá somente um prato: frango à milanesa. Washington gosta muito de brincar com palavras e decidiu então definir dois comandos para o robô-garçom: o comando “ali na mesa $X$” e o comando “a milanesa $X$”.

O comando “ali na mesa $X$” significa que o robô-garçom deve se dirigir até a mesa $X$ e aguardar a próxima instrução. Já o comando “a milanesa $X$” significa que o robô-garçom deve registrar no sistema um pedido de $X$ frangos à milanesa para a mesa em que ele se encontra. No início da noite, o robô-garçom se encontra na mesa $1$.

Infelizmente, o robô-garçom tem um defeito e não consegue lidar bem com anagramas. Para cada comando recebido, o robô tem $50%$ de chance de executá-lo corretamente e $50%$ de chance de executar o outro comando.

Sua tarefa é, dado o histórico de comandos recebidos pelo robô, determinar, para cada mesa do restaurante, o valor esperado do número de frangos à milanesa que serão servidos.

A primeira linha da entrada contém dois inteiros $N$ e $Q$ ($1 \leq N, Q \leq 10^5$), representando o número de mesas e o número de comandos do robô-garçom, respectivamente.

A segunda linha contém $Q$ inteiros $X_1, \dots, X_Q$ ($1 \leq X_i \leq N$) separados por espaço. Cada $X_i$ descreve o valor de um dos comandos que o robô-garçom recebeu, na ordem em que ocorreram.

Note que o comando em si não é fornecido, já que o robô-garçom executará com $50%$ de chance um ou outro.

A saída deve conter $N$ linhas. A $i$-ésima linha deverá conter o valor esperado do número de frangos à milanesa que serão servidos na mesa $i$, conforme descrito a seguir.

O valor esperado pode não ser um inteiro, mas sempre será um número racional e, portanto, pode ser representado por uma fração irredutível $\tfrac{p}{q}$. Como $p$ e $q$ podem ser muito grandes, você deve imprimir $p \times q^{-1} \bmod (10^9 + 7)$, onde $q^{-1}$ é o inverso multiplicativo de $q$ módulo $10^9 + 7$.