446_E. DZY Loves Bridges_9677
DZY owns 2m islands near his home, numbered from 1 to 2m. He loves building bridges to connect the islands. Every bridge he builds takes one day's time to walk across.

DZY has a strange rule of building the bridges. For every pair of islands u, v (u ≠ v), he has built 2k different bridges connecting them, where <image> (a|b means b is divisible by a). These bridges are bidirectional.

Also, DZY has built some bridges connecting his home with the islands. Specifically, there are ai different bridges from his home to the i-th island. These are one-way bridges, so after he leaves his home he will never come back.

DZY decides to go to the islands for sightseeing. At first he is at home. He chooses and walks across one of the bridges connecting with his home, and arrives at some island. After that, he will spend t day(s) on the islands. Each day, he can choose to stay and rest, or to walk to another island across the bridge. It is allowed to stay at an island for more than one day. It's also allowed to cross one bridge more than once.

Suppose that right after the t-th day DZY stands at the i-th island. Let ans[i] be the number of ways for DZY to reach the i-th island after t-th day. Your task is to calculate ans[i] for each i modulo 1051131.

Input

To avoid huge input, we use the following way to generate the array a. You are given the first s elements of array: a1, a2, ..., as. All the other elements should be calculated by formula: ai = (101·ai - s + 10007) mod 1051131 (s < i ≤ 2m).

The first line contains three integers m, t, s (1 ≤ m ≤ 25; 1 ≤ t ≤ 1018; 1 ≤ s ≤ min(2m, 105)).

The second line contains s integers a1, a2, ..., as (1 ≤ ai ≤ 106).

Output

To avoid huge output, you only need to output xor-sum of all the answers for all i modulo 1051131 (1 ≤ i ≤ 2m), i.e. (ans[1] mod 1051131) xor (ans[2] mod 1051131) xor... xor (ans[n] mod 1051131).

Examples

Input

2 1 4
1 1 1 2


Output

1


Input

3 5 6
389094 705719 547193 653800 947499 17024


Output

556970

Note

In the first sample, ans = [6, 7, 6, 6].

If he wants to be at island 1 after one day, he has 6 different ways:

  1. home —> 1 -(stay)-> 1 
  2. home —> 2 —> 1 
  3. home —> 3 —> 1 
  4. home —> 3 —> 1 (note that there are two different bridges between 1 and 3) 
  5. home —> 4 —> 1 
  6. home —> 4 —> 1 (note that there are two different bridges from home to 4) 



