import Foundation

let main: () = {
    let (N, K) = *listOfInt()
    var LR = [(Int, Int)]()
    repeate(K) {
        let (l, r) = *listOfInt()
        LR.append((l, r + 1))
    }
    var dp = Array<ModInt>(N) { ModInt(0) }
    dp[0] = ModInt(1); dp[1] = ModInt(-1)
    for n in 0 ..< N {
        if n > 0 { dp[n] += dp[n - 1] }
        for (l, r) in LR {
            if n + l < N { dp[n + l] += dp[n] }
            if n + r < N { dp[n + r] -= dp[n] }
        }
    }
    let ans = dp[N - 1].value
    print(ans)
}()
























//----------------------------------

let dx = [1, 0, -1, 0] //[1, 0, -1, 0, -1,  1, -1, 1]
let dy = [0, 1, 0, -1] //[0, 1, 0, -1, -1, -1,  1, 1]

@inlinable func gcd(_ a: Int, _ b: Int) -> Int { (b > 0) ? gcd(b, a % b) : a }
@inlinable func lcm(_ a: Int, _ b: Int) -> Int { a / gcd(a, b) * b }

//----------------------------------

infix operator  =~ : ComparisonPrecedence
infix operator !=~ : ComparisonPrecedence
func =~ <T: FixedWidthInteger>(left: T, right: Range<T>) -> Bool { right ~= left }
func !=~ <T: FixedWidthInteger>(left: T, right: Range<T>) -> Bool { !(right ~= left) }
func =~ <T: FixedWidthInteger>(left: T, right: ClosedRange<T>) -> Bool { right ~= left }
func !=~ <T: FixedWidthInteger>(left: T, right: ClosedRange<T>) -> Bool { !(right ~= left) }

func =~ <T: Collection > (left: T.Element, right: T) -> Bool where T.Element : Equatable { right.contains(left) }
func !=~ <T: Collection > (left: T.Element, right: T) -> Bool where T.Element : Equatable { !right.contains(left) }

infix operator /^ : MultiplicationPrecedence
infix operator /^= : AssignmentPrecedence
func /^ <T: FixedWidthInteger>(left: T, right: T) -> T { (left + (right - 1)) / right }
func /^= <T: FixedWidthInteger>(left: inout T, right: T) { left = (left + (right - 1)) / right }

@inlinable func chmax<T: Comparable>(_ m: inout T, _ q: T) { if (m < q) { m = q } }
@inlinable func chmin<T: Comparable>(_ m: inout T, _ q: T) { if (m > q) { m = q } }
@inlinable func chRmax<T: Comparable>(_ m: inout T, _ q: T) -> Bool { if (m < q) { m = q; return true } else { return false } }
@inlinable func chRmin<T: Comparable>(_ m: inout T, _ q: T) -> Bool { if (m > q) { m = q; return true } else { return false } }

prefix operator *
prefix func * <T> (a: [T]) -> (T, T) { (a[0], a[1]) }
prefix func * <T> (a: [T]) -> (T, T, T) { (a[0], a[1], a[2]) }
prefix func * <T> (a: [T]) -> (T, T, T, T) { (a[0], a[1], a[2], a[3]) }
prefix func * <T> (a: [T]) -> (T, T, T, T, T) { (a[0], a[1], a[2], a[3], a[4]) }
prefix func * <T> (a: [T]) -> (T, T, T, T, T, T) { (a[0], a[1], a[2], a[3], a[4], a[5]) }

func printErr(_ str: String, terminator: String = "\n") {
    let s = str + terminator
    FileHandle.standardError.write(s.data(using: .utf8)!)
    FileHandle.standardError.synchronizeFile()
}

@inlinable func next() -> String { readLine()! }
@inlinable func nextInt() -> Int { Int(next())! }
@inlinable func nextDouble() -> Double { Double(next())! }
@inlinable func listOfString() -> [String] { next().split(separator: " ").map(String.init) }
@inlinable func listOfInt() -> [Int] { listOfString().map { Int($0)! } }
@inlinable func listOfInt(_ offset: Int = 0) -> [Int] { listOfString().map { Int($0)! + offset } }
@inlinable func listOfInt(_ offsets: Int ...) -> [Int] { listOfString().enumerated().map { Int($0.element)! + offsets[$0.offset % offsets.count] } }
@inlinable func listOfDouble(_ offset: Double = 0.0) -> [Double] { listOfString().map { Double($0)! + offset } }
@inlinable func listOfDouble(_ offsets: Double ...) -> [Double] { listOfString().enumerated().map { Double($0.element)! + offsets[$0.offset % offsets.count] } }

extension Int {
    init(s: String) { self.init(s)! }
    var isEven: Bool { self.isMultiple(of: 2) }
    var isOdd: Bool { !self.isEven }
    var isTrue: Bool { self != 0 }
    var isFalse: Bool { !self.isTrue }
    var toString: String { String(self) }
    var toChar: Character { Character(UnicodeScalar(UInt8(self))) }
}
func + (left: Int, right: Bool) -> Int { left + (right ? 1 : 0) }
extension Character {
    var asciiCode: Int { Int(self.asciiValue!) }
    var string: String { String(self) }
}
extension String {
    @inlinable subscript (position: Int) -> Character { self[self.index(self.startIndex, offsetBy: position)] }
    @inlinable func repeate(_ times: Int) -> String { String(repeating: self, count: times) }
    //  @inlinable subscript (n: Int) -> String { String(self[self.index(self.startIndex, offsetBy: n)]) }
    //  @inlinable subscript (n: Int) -> Int { Int(self[self.index(self.startIndex, offsetBy: n)].asciiValue!) }
    var toInt: Int { Int(self)! }
}
extension String { // VB like
    @inlinable func _index(_ position: Int) -> String.Index! {
        if !(0 ..< self.count ~= position) { return nil }
        return self.index(self.startIndex, offsetBy: position)
    }
    @inlinable func mid(from index: Int, length: Int) -> String! {
        if let startPosition = self._index(index) {
            if let endPosition = self._index(index + length - 1) {
                return String(self[startPosition...endPosition])
            } else {
                let endPosition = self.index(before: self.endIndex)
                return String(self[startPosition...endPosition])
            }
        }
        return ""
    }
    @inlinable func left(_ length: Int) -> String { String(self.prefix(length)) }
    @inlinable func right(_ length: Int) -> String { String(self.suffix(length)) }
}

