// Sample Input 1
8 3 3
1 1 2 2 3 1 1 2
1 1 2

// Sample Input 2
1 1 5
1
1

// Sample Input 3
8 3 3
1 2 1 2 1 3 1 3
3 2 3

// Sample Input 4
22 2 15
2 9 1 2 7 11 5 12 7 11 9 10 6 13 13 4 2 14 7 15 7 8
1 2

// Sample Output 1
2

// Sample Output 2
24

// Sample Output 3
4

// Sample Output 4
520561546