Маленький пингвин Поло любит свою родную деревню. В этой деревне n домов, пронумерованных целыми числами от 1 до n. На каждом доме висит табличка с целым числом, на i-том доме висит табличка с целым числом p_i (1 ≤ p_i ≤ n).

Маленький пингвин Поло очень любит гулять по этой деревне. Прогулка выглядит следующим образом. Сначала он стоит около дома с номером x. Потом пингвин идет к дому, номер которого написан на табличке дома x (то есть к дому p_x), затем к дому, номер которого написан на табличке дома p_x (то есть к дому p_px), и так далее.

Известно, что:

1. Начав прогулку от любого дома с номером от 1 до k, включительно, он может дойти до дома с номером 1.
2. Начав прогулку от любого дома с номером от k + 1 до n, включительно, он точно не может дойти до дома с номером 1.
3. Начав прогулку от дома с номером 1, пингвин Поло может попасть обратно к дому с номером 1 через некоторое ненулевое количество переходов от дома к дому.

Вам нужно найти, сколькими способами можно написать числа на табличках домов, чтобы описанные выше три условия выполнялись. Выведите остаток от деления этого количества на 1000000007 (10⁹ + 7).