extension Dictionary {
    @inlinable mutating func getOrSet(_ key: Key, _ defaultValue: () -> Value) -> Value {
        if let stored = self[key] { return stored }
        else {
            let newValue = defaultValue()
            self[key] = newValue
            return newValue
        }
    }
    @inlinable mutating func getOrElse(_ key: Key, _ defaultValue: () -> Value) -> Value {
        if let stored = self[key] { return stored } else { return defaultValue() }
    }
    @inlinable func containsKey(_ key: Key) -> Bool { self.keys.contains(key) }
}

extension Set {
    static func += (left: inout Set<Element>, right: Element) { left.insert(right) }
    static func -= (left: inout Set<Element>, right: Element) { left.remove(right) }
}

extension Array {
    static func += (left: inout Array<Element>, right: Element) { left.append(right) }
    init(_ size: Int, _ initValue: ((Int) -> Element)) {
        self = [Element]()
        for index in 0 ..< size {
            let value = initValue(index)
            self.append(value)
        }
    }
    init(_ size: Int, _ initValue: (() -> Element)) {
        self = [Element]()
        for _ in 0 ..< size {
            let value = initValue()
            self.append(value)
        }
    }
}
typealias IntArray = Array<Int>
typealias DoubleArray = Array<Double>
typealias BoolArray = Array<Bool>
typealias StringArray = Array<String>

extension Array where Element == Int {
    init(_ size: Int) {
        self = [Element](repeating: 0, count: size)
    }
}
extension Array where Element == Double {
    init(_ size: Int) {
        self = [Element](repeating: 0.0, count: size)
    }
}
extension Array where Element == Bool {
    init(_ size: Int) {
        self = [Element](repeating: false, count: size)
    }
}
extension Array where Element == String {
    init(_ size: Int) {
        self = [Element](repeating: "", count: size)
    }
}

extension Array {
    @inlinable func count(_ predicate: ((Element) -> Bool)) -> Int {
        var cnt = 0; for e in self { if (predicate(e)) { cnt += 1 } }
        return cnt
    }
    @inlinable func groupBy<K>(_ keySelector: (Element) -> K) -> [K : [Element]] {
        var destination = [K : [Element]]()
        for element in self {
            let key = keySelector(element)
            var list = destination.getOrSet(key) { [Element]() }
            list.append(element)
            destination[key] = list
        }
        return destination
    }
    @inlinable func groupByIndexed<K>(_ keySelector: (Element) -> K) -> [K : [Int]] {
        var destination = [K : [Int]]()
        for element in self.enumerated() {
            let key = keySelector(element.element)
            var list = destination.getOrSet(key) { [Int]() }
            list.append(element.offset)
            destination[key] = list
        }
        return destination
    }
}

extension Array {
    func binarySearch(_ element: Element, by compare: (Element, Element) -> Int, fromIndex: Int = 0, toIndex: Int = -1) -> Int {
        var low = fromIndex
        var high = (toIndex == -1) ? self.count - 1 : toIndex - 1
        while (low <= high) {
            let mid = (low + high) >> 1 // safe from overflows
            let midVal = self[mid]
            let cmp = compare(midVal, element)
            if (cmp < 0) { low = mid + 1 }          //-1
            else if (0 < cmp) { high = mid - 1 }    // 1
            else { return mid } // key found        // 0
        }
        return -(low + 1)  // key not found
    }
}
extension Array where Element : Comparable {
    func binarySearch(_ element: Element, fromIndex: Int = 0, toIndex: Int = -1) -> Int {
        var low = fromIndex
        var high = (toIndex == -1) ? self.count - 1 : toIndex - 1
        while (low <= high) {
            let mid = (low + high) >> 1 // safe from overflows
            let midVal = self[mid]
            if (midVal < element) { low = mid + 1 }
            else if (midVal > element) { high = mid - 1 }
            else { return mid } // key found
        }
        return -(low + 1)  // key not found
    }
}

extension Array where Element == Int {
    @inlinable func distinct() -> [Element] {
        var set = Set<Element>(), ary = [Element]()
        for n in self.indices { if !set.contains(self[n]) { ary.append(self[n]); set.insert(self[n]) } }
        return ary
    }
    @inlinable func any(_ predicate: (Element) -> Bool) -> Bool {
        var any = false; for element in self { if predicate(element) { any = true } }
        return any
    }
    @inlinable func all(_ predicate: (Element) -> Bool) -> Bool {
        self.allSatisfy(predicate)
    }
    @inlinable func sum() -> Element { self.reduce(0, +) }
    @inlinable func sum(by predicate: (Element) -> Element) -> Element {
        var sum = 0; for e in self { sum += predicate(e) }
        return sum
    }
    @inlinable func joinToString(_ sepatator: String = " ") -> String { self.map { String($0) }.joined(separator: sepatator) }
}

