AT_awtf2025_b Movies

Maroon's summer vacation lasts $ N $ days from Day $ 1 $ through Day $ N $ . During the vacation, $ M $ movies numbered from $ 1 $ through $ M $ are scheduled to be screened, and movie $ i $ can be watched from Day $ L_i $ through Day $ R_i $ . For a subset $ s $ of all movies, define $ f(s) $ as follows: - $ f(s) $ is the maximum number of movies in $ s $ that can be watched throughout the vacation when he can watch at most one movie per day. Here, watching the same movie multiple times counts as one movie. There are $ 2^M $ possible sets for $ s $ . Find the sum, modulo $ 998244353 $ , of $ f(s) $ over all of them.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_M $ $ R_M $

Output the answer.

### Sample Explanation 1 $ f(s)=|s| $ holds for most $ s $ . The only exception is $ s=\{1,2,3\} $ , where $ f(s)=2 $ . The sum of $ f(s) $ over all $ s $ is $ 11 $ . ### Constraints - $ 1 \leq N \leq 100 $ - $ 1 \leq M \leq N \times (N+1) /2 $ - $ 1 \leq L_i \leq R_i \leq N $ - $ (L_i,R_i) \neq (L_j,R_j) $ ( $ i \neq j $ ) - All input values are integers.