| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P166PROF - ROUND 6F - Điện tử số |
Lúi hôm nay có bài thực hành môn điện tử số. Lúi rất vui vì lần đầu tiên được thử lắp mạch điện tử và Lúi cũng rất thích tìm hiểu về cổng XOR.
Trong bài thực hành của Lúi, mạch gồm n dữ liệu vào, mỗi cổng vào chỉ nhận dữ liệu là các số từ 0 đến 2m – 1. Các cổng dữ liệu được lắp với các cổng XOR và 2 khóa có thể điều chỉnh được là l và r. Đầu ra là 1 số nguyên duy nhất là kết quả nhận được của hàm f(l, r) = al xor al + 1 xor ... xor ar – 1 xor ar.
Giờ Lúi muốn biết có bao nhiêu bộ dữ liệu đầu vào mà đầu ra luôn là số khác 0 với mọi cặp (l, r) trong đó .
Input
Dòng đầu số nguyên n, m (1 <= n, m <= 10^5)
Output
In trên một dòng số nguyên duy nhất là số bộ dữ liệu. Vì số lượng bộ dữ liệu là lớn nên kết quả cần được lấy MOD 1000000009 (1e9 + 9).
Example
Input: 2 2 Output: 6
Giải thích:
(1, 2); (2, 1); (2, 3); (3, 2); (1, 3) và (3, 1).
| Được gửi lên bởi: | adm |
| Ngày: | 2016-03-31 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