extension Array where Element == Double {
    @inlinable func sum() -> Element { self.reduce(0.0, +) }
    @inlinable func sum(by predicate: (Element) -> Element) -> Element {
        var sum = 0.0; for e in self { sum += predicate(e) }
        return sum
    }
    @inlinable func joinToString(_ sepatator: String = " ") -> String { self.map { String($0) }.joined(separator: sepatator) }
}
extension Array where Element == String {
    @inlinable func toIntDouble() -> (Int, Double) { (Int(self[0])!, Double(self[1])!) }
    @inlinable func toIntString() -> (Int, String) { (Int(self[0])!, self[1]) }
    @inlinable func toIntIntString() -> (Int, Int, String) { (Int(self[0])!, Int(self[1])!, self[2]) }
}

@inlinable func block( _ action: () -> Void) {
    action()
}
@inlinable func repeate(_ times1: Int, _ action: () -> Void) {
    for _ in 0 ..< times1 { action() }
}
@inlinable func repeate(_ times1: Int, _ action: (Int) -> Void) {
    for index1 in 0 ..< times1 {
        action(index1)
    }
}
@inlinable func repeate(_ times1: Int, _ times2: Int, _ action: (Int, Int) -> Void) {
    for index1 in 0 ..< times1 {
        for index2 in 0 ..< times2 {
            action(index1, index2)
        }
    }
}
@inlinable func repeate(_ times1: Int, _ times2: Int, _ times3: Int, _ action: (Int, Int, Int) -> Void) {
    for index1 in 0 ..< times1 {
        for index2 in 0 ..< times2 {
            for index3 in 0 ..< times3 {
                action(index1, index2, index3)
            }
        }
    }
}
@inlinable func repeate(_ times1: Int, _ times2: Int, _ times3: Int, _ times4: Int, _ action: (Int, Int, Int, Int) -> Void) {
    for index1 in 0 ..< times1 {
        for index2 in 0 ..< times2 {
            for index3 in 0 ..< times3 {
                for index4 in 0 ..< times4 {
                    action(index1, index2, index3, index4)
                }
            }
        }
    }
}

func measureTimeSeconds(block: (() -> Void)) -> Double {
    let startTime = Date()
    block()
    let duration = -startTime.timeIntervalSinceNow
    return duration
}


func turnpos(_ x: Int, _ y: Int) -> Int {
    var nx: Int
    var ratio: Int
    switch (x) {
    case ..<0:
        nx = -1 * x
        ratio = nx / y
        return (ratio + 1) * y + x
    default: return x // 0...
    }
}
func isprime(_ x: Int) -> Bool {
    switch (x) {
    case ...1: return false
    case ...3: return true
    default:
        var n = 2
        while n * n <= x {
            if x % n == 0 { return false }
            n += 1
        }
        return true
    }
}
func + (left: ModInt, right: ModInt) -> ModInt {  ModInt((left._value + right._value) % left._MOD) }
func - (left: ModInt, right: ModInt) -> ModInt { ModInt(turnpos((left._value - right._value) % left._MOD, left._MOD)) }
func * (left: ModInt, right: ModInt) -> ModInt { ModInt((left._value * right._value) % left._MOD) }
func / (left: ModInt, right: ModInt) -> ModInt { ModInt(left._value * right.pow(right._value, right._MOD - 2) % right._MOD) }
func + (left: ModInt, right: Int) -> ModInt { ModInt((left._value + right) % left._MOD) }
func + (left: Int, right: ModInt) -> ModInt { ModInt((right._value + left) % right._MOD) }
func += (left: inout ModInt, right: Int){ left = left + right }
func += (left: inout ModInt, right: ModInt){ left = left + right }
func - (left: ModInt, right: Int) -> ModInt { ModInt((left._value - right) % left._MOD) }
func - (left: Int, right: ModInt) -> ModInt { ModInt((left - right._value) % right._MOD) }
func -= (left: inout ModInt, right: Int) { left = left - right }
func -= (left: inout ModInt, right: ModInt) { left = left - right }
func * (left: ModInt, right: Int) -> ModInt { ModInt((left._value * right) % left._MOD) }
func * (left: Int, right: ModInt) -> ModInt { ModInt((left * right._value) % right._MOD) }
func *= (left: inout ModInt, right: Int) { left = left * right }
func *= (left: inout ModInt, right: ModInt) { left = left * right }
func / (left: ModInt, right: Int) -> ModInt { left / ModInt(right) }
func / (left: Int, right: ModInt) -> ModInt { ModInt(left) / right }
func /= (left: inout ModInt, right: Int) { left = left / right }
func /= (left: inout ModInt, right: ModInt) { left = left / right }
infix operator ** : BitwiseShiftPrecedence
func ** (left: ModInt, right: Int) -> ModInt { ModInt(left.pow(left._value, right)) }
func ** (left: ModInt, right: ModInt) -> ModInt { ModInt(left.pow(left._value, right._value)) }
func ** (left: Int, right: Int) -> Int { Int(pow(Double(left), Double(right))) }
prefix func - (left: ModInt) -> ModInt { ModInt(-1 * left._value) }
func == (left: ModInt, right: ModInt) -> Bool { (left._value - right._value) % left._MOD == 0 }
func != (left: ModInt, right: ModInt) -> Bool { !(left == right) }
func debugPrint(_ x: ModInt) { print("\(x._value) mod \(x._MOD)") }
func debugPrint(_ x: [ModInt]) { for (n, v) in x.enumerated() { print("[\(n)] \(v._value) mod \(v._MOD)") } }

