Maximum XOR

You are given an array A of N integers. You have to perform the following operations on the array:

1. Find an integer k which provides maximum XOR (exclusive OR) with the array. In other words, you need to find k such that 0 <= k < 2²³ and A[1] ⊕ A[1] ⊕ A[2]...A[n-1] ⊕ k is maximum.
2. Print value of k that is calculated in step 1 in a new line.
3. Remove the element that has the maximum value from the array A. Note that this step decreases the size of the array by 1.
4. If the array A has not become empty, then go to step 1 or end the program.

Input Format

• First line : N denoting the number of elements in the array
• Next line : N integers defining the A array

Output Format

Print N lines containing k for every removal

Sample Input

5

4 7 18 16 14

Sample Output

4294967280

4294967266

4294967282

4294967292

4294967291

Favorite Subsequences

You are given a string s of length N.

Now, a good subsequence is one that can be represented in the form aⁱb^jc^k, where i >= 1, j >= 1 and k >= 1. For example , if i = 2, j = 1, k = 3, it represents the string aabccc. In short, a good subsequence is a subsequence that first consist of i a characters, followed by j b characters, followed by k c characters, where i≥ 1, j ≥ 1 and k ≥ 1.

You are required to find the number of good subsequences of String S. As the number of such subsequences could be rather large, print the answer Modulo 10⁹+7.

Note: Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different.

Input Format:

The first and only line of input contains the S

Output Format :

Print the required answer on a single line.

Sample Input :

abcabc

Sample Output:

7