{"code":"fc112warp","name":"WARP","description":"Tèo đang bị lạc trong mê cung và cần tìm đường thoát ra. Mê cung gồm $n$ phòng đánh số từ 1 đến $n$. Mỗi phòng được mã hóa bằng một số tự nhiên từ 0 đến $2^{30} − 1$.\r\n\r\nTèo đang ở phòng số 1. Trong phòng này có hướng dẫn rằng Tèo có thể di chuyển từ phòng $a$ đến phòng $b$ khi và chỉ khi:\r\n- a < b\r\n- Gọi số mã hóa của phòng $a$ và $b$ lần lượt là $x$ và $y$. Khi đó tồn tại số tự nhiên $k$ để: $\\left \\lfloor \\frac{x}{2^k} \\right \\rfloor, \\left \\lfloor \\frac{y}{2^k} \\right \\rfloor$ đều là số lẻ.\r\n\r\nĐồng thời, số cách di chuyển từ phòng a đến phòng b bằng số lượng số k thỏa mãn yêu cầu trên.\r\n\r\nTèo biết bằng mình cần đến được phòng $n$ để thoát ra khỏi mê cung. Hỏi Tèo có bao nhiêu cách\r\nđể di chuyển từ phòng 1 đến phòng $n$? Hai cách di chuyển được coi là khác nhau nếu Tèo đi qua\r\nmột phòng trong một cách nhưng không đi qua trong cách kia, hoặc Tèo dùng 2 cách khác nhau\r\nđể di chuyển giữa hai phòng. Đồng thời, vì đáp án có thể rất lớn, chỉ cần đưa ra đáp án $modulo$\r\n$10^9 + 7$.\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên gồm một số nguyên $n$ là số phòng trong mê cung ($1 \\le n \\le 10^5$).\r\n- Dòng thứ hai gồm $n$ số nguyên dương không lớn hơn $10^9$, trong đó số thứ $i$ là mã hóa của phòng thứ $i$.\r\n\r\n

Output

\r\n\r\n- In ra một số nguyên duy nhất là số cách di chuyển từ phòng 1 đến phòng $n$ $modulo$ $10^9 + 7$.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($10\\%$ số điểm): $n \\le 8$\r\n- Subtask $2$ ($40\\%$ số điểm): $n \\le 10^3$\r\n- Subtask $3$ ($50\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 4\r\n 1 3 3 1\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 5\r\n ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 9\r\n 1 3 5 7 9 11 13 15 17\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 732\r\n ```","points":200.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}