class ModInt : Comparable, Equatable {
    let _MOD = 998244353
    static func < (lhs: ModInt, rhs: ModInt) -> Bool { lhs._value < rhs._value}
    var _value: Int
    init(_ value: Int = 0) {
        if isprime(_MOD) == false { fatalError("The divisor should be prime!") }
        _value = value % _MOD
        if _value < 0 { _value = turnpos(_value, _MOD) }
    }
    func setv(newvalue: Int) {
        _value = newvalue % _MOD
        if _value < 0 { _value = turnpos(_value, _MOD) }
    }
    func getv() -> Int { _value }
    func getd() -> Int { _MOD }
    var value: Int { _value }
    func pow(_ a: Int, _ b: Int) -> Int {
        if (b == 0) { return 1 }
        if (b % 2 == 0) {
            let d = pow(a, b / 2)
            return (d * d) % _MOD
        }
        return a * pow(a, b - 1) % _MOD
    }
    func pow(_ t: Int) -> ModInt {
        if t <= 0 { return ModInt(1) }
        var a = self.pow(t >> 1)
        a *= a
        if t & 1 != 0 { a *= self }
        return a
    }
    func description() -> String { String(_value) }
}

func seq(_ start: ModInt, _ end: ModInt) -> [ModInt] {
    if start == end { return [start] }
    else {
        var result = [ModInt]()
        var temp = start
        while temp != end {
            result.append(temp)
            temp += 1
        }
        result.append(end)
        return result
    }
}
func seq(_ start: Double,_ end: Double,_ by: Double) -> [Double] {
    let length = Int(abs(round((end - start) / by)))
    var result = [Double]()
    if start >= end { for n in 0 ... length { result.append(start + by * Double(n)) } }
    else { for n in 0 ... length { result.append(start - by * Double(n)) } }
    return result
}

func xxxy() {
    var fac = [ModInt]()
    func combi(_ n: Int, _ k: Int) -> ModInt { fact(n) / fact(k) / fact(n - k) }
    func fact(_ n: Int) -> ModInt {
        if (fac.count == 0) { fac.append(ModInt(1)) }
        while (fac.count <= n) {
            fac.append(fac.last! * ModInt(fac.count))
        }
        return fac[n]
    }
}

/*
 struct Deque<T> {
 var firstQueue = [T]()
 var lastQueue = [T]()
 var isEmpty: Bool { firstQueue.isEmpty && lastQueue.isEmpty }
 var count: Int { firstQueue.count + lastQueue.count }
 mutating func addFirst(_ t: T) { firstQueue.append(t) }
 mutating func addLast(_ t: T) { lastQueue.append(t) }
 mutating func removeFirst() -> T? {
 if !firstQueue.isEmpty {
 return firstQueue.removeLast()
 } else if !lastQueue.isEmpty {
 return lastQueue.removeFirst()
 } else {
 return nil
 }
 
 }
 }
 */
/*
 struct Deque<T> {
 var elements = [T]()
 var isEmpty: Bool { elements.isEmpty }
 var count: Int { elements.count }
 mutating func addFirst(_ t: T) { elements.insert(t, at: 0) }
 mutating func addLast(_ t: T) { elements.append(t) }
 mutating func removeFirst() -> T? { if !isEmpty { return elements.removeFirst() } else { return nil } }
 mutating func removeLast() -> T? { elements.popLast() }
 mutating func peekFirst() -> T? { if !isEmpty { return elements.first } else { return nil } }
 mutating func peekLast() -> T? { if !isEmpty { return elements.last } else { return nil } }
 var description: String { elements.description }
 }
 */

// https://github.com/mattgallagher/CwlUtils
//
//  CwlDeque.swift
//  CwlUtils
//
//  Created by Matt Gallagher on 2016/09/13.
//  Copyright © 2016 Matt Gallagher ( https://www.cocoawithlove.com ). All rights reserved.
//
//  Permission to use, copy, modify, and/or distribute this software for any
//  purpose with or without fee is hereby granted, provided that the above
//  copyright notice and this permission notice appear in all copies.
//
//  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
//  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
//  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
//  SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
//  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
//  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
//  IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
//

import Foundation

/// This is a basic "circular-buffer" style Double-Ended Queue.
public struct Deque<T>: RandomAccessCollection, MutableCollection, RangeReplaceableCollection, ExpressibleByArrayLiteral, CustomDebugStringConvertible {
    public typealias Index = Int
    public typealias Indices = CountableRange<Int>
    public typealias Element = T
    
    private let overAllocateFactor = 2
    private let downsizeTriggerFactor = 16
    private let defaultMinimumCapacity = 5
    
    private var buffer: DequeBuffer<T>? = nil
    private var minCapacity: Int
    
    /// Implementation of RangeReplaceableCollection function
    public init() {
        self.minCapacity = defaultMinimumCapacity
    }
    
    /// Allocate with a minimum capacity
    public init(minCapacity: Int) {
        self.minCapacity = minCapacity
    }
    
    /// Implementation of ExpressibleByArrayLiteral function
    public init(arrayLiteral: T...) {
        self.minCapacity = defaultMinimumCapacity
        replaceSubrange(0..<0, with: arrayLiteral)
    }
    
    /// Implementation of CustomDebugStringConvertible function
    public var debugDescription: String {
        var result = "\(type(of: self))(["
        var iterator = makeIterator()
        if let next = iterator.next() {
            debugPrint(next, terminator: "", to: &result)
            while let n = iterator.next() {
                result += ", "
                debugPrint(n, terminator: "", to: &result)
            }
        }
        result += "])"
        return result
    }
    
    #if swift(>=4.1)
    public subscript(bounds: Range<Index>) -> Slice<Deque<T>> {
        return Slice<Deque<T>>(base: self, bounds: bounds)
    }
    #else
    public subscript(bounds: Range<Index>) -> RangeReplaceableRandomAccessSlice<Deque<T>> {
        return RangeReplaceableRandomAccessSlice<Deque<T>>(base: self, bounds: bounds)
    }
    #endif
    
