There exists an island called Arpa’s land, some beautiful girls are living there, as ugly ones do.
Mehrdad wants to become minister of Arpa’s land. Arpa has prepared an exam. Exam has only one question, given n, print the last digit of 1378n.
Mehrdad has become quite confused and wants you to help him. Please help, although it's a naive cheat.
The single line of input contains one integer n (0 ≤ n ≤ 10106).
Print single integer — the last digit of 1378n.
1
8
2
4
In the first example, last digit of 13781 = 1378 is 8.
In the second example, last digit of 13782 = 1378·1378 = 1898884 is 4.
There are some beautiful girls in Arpa’s land as mentioned before.
Once Arpa came up with an obvious problem:
Given an array and a number x, count the number of pairs of indices i, j (1 ≤ i < j ≤ n) such that 
, where 
is bitwise xor operation.
Immediately, Mehrdad discovered a terrible solution that nobody trusted. Now Arpa needs your help to implement the solution to that problem.
First line contains two integers n and x (1 ≤ n ≤ 2·106, 0 ≤ x ≤ 2107) — the number of elements in the array and the integer x.
Second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2107) — the elements of the array. It's guaranteed that 
.
Input compression : x and ais are given in 32 base numerical system (i.e. "V" = 31, "H9" = 17·32 + 9 = 480).
It's guaranteed that no number starts with zero in the input.
Print a single integer: the answer to the problem.
2 3
1 2
1
4 1
A C E F
1
A bitwise xor takes two bit integers of equal length and performs the logical xor operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. You can read more about bitwise xor operation here: https://en.wikipedia.org/wiki/Bitwise_operation#XOR.
As you noticed, there are lovely girls in Arpa’s land.
People in Arpa's land are numbered from 1 to n. Everyone has exactly one crush, i-th person's crush is person with the number crushi.
Someday Arpa shouted Owf loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows.
The game consists of rounds. Assume person x wants to start a round, he calls crushx and says: "Oww...wwf" (the letter w is repeated t times) and cuts off the phone immediately. If t > 1 then crushx calls crushcrushx and says: "Oww...wwf" (the letter w is repeated t - 1 times) and cuts off the phone immediately. The round continues until some person receives an "Owf" (t = 1). This person is called the Joon-Joon of the round. There can't be two rounds at the same time.
Mehrdad has an evil plan to make the game more funny, he wants to find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y , x would become the Joon-Joon of the round. Find such t for Mehrdad if it's possible.
Some strange fact in Arpa's land is that someone can be himself's crush (i.e. crushi = i).
The first line of input contains integer n (1 ≤ n ≤ 5·106) — the number of people in Arpa's land.
The second line contains n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush.
If there is no t satisfying the condition, print -1. Otherwise print such smallest t. As answer can become too large, print it modulo 109 + 7.
4
2 3 1 4
3
4
4 4 4 4
-1
4
2 1 4 3
1
In the first sample suppose t = 3.
If the first person starts some round:
The first person calls the second person and says "Owwwf", then the second person calls the third person and says "Owwf", then the third person calls the first person and says "Owf", so the first person becomes Joon-Joon of the round. So the condition is satisfied if x is 1.
The process is similar for the second and the third person.
If the fourth person starts some round:
The fourth person calls himself and says "Owwwf", then he calls himself again and says "Owwf", then he calls himself for another time and says "Owf", so the fourth person becomes Joon-Joon of the round. So the condition is satisfied when x is 4.
In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.
Just in case somebody missed it: we have wonderful girls in Arpa’s land.
Arpa has a rooted tree (connected acyclic graph) consisting of n vertices. The vertex 1 is the root. There is a letter written on each edge of this tree. Mehrdad is a fan of Dokhtar-kosh things. He call a string Dokhtar-kosh, if we can shuffle the characters in string such that it becomes palindrome.
He asks Arpa, for each vertex v, what is the length of the longest simple path in subtree of v that form a Dokhtar-kosh string.
The first line contains integer n (1 ≤ n ≤ 5·105) — the number of vertices in the tree.
(n - 1) lines follow, the i-th of them contain an integer pi and a letter ci (1 ≤ pi < i, ci is lowercase English letter), that mean that there is an edge between nodes pi and i and there is a letter ci written on this edge.
Print n integers. The i-th of them should be the length of the longest simple path in subtree of the i-th vertex that form a Dokhtar-kosh string.
4
1 s
2 a
3 s
3 1 1 0
5
1 a
2 z
1 a
4 z
4 1 0 1 0