Problem C
Dining Hall Dilemma

Selective Focus Photography of Pasta With Tomato and Basil. Photo by Lisa Fotios

You are now the owner of BPlate and Feast. You want to plan a schedule for operating the two dining halls for the next $n$ days. Originally, you started implementing an all-or-nothing policy where you chose some days to have both dining halls open and some to have both dining halls closed. You realized that for specific days, however, you’d like to have theme nights at the dining hall where you give your undivided attention to either BPlate or Feast. So now on any given day you have the option to have both Feast and BPlate open or both closed, but on the $k$ specified days you have themed dinners, you must have only one of the dining halls open.

You can only earn money for a dining hall on a day when it is open. The expected earning for each dining hall on day $1$ is $1. However, for each dining hall, the expected earnings double each day (regardless of whether or not it operated on the previous day) as more people find out how great the dining hall is!

You want to earn exactly $d$ dollars over $n$ days. A schedule is considered favorable if it results in an expected earning of exactly $d$ dollars. How many possible favorable schedules are there?

Input

The first line of the input contains three space separated integers $n$ ($1 \leq n \leq 60$), $k$ ($1 \leq k \leq n$), and $d$ ($0 \leq d \leq 10^{18}$)

The second line of the input consists of $k$ space separated integers denoting the day numbers of the themed dinners.

Output

Print a single integer denoting the number of favorable schedules.

5 2 34
2 5

4