    /// Implementation of RandomAccessCollection function
    public subscript(_ at: Index) -> T {
        get {
            return buffer!.withUnsafeMutablePointers { headerPtr, bodyPtr -> T in
                precondition(at >= 0 && at < headerPtr.pointee.count)
                var offset = headerPtr.pointee.offset + at
                if offset >= headerPtr.pointee.capacity {
                    offset -= headerPtr.pointee.capacity
                }
                return bodyPtr[offset]
            }
        }
        set {
            buffer!.withUnsafeMutablePointers { headerPtr, bodyPtr in
                precondition(at >= 0 && at < headerPtr.pointee.count)
                var offset = headerPtr.pointee.offset + at
                if offset >= headerPtr.pointee.capacity {
                    offset -= headerPtr.pointee.capacity
                }
                bodyPtr[offset] = newValue
            }
        }
    }
    
    /// Implementation of Collection function
    public var startIndex: Index {
        return 0
    }
    
    /// Implementation of Collection function
    public var endIndex: Index {
        return buffer?.withUnsafeMutablePointerToHeader { headerPtr in headerPtr.pointee.count } ?? 0
    }
    
    /// Implementation of Collection function
    public var isEmpty: Bool {
        return buffer?.withUnsafeMutablePointerToHeader { headerPtr in headerPtr.pointee.count == 0 } ?? true
    }
    
    /// Implementation of Collection function
    public var count: Int {
        return endIndex
    }
    
    /// Optimized implementation of RangeReplaceableCollection function
    public mutating func append(_ newElement: T) {
        let done = buffer?.withUnsafeMutablePointers { headerPtr, bodyPtr -> Bool in
            guard headerPtr.pointee.capacity >= headerPtr.pointee.count + 1 else { return false }
            var index = headerPtr.pointee.offset + headerPtr.pointee.count
            if index >= headerPtr.pointee.capacity {
                index -= headerPtr.pointee.capacity
            }
            bodyPtr.advanced(by: index).initialize(to: newElement)
            headerPtr.pointee.count += 1
            return true
            } ?? false
        
        if done {
            return
        }
        
        let index = endIndex
        return replaceSubrange(index..<index, with: CollectionOfOne(newElement))
    }
    
    /// Optimized implementation of RangeReplaceableCollection function
    public mutating func insert(_ newElement: T, at: Int) {
        let done = buffer?.withUnsafeMutablePointers { headerPtr, bodyPtr -> Bool in
            guard at == 0, headerPtr.pointee.capacity >= headerPtr.pointee.count + 1 else { return false }
            var index = headerPtr.pointee.offset - 1
            if index < 0 {
                index += headerPtr.pointee.capacity
            }
            bodyPtr.advanced(by: index).initialize(to: newElement)
            headerPtr.pointee.count += 1
            headerPtr.pointee.offset = index
            return true
            } ?? false
        
        if done {
            return
        }
        
        return replaceSubrange(at..<at, with: CollectionOfOne(newElement))
    }
    
    /// Optimized implementation of RangeReplaceableCollection function
    public mutating func remove(at: Int) {
        let done = buffer?.withUnsafeMutablePointers { headerPtr, bodyPtr -> Bool in
            if at == headerPtr.pointee.count - 1 {
                headerPtr.pointee.count -= 1
                return true
            } else if at == 0, headerPtr.pointee.count > 0 {
                headerPtr.pointee.offset += 1
                if headerPtr.pointee.offset >= headerPtr.pointee.capacity {
                    headerPtr.pointee.offset -= headerPtr.pointee.capacity
                }
                headerPtr.pointee.count -= 1
                return true
            }
            return false
            } ?? false
        
        if done {
            return
        }
        
        return replaceSubrange(at...at, with: EmptyCollection())
    }
    
    /// Optimized implementation of RangeReplaceableCollection function
    public mutating func removeFirst() -> T {
        return buffer!.withUnsafeMutablePointers { headerPtr, bodyPtr -> T in
            precondition(headerPtr.pointee.count > 0, "Index beyond bounds")
            let result = bodyPtr[headerPtr.pointee.offset]
            #if swift(>=4.1)
            bodyPtr.advanced(by: headerPtr.pointee.offset).deinitialize(count: 1)
            #else
            bodyPtr.advanced(by: headerPtr.pointee.offset).deinitialize()
            #endif
            headerPtr.pointee.offset += 1
            if headerPtr.pointee.offset >= headerPtr.pointee.capacity {
                headerPtr.pointee.offset -= headerPtr.pointee.capacity
            }
            headerPtr.pointee.count -= 1
            return result
        }
    }
    
    // Used when removing a range from the collection or deiniting self.
    private static func deinitialize(range: CountableRange<Int>, header: UnsafeMutablePointer<DequeHeader>, body: UnsafeMutablePointer<T>) {
        let splitRange = header.pointee.splitRangeIndices(inRange: range)
        body.advanced(by: splitRange.low.startIndex).deinitialize(count: splitRange.low.count)
        body.advanced(by: splitRange.high.startIndex).deinitialize(count: splitRange.high.count)
    }
    
