Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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 CPP C++ 4.3.2 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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.