Giải bài trực tuyến

Một kỷ lục thế giới về xếp domino đổ đã được ghi nhận vào hôm 17/11/2006. Kỷ lục này thuộc về Hà Lan khi 4.079.381 quân domino đã lần lượt đổ xuống theo phản ứng dây chuyền trong tiếng vỗ tay reo hò của các cổ động viên. Những người tổ chức sự kiện Ngày Domino ở Hà Lan cho biết, 4.079.381 quân domino đã lần lượt đổ xuống trong vòng 2 giờ đồng hồ. Những quân domino đã di dộng uyển chuyển trên nền những điệu nhạc cổ điển và đương đại là nét đặc biệt nhất của màn trình diễn domino. Tác giả Robin Paul Weijers nói: “Hơn 4 triệu quân domino, điều này chưa bao giờ xảy ra. Chúng tôi còn thành công trong việc khiến cho những quân bài domino nhảy múa trong tiếng nhạc. Tôi rất hạnh phúc vì đã thành công”.

Với màn trình diễn tuyệt vời này, những kỷ lục gia domino Hà Lan đã phá vỡ kỷ lục của chính họ lập được năm 2005 với 4.002.136 quân bài domino. Sắp tới, Bờm dự định xây dựng một công trình lớn hơn để phá kỷ lục của người Hà Lan. Công trình sẽ bao gồm 2 công đoạn chính:

• Công đoạn 1: Xếp M*N-T quân domino vào các ô còn trống trên hình chữ nhật kích thức M*N (M, N ≤ 16), trong hình chữ nhật đó có T ô đã được đặt trước T vật trang trí.
• Công đoạn 2: Xếp R*L quân domino thành một dãy độ dài L (L ≤ 10⁶), mỗi hàng có đúng R (R ≤ 8) quân (có thể được hiểu như xếp vào hình chữ nhật kích thước R * L).

Điểm độc đáo trong công trình này là sự phối màu giữa các quân domino lân cận chung cạnh. Các quân domino được xếp bằng hai loại domino, loại 1 có màu xanh nhạt và loại 2 có màu xanh đậm. Quân domino ở vị trí ô (i,j) sẽ phải thỏa mãn điều kiện: nếu i+j lẻ thì màu quân domino này sẽ phải có màu không nhạt hơn các quân ở các ô chung cạnh (nếu có), nếu i+j chẵn thì màu quân domino này sẽ phải có màu không đậm hơn các quân ở các ô chung cạnh (nếu có).

Để xây dựng công trình, Bờm muốn biết số lượng cách xếp khác nhau của công đoạn 1 và công đoạn 2. Hai cách xếp được gọi là khác nhau nếu khi chồng khít 2 cách lên nhau (không xoay hoặc lật) có ít nhất một quân khác màu.

Input

• Dòng 1: gồm 1 số nguyên dương K (K ≤ 10⁹), các kết quả tìm được sẽ mod cho K,
• Dòng 2: bắt đầu là 3 số nguyên dương M, N, T (M, N ≤ 16, T ≤ M * N), trong đó M, N là kích thước hình chữ nhật trong công đoạn 1, T là số lượng ô trong hình chữ nhật đã đặt vật trang trí, tiếp theo là T cặp số, cặp số (i, j) là tọa độ ô đã đã đặt vật trang trí;
• Dòng 3: gồm 2 số nguyên dương R, L (R ≤ 8, L ≤ 10⁶) là kích thước hình của công đoạn 2.

Output

• Dòng 1: số cách xếp công đoạn 1 khác nhau mod K;
• Dòng 2: số cách xếp công đoạn 2 khác nhau mod K.

Example

Input:
1000
5 5 1 3 3
3 10000

Output:
240
593
Chú ý: Có 50% số test M, N ≤ 10 và L ≤ 10000;