    // Move from an initialized to an uninitialized location, deinitializing the source.
    //
    // NOTE: the terms "preMapped" and "postMapped" are used. "preMapped" refer to the public indices exposed by this type (zero based, contiguous), and "postMapped" refers to internal offsets within the buffer (not necessarily zero based and may wrap around). This function will only handle a single, contiguous block of "postMapped" indices so the caller must ensure that this function is invoked separately for each contiguous block.
    private static func moveInitialize(preMappedSourceRange: CountableRange<Int>, postMappedDestinationRange: CountableRange<Int>, sourceHeader: UnsafeMutablePointer<DequeHeader>, sourceBody: UnsafeMutablePointer<T>, destinationBody: UnsafeMutablePointer<T>) {
        let sourceSplitRange = sourceHeader.pointee.splitRangeIndices(inRange: preMappedSourceRange)
        
        assert(sourceSplitRange.low.startIndex >= 0 && (sourceSplitRange.low.startIndex < sourceHeader.pointee.capacity || sourceSplitRange.low.startIndex == sourceSplitRange.low.endIndex))
        assert(sourceSplitRange.low.endIndex >= 0 && sourceSplitRange.low.endIndex <= sourceHeader.pointee.capacity)
        
        assert(sourceSplitRange.high.startIndex >= 0 && (sourceSplitRange.high.startIndex < sourceHeader.pointee.capacity || sourceSplitRange.high.startIndex == sourceSplitRange.high.endIndex))
        assert(sourceSplitRange.high.endIndex >= 0 && sourceSplitRange.high.endIndex <= sourceHeader.pointee.capacity)
        
        destinationBody.advanced(by: postMappedDestinationRange.startIndex).moveInitialize(from: sourceBody.advanced(by: sourceSplitRange.low.startIndex), count: sourceSplitRange.low.count)
        destinationBody.advanced(by: postMappedDestinationRange.startIndex + sourceSplitRange.low.count).moveInitialize(from: sourceBody.advanced(by: sourceSplitRange.high.startIndex), count: sourceSplitRange.high.count)
    }
    
    // Copy from an initialized to an uninitialized location, leaving the source initialized.
    //
    // NOTE: the terms "preMapped" and "postMapped" are used. "preMapped" refer to the public indices exposed by this type (zero based, contiguous), and "postMapped" refers to internal offsets within the buffer (not necessarily zero based and may wrap around). This function will only handle a single, contiguous block of "postMapped" indices so the caller must ensure that this function is invoked separately for each contiguous block.
    private static func copyInitialize(preMappedSourceRange: CountableRange<Int>, postMappedDestinationRange: CountableRange<Int>, sourceHeader: UnsafeMutablePointer<DequeHeader>, sourceBody: UnsafeMutablePointer<T>, destinationBody: UnsafeMutablePointer<T>) {
        let sourceSplitRange = sourceHeader.pointee.splitRangeIndices(inRange: preMappedSourceRange)
        
        assert(sourceSplitRange.low.startIndex >= 0 && (sourceSplitRange.low.startIndex < sourceHeader.pointee.capacity || sourceSplitRange.low.startIndex == sourceSplitRange.low.endIndex))
        assert(sourceSplitRange.low.endIndex >= 0 && sourceSplitRange.low.endIndex <= sourceHeader.pointee.capacity)
        
        assert(sourceSplitRange.high.startIndex >= 0 && (sourceSplitRange.high.startIndex < sourceHeader.pointee.capacity || sourceSplitRange.high.startIndex == sourceSplitRange.high.endIndex))
        assert(sourceSplitRange.high.endIndex >= 0 && sourceSplitRange.high.endIndex <= sourceHeader.pointee.capacity)
        
        destinationBody.advanced(by: postMappedDestinationRange.startIndex).initialize(from: sourceBody.advanced(by: sourceSplitRange.low.startIndex), count: sourceSplitRange.low.count)
        destinationBody.advanced(by: postMappedDestinationRange.startIndex + sourceSplitRange.low.count).initialize(from: sourceBody.advanced(by: sourceSplitRange.high.startIndex), count: sourceSplitRange.high.count)
    }
    
    // Internal implementation of replaceSubrange<C>(_:with:) when no reallocation
    // of the underlying buffer is required
    private static func mutateWithoutReallocate<C>(info: DequeMutationInfo2, elements newElements: C, header: UnsafeMutablePointer<DequeHeader>, body: UnsafeMutablePointer<T>) where C: Collection, C.Iterator.Element == T {
        if info.removed > 0 {
            Deque.deinitialize(range: info.start..<(info.start + info.removed), header: header, body: body)
        }
        
        if info.removed != info.inserted {
            if info.start < header.pointee.count - (info.start + info.removed) {
                let oldOffset = header.pointee.offset
                header.pointee.offset -= info.inserted - info.removed
                if header.pointee.offset < 0 {
                    header.pointee.offset += header.pointee.capacity
                } else if header.pointee.offset >= header.pointee.capacity {
                    header.pointee.offset -= header.pointee.capacity
                }
                let delta = oldOffset - header.pointee.offset
                if info.start != 0 {
                    let destinationSplitIndices = header.pointee.splitRangeIndices(inRange: 0..<info.start)
                    let lowCount = destinationSplitIndices.low.count
                    Deque.moveInitialize(preMappedSourceRange: delta..<(delta + lowCount), postMappedDestinationRange: destinationSplitIndices.low, sourceHeader: header, sourceBody: body, destinationBody: body)
                    if lowCount != info.start {
                        Deque.moveInitialize(preMappedSourceRange: (delta + lowCount)..<(info.start + delta), postMappedDestinationRange: destinationSplitIndices.high, sourceHeader: header, sourceBody: body, destinationBody: body)
                    }
                }
            } else {
                if (info.start + info.removed) != header.pointee.count {
                    let start = info.start + info.removed
                    let end = header.pointee.count
                    let destinationSplitIndices = header.pointee.splitRangeIndices(inRange: (info.start + info.inserted)..<(end - info.removed + info.inserted))
                    let lowCount = destinationSplitIndices.low.count
                    
                    Deque.moveInitialize(preMappedSourceRange: start..<end, postMappedDestinationRange: destinationSplitIndices.low, sourceHeader: header, sourceBody: body, destinationBody: body)
                    if lowCount != end - start {
                        Deque.moveInitialize(preMappedSourceRange: (start + lowCount)..<end, postMappedDestinationRange: destinationSplitIndices.high, sourceHeader: header, sourceBody: body, destinationBody: body)
                    }
                }
            }
            header.pointee.count = header.pointee.count - info.removed + info.inserted
        }
        
        if info.inserted == 1, let e = newElements.first {
            if info.start >= header.pointee.capacity - header.pointee.offset {
                body.advanced(by: info.start - header.pointee.capacity + header.pointee.offset).initialize(to: e)
            } else {
                body.advanced(by: header.pointee.offset + info.start).initialize(to: e)
            }
        } else if info.inserted > 0 {
            let inserted = header.pointee.splitRangeIndices(inRange: info.start..<(info.start + info.inserted))
            var iterator = newElements.makeIterator()
            for i in inserted.low {
                if let n = iterator.next() {
                    body.advanced(by: i).initialize(to: n)
                }
            }
            for i in inserted.high {
                if let n = iterator.next() {
                    body.advanced(by: i).initialize(to: n)
                }
            }
        }
    }
    