In the second sample, (a1, a2, a3, a4, a5, a6, a7, a8) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849), ans = [235771, 712729, 433182, 745954, 139255, 935785, 620229, 644335].
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    private static final int MODULO = 1051131;
    private long days;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = 1 << in.nextInt();
        days = in.nextLong();
        int s = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < s; ++i)
            a[i] = in.nextInt() % MODULO;
        for (int i = s; i < n; ++i)
            a[i] = (101 * a[i - s] + 10007) % MODULO;
        a = doIt(a, 1, 0);
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] < 0)
                a[i] += MODULO;
            res ^= a[i];
        }
        out.println(res);
    }

    private int[] doIt(int[] a, int p, int q) {
        int n = a.length;
        assert (n & (n - 1)) == 0;
        if (n == 1) {
            a[0] = (int) (a[0] * IntegerUtils.powerModulo(p + q, days, MODULO) % MODULO);
            return a;
        }
        n /= 2;
        int[] b = new int[n];
        for (int i = 0; i < n; ++i) {
            b[i] = a[i] + a[i + n];
            if (b[i] >= MODULO)
                b[i] -= MODULO;
        }
        b = Arrays.copyOf(doIt(b, 2 * p % MODULO, (int) (((n - 1L) * p + q) % MODULO)), 2 * n);
        System.arraycopy(b, 0, b, n, n);
        long multiplier = IntegerUtils.powerModulo(((1L - n) * p + q) % MODULO, days, MODULO);
        for (int i = 0; i < n; ++i) {
            b[i] = (int) ((b[i] + (a[i] - a[i + n]) * multiplier) % MODULO);
            b[i + n] = (int) ((b[i + n] - (a[i] - a[i + n]) * multiplier) % MODULO);
        }
        for (int i = 0; i < 2 * n; ++i)
            b[i] = (int) (b[i] * (MODULO + 1L) / 2 % MODULO);
        return b;
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        try {
            while(tokenizer == null || !tokenizer.hasMoreTokens())
                tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}

class IntegerUtils {

    public static long powerModulo(long a, long n, long mod) {
        long res = 1;
        for(; n > 0; n >>= 1) {
            if((n & 1) != 0) res = res * a % mod;
            a = a * a % mod;
        }
        return res;
    }

    }


2 1 4
1 1 1 2
 3 5 6
389094 705719 547193 653800 947499 17024
 20 285682452833524258 1
33338
 3 159792384791265 7
366310 201358 978173 900642 949624 50986 197378
 1 1 2
468879 777745
 20 325906599894074452 1
33338
 3 159792384791265 7
249459 201358 978173 900642 949624 50986 197378
 1 1 2
468879 565599
 2 1 4
1 1 1 3
 3 5 6
256880 705719 547193 653800 947499 17024
 20 325906599894074452 1
10952
 3 159792384791265 7
100899 201358 978173 900642 949624 50986 197378
 2 1 4
1 1 1 6
 3 5 6
87287 705719 547193 653800 947499 17024
 20 392661610799236362 1
10952
 3 159792384791265 7
100899 201358 978173 900642 949624 52682 197378
 2 1 4
1 1 1 8
 3 5 6
87287 529109 547193 653800 947499 17024
 20 39896286655220033 1
10952
 3 159792384791265 7
100899 140926 978173 900642 949624 52682 197378
 2 1 4
1 1 1 15
 20 44849718754917517 1
10952
 2 1 2
468879 1308123
 3 1 4
1 1 1 15
 20 3462059678897902 1
10952
 2 1 2
445625 1308123
 4 1 4
1 1 1 15
 18 3462059678897902 1
10952
 3 136859598627018 7
366310 201358 978173 900642 949624 50986 197378
 2 1 4
1 0 1 2
 3 5 6
92175 705719 547193 653800 947499 17024
 20 325906599894074452 1
63624
 3 159792384791265 7
249459 201358 978173 900642 426755 50986 197378
 2 1 4
1 1 2 3
 3 6 6
256880 705719 547193 653800 947499 17024
 20 619293803874790356 1
10952
 3 1 4
1 1 1 6
 3 5 6
87287 705719 547193 653800 947499 19041
 20 392661610799236362 1
17369
 3 159792384791265 7
100899 201358 978173 1628889 949624 52682 197378
 2 1 4
1 0 1 8
 3 5 2
87287 529109 547193 653800 947499 17024
 20 39896286655220033 1
1530
 3 159792384791265 7
100899 140926 978173 900642 805595 52682 197378
 2 1 4
1 0 1 15
 2 1 2
426145 1308123
 4 1 4
1 1 1 20
 18 5528986919384431 1
10952
 3 136859598627018 7
366310 201358 978173 900642 91672 50986 197378
 2 1 2
468879 179793
 3 5 6
92175 705719 547193 653800 947499 1837
 3 159792384791265 7
249459 111082 978173 900642 426755 50986 197378
 3 9 6
256880 705719 547193 653800 947499 17024
 20 619293803874790356 1
11990
 3 1 4
2 1 1 6
 3 5 6
87287 705719 652886 653800 947499 19041
 20 392661610799236362 1
19623
 3 10 2
87287 529109 547193 653800 947499 17024
 22 39896286655220033 1
1530
 3 159792384791265 7
100899 140926 978173 1142722 805595 52682 197378
 2 2 4
1 0 1 15
 4 1 4
1 1 1 37
 3 136859598627018 7
484665 201358 978173 900642 91672 50986 197378
 2 1 2
468879 97499
 3 5 6
92175 705719 547193 653800 947499 3486
 3 159792384791265 7
249459 111082 978173 900642 426755 66167 197378
 3 9 6
256880 705719 547193 788431 947499 17024
 3 1 4
2 1 0 6
 3 5 6
87287 705719 652886 653800 947499 28967
 20 392661610799236362 1
17885
 22 39896286655220033 1
3047
 3 159792384791265 7
100899 140926 978173 499688 805595 52682 197378
 4 1 4
1 1 1 8
 3 5 6
169774 705719 547193 653800 947499 3486
 3 159792384791265 7
249459 142549 978173 900642 426755 66167 197378
 3 9 6
256880 705719 547193 788431 947499 3472
 3 1 4
2 2 0 6
 3 5 6
71059 705719 652886 653800 947499 28967
 3 1 2
87287 529109 547193 653800 455229 17024
 22 39896286655220033 1
444
 3 159792384791265 7
100899 140926 978173 499688 1111196 52682 197378
 3 2 2
1 2 1 0
 4 1 1
1 1 1 8
 1 1 2
468879 519781
 1 1 2
468879 923773
 1 1 2
468879 1308123
 20 285682452833524258 0
33338
 1 1 2
468879 179793
 1 1 2
816055 565599
 1 1 2
935497 519781
 1 2 2
468879 923773
 1 2 2
468879 1308123
 3 1 2
1 1 1 15
 1 1 2
816055 354223
 1 4 2
468879 1308123
 3 2 2
1 1 1 15
 18 5528986919384431 0
10952
 1 1 2
1321036 354223
 20 619293803874790356 0
11990
 3 10 2
87287 529109 547193 653800 455229 17024
 3 2 2
1 1 1 0
 18 5528986919384431 0
4509
 1 1 2
721151 354223

1
 556970
 602725
 683591
 0
 1358220
 214434
 0
 14
 197090
 1847712
 592778
 5
 731566
 1657720
 837866
 31
 324160
 1927807
 251846
 50
 817605
 1022304
 3752
 1342001
 207213
 55746
 1331423
 928235
 2
 373978
 1103424
 633126
 3
 176988
 1308097
 29406
 824850
 2188
 52439
 24
 189025
 1865554
 720126
 49
 516692
 197549
 206847
 365155
 49348
 579221
 292370
 1509915
 997405
 1136
 125675
 266721
 953735
 295008
 278609
 19
 238241
 223329
 191644
 752582
 999950
 117245
 29106
 384844
 400910
 1266354
 221174
 118270
 636534
 635242
 720023
 2468
 1315263
 31216
 713107
 503307
 637333
 323121
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0
 953735
 0
 0
 0
