Trong ngày cuối cùng trước khi học kỳ mới bắt đầu, CLB H3.2 có tổ chức một Vũ hội, trong đó các thành viên sẽ múa hát xuyên màn đêm. Để buổi Vũ hội thêm rực rỡ, Ban tổ chức đã lắp thêm ~n~ bóng đèn trang trí vào khắp phòng, và các bóng đèn được đánh số từ ~1~ đến ~n~. Có tất cả ~6~ công tắc với các tính năng như sau:

• Công tắc 1: thay đổi trạng thái tất cả các bóng đèn (từ bật thành tắt, tắt thành bật).
• Công tắc 2: cũng thay đổi trạng thái nhưng chỉ với các bóng có số thứ tự chẵn.
• Công tắc 3: cũng thay đổi trạng thái với các bóng có số thứ tự lẻ.
• Công tắc 4: cũng thay đổi trạng thái với các bóng có số thứ tự chia hết cho ~3~.
• Công tắc 5: cũng thay đổi trạng thái với các bóng có số thứ tự chia ~3~ dư ~1~.
• Công tắc 6: cũng thay đổi trạng thái với các bóng có số thứ tự chia ~3~ dư ~2~.

Ban đầu, tất cả bóng đèn đều bật. Trong buổi tiệc, DJ Banana sẽ lo việc điều phối âm nhạc và bật tắt các công tắc để không khí thêm phần mờ ảo. Đến cuối buổi tiệc, Banana mắt lim dim đếm được có ~m~ bóng đèn còn bật (các bóng còn lại chưa rõ bật hay tắt) và đếm được rằng đã bấm công tắc tổng cộng ~c~ lần. Hỏi có thể có bao nhiêu khả năng xảy ra đối với ~n~ bóng đèn của đêm Vũ hội?

Input

Một dòng duy nhất gồm số bóng đèn ~n~ với ~1 \le n \le 10^5~, số bóng đèn còn bật mà Banana đã thấy được là ~m~ với ~0 \le m \le n~ và tổng số lần ấn công tắc ~c~ với ~0 \le c \le 10^9~.

Dòng tiếp theo cho biết số thứ tự của các bóng đèn còn bật mà Ban thấy được (chú ý một lần nữa rằng các bóng còn lại thì không rõ là bật hay tắt).

Output

Số tất cả trạng thái có thể có thể (kết quả này vẫn tính được trong kiểu Int64).

Sample input 1:

4 2 1
1 2

Sample output 1:

1

Sample input 2:

8 2 100
1 5

Sample output 2:

4

Giải thích: trong VD1, ta thấy ở cuối cùng còn bóng đèn ~1,2~ còn bật, các bóng ~3,4~ chưa rõ trạng thái, ngoài ra được nhấn công tắc ~1~ lần. Như thế thì có thể nhấn công tắc ~4~ một lần và bóng có STT chia hết cho ~3~ sẽ tắt, lúc đó các bóng còn bật là ~1,2,4~, dễ thấy không còn trạng thái nào khác có thể thu được. Trong VD2, ta có một trong các cách là bật tắt công tắc 1 tất cả ~100~ lần, khi đó cuối cùng tất cả bóng đèn đều bật (nên rõ ràng trong đó có bóng ~1,5~ cũng còn bật).