    // Internal implementation of replaceSubrange<C>(_:with:) when reallocation
    // of the underlying buffer is required. Can handle no previous buffer or
    // previous buffer too small or previous buffer too big or previous buffer
    // non-unique.
    private mutating func reallocateAndMutate<C>(info: DequeMutationInfo2, elements newElements: C, header: UnsafeMutablePointer<DequeHeader>?, body: UnsafeMutablePointer<T>?, deletePrevious: Bool) where C: Collection, C.Iterator.Element == T {
        if info.newCount == 0 {
            // Let the regular deallocation handle the deinitialize
            buffer = nil
        } else {
            let newCapacity: Int
            let oldCapacity = header?.pointee.capacity ?? 0
            if info.newCount > oldCapacity || info.newCount <= oldCapacity / downsizeTriggerFactor {
                newCapacity = Swift.max(minCapacity, info.newCount * overAllocateFactor)
            } else {
                newCapacity = oldCapacity
            }
            
            let newBuffer = DequeBuffer<T>.create(minimumCapacity: newCapacity) { (buffer: ManagedBuffer<DequeHeader, T>) in
                return DequeHeader(offset: 0, count: info.newCount, capacity: newCapacity)
                } as! DequeBuffer<T>
            if let headerPtr = header, let bodyPtr = body {
                if deletePrevious, info.removed > 0 {
                    Deque.deinitialize(range: info.start..<(info.start + info.removed), header: headerPtr, body: bodyPtr)
                }
                
                newBuffer.withUnsafeMutablePointerToElements { newBody in
                    if info.start != 0 {
                        if deletePrevious {
                            Deque.moveInitialize(preMappedSourceRange: 0..<info.start, postMappedDestinationRange: 0..<info.start, sourceHeader: headerPtr, sourceBody: bodyPtr, destinationBody: newBody)
                        } else {
                            Deque.copyInitialize(preMappedSourceRange: 0..<info.start, postMappedDestinationRange: 0..<info.start, sourceHeader: headerPtr, sourceBody: bodyPtr, destinationBody: newBody)
                        }
                    }
                    
                    let oldCount = header?.pointee.count ?? 0
                    if info.start + info.removed != oldCount {
                        if deletePrevious {
                            Deque.moveInitialize(preMappedSourceRange: (info.start + info.removed)..<oldCount, postMappedDestinationRange: (info.start + info.inserted)..<info.newCount, sourceHeader: headerPtr, sourceBody: bodyPtr, destinationBody: newBody)
                        } else {
                            Deque.copyInitialize(preMappedSourceRange: (info.start + info.removed)..<oldCount, postMappedDestinationRange: (info.start + info.inserted)..<info.newCount, sourceHeader: headerPtr, sourceBody: bodyPtr, destinationBody: newBody)
                        }
                    }
                }
                
                // Make sure the old buffer doesn't deinitialize when it deallocates.
                if deletePrevious {
                    headerPtr.pointee.count = 0
                }
            }
            
            if info.inserted > 0 {
                newBuffer.withUnsafeMutablePointerToElements { newBody in
                    #if swift(>=3.1)
                    let umbp = UnsafeMutableBufferPointer(start: newBody.advanced(by: info.start), count: info.inserted)
                    _ = umbp.initialize(from: newElements)
                    #else
                    // Insert the new subrange
                    newBody.advanced(by: info.start).initialize(from: newElements)
                    #endif
                }
            }
            
            buffer = newBuffer
        }
    }
    
    /// Implemetation of the RangeReplaceableCollection function. Internally
    /// implemented using either mutateWithoutReallocate or reallocateAndMutate.
    public mutating func replaceSubrange<C>(_ subrange: Range<Int>, with newElements: C) where C: Collection, C.Iterator.Element == T {
        precondition(subrange.lowerBound >= 0, "Subrange lowerBound is negative")
        
        if isKnownUniquelyReferenced(&buffer), let b = buffer {
            b.withUnsafeMutablePointers { headerPtr, bodyPtr in
                let info = DequeMutationInfo2(subrange: subrange, previousCount: headerPtr.pointee.count, insertedCount: numericCast(newElements.count))
                if info.newCount <= headerPtr.pointee.capacity && (info.newCount < minCapacity || info.newCount > headerPtr.pointee.capacity / downsizeTriggerFactor) {
                    Deque.mutateWithoutReallocate(info: info, elements: newElements, header: headerPtr, body: bodyPtr)
                } else {
                    reallocateAndMutate(info: info, elements: newElements, header: headerPtr, body: bodyPtr, deletePrevious: true)
                }
            }
        } else if let b = buffer {
            b.withUnsafeMutablePointers { headerPtr, bodyPtr in
                let info = DequeMutationInfo2(subrange: subrange, previousCount: headerPtr.pointee.count, insertedCount: numericCast(newElements.count))
                reallocateAndMutate(info: info, elements: newElements, header: headerPtr, body: bodyPtr, deletePrevious: false)
            }
        } else {
            let info = DequeMutationInfo2(subrange: subrange, previousCount: 0, insertedCount: numericCast(newElements.count))
            reallocateAndMutate(info: info, elements: newElements, header: nil, body: nil, deletePrevious: true)
        }
    }
}

