Nguồn: Tự nghĩ.
Rating : 1300.

**Đề Bài**:
Tối hôm qua, Cubill do bận đi chơi Trung Thu mà chưa kịp làm bài tập toán mà thầy Lạc Đà cho cậu. Nên hôm sau cậu ngồi trong tiết toán trong sự lo lắng tột độ, cậu chỉ cầu trời là thầy đừng gọi cậu thế nhưng hai tiếng Cu...bill như xé lòng cậu. Cậu lo lắng lên bảng và được thầy cho bài toán sau:

Cho một dãy số gồm $n$ số, dãy số này bắt đầu từ số $x$ và số sau gấp $x$ lần số trước đó. Cụ thể dãy số đó có dạng "$x$, $x^2$, $x^3$, $x^4$, ...., $x^n$." Thầy yêu cầu cậu tính số dư của tổng dãy số đó khi chia dư cho $m$.

Do hôm qua không học bài nên Cubill mong các bạn sẽ giúp cậu qua được kiếp nạn này.
**Input**:
* Dòng đầu chứa ba số nguyên dương $x$, $n$, $m$ ($1\le x, m \le 10^9$, $1\le n \le 10^{18}$) thể hiện các số như đề bài mà thầy Lạc Đà cho cậu.

**Output**:
* Một số nguyên duy nhất là số dư của tổng dãy số khi chia dư cho $m$.

**Scoring:**

| Subtask | Điểm | Giới Hạn |
| -------- | -------- | -------- |
| 1 | 30 | $x=2$ |
| 2 | 70 | Không có ràng buộc gì thêm |

**Lời Giải:**
Subtask 1:
Ta dễ thấy công thức cho sub này là $2^{n+1}-2$.
Đpt: $(log n)$
Subtask 2:
Gọi F[i] là $x^i$, S[i] là F[1]+F[2]+...+F[i].
Ta thấy rằng:
$\left( \begin{array}{cc} S[i] \\ F[i] \end{array} \right)$ * $\left( \begin{array}{cc} 1 & x \\ 0 & x \end{array} \right)$ = $\left( \begin{array}{cc} S[i+1] \\ F[i+1] \end{array} \right)$
Nên ta nhân ma trận cơ bản để tính S[n].

Đpt: $(log n)$

**Code:** https://ideone.com/1DDf30