#include using namespace std; #define int long long const int mod = 998244353; void mul_matrix_2x2( int const (&m0)[4], int const (&m1)[4], int (&m_out)[4]) { m_out[0] = (m0[0] * m1[0] + m0[1] * m1[2])%mod; m_out[1] = (m0[0] * m1[1] + m0[1] * m1[3])%mod; m_out[2] = (m0[2] * m1[0] + m0[3] * m1[2])%mod; m_out[3] = (m0[2] * m1[1] + m0[3] * m1[3])%mod; } void power_matrix_2x2( int const (&m0)[4], unsigned int const n, int (&m_out)[4]) { if (n == 0) { m_out[0] = 1; m_out[1] = 0; m_out[2] = 0; m_out[3] = 1; } else if (n == 1) { m_out[0] = m0[0]; m_out[1] = m0[1]; m_out[2] = m0[2]; m_out[3] = m0[3]; } else if (n % 2 == 0) { int tmp_m[4]; mul_matrix_2x2(m0, m0, tmp_m); power_matrix_2x2(tmp_m, n / 2, m_out); } else { int tmp_m_a[4]; int tmp_m_b[4]; mul_matrix_2x2(m0, m0, tmp_m_a); power_matrix_2x2(tmp_m_a, n / 2, tmp_m_b); mul_matrix_2x2(m0, tmp_m_b, m_out); } } int calculate_fibonacci(int n) { int const matrix_2x2[4] = {1, 1, 1, 0}; int result_matrix_2x2[4]; power_matrix_2x2(matrix_2x2, n, result_matrix_2x2); return (result_matrix_2x2[2] + result_matrix_2x2[3])%mod; } signed main(){ int N; cin>>N; cout<<(calculate_fibonacci(N)+mod-1)%mod<