LCM of Pell‐like Numbers

Define \(e(n)\) and \(f(n)\) by

\[ (1+\sqrt{2})^n = e(n)+\sqrt{2}\,f(n),\quad (1-\sqrt{2})^n = e(n)-\sqrt{2}\,f(n), \]

so that \(e(n)\) and \(f(n)\) are integers. Let \[ g(n)=\operatorname{lcm}(f(1), f(2), \dots, f(n)). \]

Given two positive integers \(n\) and \(p\), where \(p\) is prime, and it is guaranteed that none of \(f(1),f(2),\dots,f(n)\) is \(0\) modulo \(p\), compute \[ S=\sum_{i=1}^n i\times g(i)\pmod{p}. \]

inputFormat

The input consists of a single line containing two space‐separated integers \(n\) and \(p\), where \(p\) is a prime number.

outputFormat

Output a single integer representing \(\sum_{i=1}^n i\times g(i) \pmod{p}\).

sample

4 7

2