// Internal state for the Deque
private struct DequeHeader {
    var offset: Int
    var count: Int
    var capacity: Int
    
    // Translate from preMapped to postMapped indices.
    //
    // "preMapped" refer to the public indices exposed by this type (zero based, contiguous), and "postMapped" refers to internal offsets within the buffer (not necessarily zero based and may wrap around).
    //
    // Since "postMapped" indices are not necessarily contiguous, two separate, contiguous ranges are returned. Both `startIndex` and `endIndex` in the `high` range will equal the `endIndex` in the `low` range if the range specified by `inRange` is continuous after mapping.
    func splitRangeIndices(inRange: CountableRange<Int>) -> (low: CountableRange<Int>, high: CountableRange<Int>) {
        let limit = capacity - offset
        if inRange.startIndex >= limit {
            return (low: (inRange.startIndex - limit)..<(inRange.endIndex - limit), high: (inRange.endIndex - limit)..<(inRange.endIndex - limit))
        } else if inRange.endIndex > limit {
            return (low: (inRange.startIndex + offset)..<capacity, high: 0..<(inRange.endIndex - limit))
        }
        return (low: (inRange.startIndex + offset)..<(inRange.endIndex + offset), high: (inRange.endIndex + offset)..<(inRange.endIndex + offset))
    }
    
}

// Private type used to communicate parameters between replaceSubrange<C>(_:with:)
// and reallocateAndMutate or mutateWithoutReallocate
private struct DequeMutationInfo2 {
    let start: Int
    let removed: Int
    let inserted: Int
    let newCount: Int
    
    init(subrange: Range<Int>, previousCount: Int, insertedCount: Int) {
        precondition(subrange.upperBound <= previousCount, "Subrange upperBound is out of range")
        
        self.start = subrange.lowerBound
        self.removed = subrange.count
        self.inserted = insertedCount
        self.newCount = previousCount - self.removed + self.inserted
    }
}

// Private reimplementation of function with same name from stdlib/public/core/BuiltIn.swift
private func roundUp(_ offset: UInt, toAlignment alignment: Int) -> UInt {
    let x = offset + UInt(bitPattern: alignment) &- 1
    return x & ~(UInt(bitPattern: alignment) &- 1)
}

// Private reimplementation of definition from stdlib/public/SwiftShims/HeapObject.h
private struct HeapObject {
    let metadata: Int = 0
    let strongRefCount: UInt32 = 0
    let weakRefCount: UInt32 = 0
}

// An implementation of DequeBuffer using ManagedBufferPointer to allocate the
// storage and then using raw pointer offsets into self to access contents
// (avoiding the ManagedBufferPointer accessors which are a performance problem
// in Swift 3).
private final class DequeBuffer<T>: ManagedBuffer<DequeHeader, T> {
    #if true
    private static var headerOffset: Int {
        return Int(roundUp(UInt(MemoryLayout<HeapObject>.size), toAlignment: MemoryLayout<DequeHeader>.alignment))
    }
    
    private static var elementOffset: Int {
        return Int(roundUp(UInt(headerOffset) + UInt(MemoryLayout<DequeHeader>.size), toAlignment: MemoryLayout<T>.alignment))
    }
    
    private var bodyPtr: UnsafeMutablePointer<T> {
        return Unmanaged<DequeBuffer<T>>.passUnretained(self).toOpaque().advanced(by: DequeBuffer<T>.elementOffset).assumingMemoryBound(to: T.self)
    }
    
    private var headerPtr: UnsafeMutablePointer<DequeHeader> {
        return Unmanaged<DequeBuffer<T>>.passUnretained(self).toOpaque().advanced(by: DequeBuffer<T>.headerOffset).assumingMemoryBound(to: DequeHeader.self)
    }
    #endif
    
    deinit {
        #if true
        // We need to assert this in case some of our dirty assumptions stop being true
        assert(ManagedBufferPointer<DequeHeader, T>(unsafeBufferObject: self).withUnsafeMutablePointers { (header, body) in
            self.headerPtr == header && self.bodyPtr == body
        })
        
        let splitRange = headerPtr.pointee.splitRangeIndices(inRange: 0..<headerPtr.pointee.count)
        bodyPtr.advanced(by: splitRange.low.startIndex).deinitialize(count: splitRange.low.count)
        bodyPtr.advanced(by: splitRange.high.startIndex).deinitialize(count: splitRange.high.count)
        #else
        withUnsafeMutablePointers { headerPtr, bodyPtr in
            let splitRange = headerPtr.pointee.splitRangeIndices(inRange: 0..<headerPtr.pointee.count)
            bodyPtr.advanced(by: splitRange.low.startIndex).deinitialize(count: splitRange.low.count)
            bodyPtr.advanced(by: splitRange.high.startIndex).deinitialize(count: splitRange.high.count)
        }
        #endif
    }
}
